Power set: Difference between revisions
added Icon/Unicon example
(added Icon/Unicon example) |
|||
Line 764:
Prelude Data.List> subsequences [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}}==
| |||