Power set: Difference between revisions
Content added Content deleted
(added Icon/Unicon example) |
|||
Line 764: | Line 764: | ||
Prelude Data.List> subsequences [1,2,3] |
Prelude Data.List> subsequences [1,2,3] |
||
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] |
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] |
||
=={{header|Icon}} and {{header|Unicon}}== |
|||
===Recursive=== |
|||
The following version returns a set containing the powerset: |
|||
<lang Icon> |
|||
procedure power_set (s) |
|||
result := set () |
|||
if *s = 0 |
|||
then insert (result, set ()) # empty set |
|||
else { |
|||
head := ?s # take a random element |
|||
# and find powerset of remaining part of set |
|||
tail_pset := power_set (delete (copy(s), head)) |
|||
result ++:= tail_pset # add powerset of remainder to results |
|||
every ps := !tail_pset do # and add head to each powerset from the remainder |
|||
insert (result, insert (copy(ps), head)) |
|||
} |
|||
return result |
|||
end |
|||
</lang> |
|||
To test the above procedure: |
|||
<lang Icon> |
|||
procedure main () |
|||
every s := !power_set (set(1,2,3,4)) do { |
|||
writes ("[ ") |
|||
every writes (!s || " ") |
|||
write ("]") |
|||
} |
|||
end |
|||
</lang> |
|||
Output: |
|||
<pre> |
|||
[ 3 ] |
|||
[ 4 3 ] |
|||
[ 2 4 ] |
|||
[ 2 3 ] |
|||
[ 1 3 ] |
|||
[ 4 ] |
|||
[ 2 ] |
|||
[ 2 1 3 ] |
|||
[ 2 4 1 ] |
|||
[ 4 1 3 ] |
|||
[ 2 4 1 3 ] |
|||
[ ] |
|||
[ 2 4 3 ] |
|||
[ 1 ] |
|||
[ 4 1 ] |
|||
[ 2 1 ] |
|||
</pre> |
|||
===Generator=== |
|||
An alternative version, which generates each item in the power set in turn: |
|||
<lang Icon> |
|||
procedure power_set (s) |
|||
if *s = 0 |
|||
then suspend set () |
|||
else { |
|||
head := ?s |
|||
every ps := power_set (delete (copy(s), head)) do { |
|||
suspend ps |
|||
suspend insert (copy(ps), head) |
|||
} |
|||
} |
|||
end |
|||
procedure main () |
|||
every s := power_set (set(1,2,3,4)) do { |
|||
writes ("[ ") |
|||
every writes (!s || " ") |
|||
write ("]") |
|||
} |
|||
end |
|||
</lang> |
|||
=={{header|J}}== |
=={{header|J}}== |