Powerset

[Christian Maeder]

powerset :: [a] -> [[[a]]]
powerset [] = [[[]]]
powerset (x:xs) = [[]] : myzip x (powerset xs)

myzip :: a -> [[[a]]] -> [[[a]]]
myzip x [a] = [map (x:) a]
myzip x (a:b) = (map (x:) a ++ head b) : myzip x b

I suggest the above version for a sorted powerset. The result keeps a 
further nesting of lists for subsets of the same length. (Flatten this 
list with "concat".)

Call "length (concat (powerset [1..19]))" (on Hugs).

Christian

oleg@pobox.com wrote:
> The following seems to be a faster version of powerset that delivers
> results strictly in the order of increasing cardinality (i.e., all
> sets of size 1 first, then of size 2, etc). It seems to run faster
> than any other ordered version of powerset posted so far. On GHCi,
> length $ powerset [1..22] is computed roughly 4 times faster than
> powerset3 given earlier. On Hugs, the powerset below also runs faster,
> with less memory consumption and in fewer GC cycles, up to a limit of
> 18 for the size of the input set. Then something happens. length $
> powerset3 [1..19] runs out of memory on my (not current) version of
> Hugs too.
> 
> The algorithm is more complex, though.
> powerset [] = [[]]
> powerset [x] = [[],[x]]
> powerset xs = [] : runit (tail rsxtails) ps0
>    where
> 	xstails = tails xs
> 	rsxtails = reverse xstails
> 	ps0 = map (const [[]]) xstails
> 	psn tn psn1 = psnew
> 	   where
> 	    psnew = [tn]:
> 	     (zipWith (++)
> 	      (reverse (zipWith (\x psn1i -> map (x:) psn1i) xs (tail $ reverse$tail $ psn1)))
> 	      psnew)
> 
>         runit [tn] _ = [xs]
> 	runit (tn:tns) psn1 = (last newps) ++ (runit tns newps)
> 	    where newps = psn tn psn1
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>