The power set of S is the set of all subsets of S.
There will be total 2n sets where n is the number element of S.
For example, the set S={a,b,c}, we could use all 3 bits value to find the power set.
| 000 |
{} |
== {} union {} |
| 001 |
{c} |
== {} union {c} |
| 010 |
{b} |
== {} union {b} |
| 011 |
{b,c} |
== {} union {b,c} |
|
| 100 |
{a} |
== {a} union {} |
| 101 |
{a,c} |
== {a} union {c} |
| 110 |
{a,b} |
== {a} union {b} |
| 111 |
{a,b,c} |
== {a} union {b,c} |
|
By using this hint (the color red represents power set of {b,c}), the power set function can be defined as:
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = powerset xs ++ map (x:) (powerset xs)
-- powerset (x:xs) = powerset xs ++ [x:xs' | xs' <- powerset xs]
This entry was posted
on Sunday, January 14th, 2007 at 8:28 am and is filed under Haskell.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
May 5th, 2011 at 9:21 am
thank you, but i need to define powerset by comprehension so i can declare
x=powerset [1..] or powerset [1,3..]
i tried with pow A=[B| subset B A==True]
but it didn’t work
May 22nd, 2011 at 7:30 pm
Hmm… I didn’t expect that use powerset in such condition.
Well, you can take a look about the implementation of
Data.List.subsequences.
In fact, subsequences function “is” powerset and can apply with [1..].