That's very similar to a version I received in an offlist email, which I had been seeking permission to repost. I find this approach to be very elegant. #g -- At 14:53 10/06/03 +0200, Christian Maeder wrote:
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
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-------------------
Graham Klyne