#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
[EMAIL PROTECTED] 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
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
------------------- Graham Klyne <[EMAIL PROTECTED]> PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E
_______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
