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.