CODEWITHSUNDEEP
f#
coder4lyf
coder4lyf

Reputation: 927

Function to get the power sets of a set in F#

I'm trying to write a function in F# to get the powersets of a set. So far I have written :

let rec powerset = function
    |[] -> [[]]
    | [x] -> [[x]; []]
    |x::xs -> [x] :: (List.map (fun n -> [x; n]) xs) @ powerset xs;;

but this isn't returning the cases that have 3 or more elements, only the pairs, the single elements, and the empty set.

Upvotes: 2

Views: 934

Answers (1)

Random Dev
Random Dev

Reputation: 52290

You are on the right track, here is a working solution:

let rec powerset = 
   function
   | [] -> [[]]
   | (x::xs) -> 
      let xss = powerset xs 
      List.map (fun xs' -> x::xs') xss @ xss

See you only have to use this trick:

for each element x you there half of the elements of the powerset will include x and half will not

so you recursively generate the powerset of the remaining elements xss and concat the two parts (List.map (fun xs' -> x::xs') xss will prepend the x to each of those)

But please note that this is not tail recursive and will blow the stack for bigger lists - you can take this idea and try to implement it with seq or make a tail-recursive version if you like

Using seq

Here is a version that uses seq and the bijection between the binary representation of natural numbers (a subset of those) and the subsets of a set (you map the elements to digits and set 1 if the corresponding element is in the subset and 0 if not):

let powerset (xs : 'a seq) : 'a seq seq =
    let digits (n : bigint) : bool seq =
        Seq.unfold (fun n -> 
            if n <= 0I 
            then None 
            else Some (n &&& 1I = 1I, n >>> 1))
            n
    let subsetBy (i : bigint) : 'a seq =
        Seq.zip xs (digits i)
        |> Seq.choose (fun (x,b) -> if b then Some x else None)
    seq { 0I .. 2I**(Seq.length xs)-1I }
    |> Seq.map subsetBy

this will work for things like powerset [1..100] but it might take a long time to enumerate them all ;) (but it should not take to much memory...)

Upvotes: 3

Related Questions