Power Set #2
My power set solution is defined.
I just found there is challenge question about get the power set in “order” without using sort.
For example:
subsets [] = [[]]
subsets [1,2,3] = [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
My solution for this challenge is simply reuse my combination function.
combination :: [a] -> Int -> [[a]]
combination _ 0 = [[]]
combination [] _ = []
combination (x:xs) n = map (x:) (combination xs (n-1)) ++ combination xs n
subset :: [a] -> [[a]]
subset xs = concat [combination xs k | k <- [0..n]] where n = length xs
February 24th, 2009 at 1:02 am
I’ve modified your powerset function to the following, so that it can generate results even with infinite lists. Of course, it doesn’t return anything interesting, but even with huge number it fairly zips along, and completely fails to overflow the stack.
powerset :: [a] -> [[a]]
powerset xs = powerset’ xs 0
where powerset’ ::[a] -> Int -> [[a]]
powerset’ xs n =
case combinations’ of
[] -> []
otherwise -> combinations’ ++ powerset’ xs (n + 1)
where combinations’ = combinations xs n
It makes use of the fact that [] is returned when n is larger than the length of the list.
What do you reckon?
February 24th, 2009 at 1:03 am
How annoying, Even with leading spaces, it fails to indent properly. Oh well, I’m sure you can figure it out.