# Powerset

**Christian Maeder
**
maeder@tzi.de

*Tue, 10 Jun 2003 14:53:16 +0200*

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
*>*
*