Power set

From Fōrmulæ wiki
Jump to: navigation, search

This page is the answer to the task Power set in the Rosetta Code.

Description (from Rosetta Code)

A set is a collection (container) of certain values, without any particular order, and no repeated values.

It corresponds with a finite set in mathematics.

A set can be implemented as an associative array (partial mapping) in which the value of each key-value pair is ignored.

Given a set S, the power set (or powerset) of S, written P(S), or 2S, is the set of all subsets of S.

Task

By using a library or built-in set type, or by defining a set type with necessary operations, write a function with a set S as input that yields the power set 2S of S.

For example, the power set of {1,2,3,4} is

{{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}.

For a set which contains n elements, the corresponding power set has 2n elements, including the edge cases of empty set.

The power set of the empty set is the set which contains itself (20 = 1):

() = { }

And the power set of the set which contains only the empty set, has two subsets, the empty set and the set which contains the empty set (21 = 2):

({}) = { , { } }

Extra credit: Demonstrate that your language supports these last two powersets.

Program

No programs needed. Power set is intrinsically supported in Fōrmulæ.

Case 1

PowerSetCase1.png

Case 2. Extra credit

PowerSetCase2.png