Power set: Difference between revisions

Line 766:

=={{header|Icon}} and {{header|Unicon}}==

The two examples below show the similarities and differences between constructing an explicit representation of the solution, i.e. a set containing the powerset, and one using generators. The basic recursive algorithm is the same in each case, but wherever the first stores part of the result away, the second uses 'suspend' to immediate pass the result back to the caller. The caller may then decide to store the results in a set, a list, or dispose of each one as it appears.

===Set building===

Line 777:

Line 779:

then insert (result, set ()) # empty set

else {

head := ?s # take a random element

head := set(?s) # take a random element

# and find powerset of remaining part of set

tail_pset := power_set (x -- ~~set(~~head))

tail_pset := power_set (x -- 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, ps ++ ~~set(~~head))

insert (result, ps ++ head)

}

return result

Line 792:

Line 794:

procedure main ()

every s := !power_set (set(1,2,3,4)) do {

every s := !power_set (set(1,2,3,4)) do { # requires '!' to generate items in the result set

writes ("[ ")

every writes (!s || " ")

Line 829:

Line 831:

then suspend set ()

else {

head := ?s

head := set(?s)

every ps := power_set ~~(delete (copy~~(s), head)) do {

every ps := power_set (s -- head) do {

suspend ps

suspend ~~insert (copy(~~ps), head)

suspend ps ++ head

}

Line 838:

Line 840:

procedure main ()

every s := power_set (set(1,2,3,4)) do {

every s := power_set (set(1,2,3,4)) do { # power_set's values are generated by 'every'

writes ("[ ")

every writes (!s || " ")