# Power set

(Redirected from Power Set)
Power set
You are encouraged to solve this task according to the task description, using any language you may know.

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):
$\mathcal{P}$($\varnothing$) = { $\varnothing$ }
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):
$\mathcal{P}$({$\varnothing$}) = { $\varnothing$, { $\varnothing$ } }

## Contents

This solution prints the power set of words read from the command line.

with Ada.Text_IO, Ada.Command_Line; procedure Power_Set is    type List is array  (Positive range <>) of Positive;   Empty: List(1 .. 0);    procedure Print_All_Subsets(Set: List; Printable: List:= Empty) is       procedure Print_Set(Items: List) is 	 First: Boolean := True;      begin 	 Ada.Text_IO.Put("{ ");	 for Item of Items loop	    if First then 	       First := False; -- no comma needed	    else	       Ada.Text_IO.Put(", "); -- comma, to separate the items	    end if;	    Ada.Text_IO.Put(Ada.Command_Line.Argument(Item));	 end loop;	 Ada.Text_IO.Put_Line(" }");      end Print_Set;       Tail: List := Set(Set'First+1 .. Set'Last);    begin      if Set = Empty then	 Print_Set(Printable);      else	 Print_All_Subsets(Tail, Printable & Set(Set'First));	 Print_All_Subsets(Tail, Printable);      end if;   end Print_All_Subsets;    Set: List(1 .. Ada.Command_Line.Argument_Count);begin   for I in Set'Range loop -- initialize set      Set(I) := I;   end loop;   Print_All_Subsets(Set); -- do the workend Power_Set;
Output:
>./power_set cat dog mouse
{ cat, dog, mouse }
{ cat, dog }
{ cat, mouse }
{ cat }
{ dog, mouse }
{ dog }
{ mouse }
{  }
>./power_set 1 2
{ 1, 2 }
{ 1 }
{ 2 }
{  }

## ALGOL 68

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

Requires: ALGOL 68g mk14.1+

MODE MEMBER = INT; PROC power set = ([]MEMBER s)[][]MEMBER:(  [2**UPB s]FLEX[1:0]MEMBER r;  INT upb r := 0;  r[upb r +:= 1] := []MEMBER(());  FOR i TO UPB s DO    MEMBER e = s[i];    FOR j TO upb r DO      [UPB r[j] + 1]MEMBER x;      x[:UPB x-1] := r[j];      x[UPB x] := e; # append to the end of x #      r[upb r +:= 1] := x # append to end of r #    OD  OD;  r[upb r] := s;  r    );# Example: #test:(  [][]MEMBER set = power set((1, 2, 4));  FOR member TO UPB set DO    INT upb = UPB set[member];    FORMAT repr set = $"("f( upb=0 |$$|$n(upb-1)(d", ")d$)");"$;    printf(($"set["d"] = "$,member, repr set, set[member],$l$))  OD)

Output:

set[1] = ();
set[2] = (1);
set[3] = (2);
set[4] = (1, 2);
set[5] = (4);
set[6] = (1, 4);
set[7] = (2, 4);
set[8] = (1, 2, 4);


## AutoHotkey

ahk discussion

a = 1,a,--             ; elements separated by commasStringSplit a, a, ,   ; a0 = #elements, a1,a2,... = elements of the set t = {Loop % (1<<a0) {       ; generate all 0-1 sequences   x := A_Index-1   Loop % a0      t .= (x>>A_Index-1) & 1 ? a%A_Index% "," : ""   t .= "}n{"         ; new subsets in new lines}MsgBox % RegExReplace(SubStr(t,1,StrLen(t)-1),",}","}")

## BBC BASIC

The elements of a set are represented as the bits in an integer (hence the maximum size of set is 32).

      DIM list$(3) : list$() = "1", "2", "3", "4"      PRINT FNpowerset(list$()) END DEF FNpowerset(list$())      IF DIM(list$(),1) > 31 ERROR 100, "Set too large to represent as integer" LOCAL i%, j%, s$      s$= "{" FOR i% = 0 TO (2 << DIM(list$(),1)) - 1        s$+= "{" FOR j% = 0 TO DIM(list$(),1)          IF i% AND (1 << j%) s$+= list$(j%) + ","        NEXT        IF RIGHT$(s$) = "," s$= LEFT$(s$) s$ += "},"      NEXT i%      = LEFT$(s$) + "}"

Output:

{{},{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}}


## Bracmat

( ( powerset  =   done todo first    .   !arg:(?done.?todo)      & (   !todo:%?first ?todo          & (powerset$(!done !first.!todo),powerset$(!done.!todo))        | !done        )  )& out$(powerset$(.1 2 3 4)));

Output:

  1 2 3 4
, 1 2 3
, 1 2 4
, 1 2
, 1 3 4
, 1 3
, 1 4
, 1
, 2 3 4
, 2 3
, 2 4
, 2
, 3 4
, 3
, 4
,

## Burlesque

 blsq ) {1 2 3 4}R@{{} {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}}

## C

#include <stdio.h> struct node {	char *s;	struct node* prev;}; void powerset(char **v, int n, struct node *up){	struct node me; 	if (!n) {		putchar('[');		while (up) {			printf(" %s", up->s);			up = up->prev;		}		puts(" ]");	} else {		me.s = *v;		me.prev = up;		powerset(v + 1, n - 1, up);		powerset(v + 1, n - 1, &me);	}} int main(int argc, char **argv){	powerset(argv + 1, argc - 1, 0);	return 0;}
Output:
% ./a.out 1 2 3
[ ]
[ 3 ]
[ 2 ]
[ 3 2 ]
[ 1 ]
[ 3 1 ]
[ 2 1 ]
[ 3 2 1 ]


## C++

###  Non-recursive version

#include <iostream>#include <set>#include <vector>#include <iterator>#include <algorithm>typedef std::set<int> set_type;typedef std::set<set_type> powerset_type; powerset_type powerset(set_type const& set){  typedef set_type::const_iterator set_iter;  typedef std::vector<set_iter> vec;  typedef vec::iterator vec_iter;   struct local  {    static int dereference(set_iter v) { return *v; }  };   powerset_type result;   vec elements;  do  {    set_type tmp;    std::transform(elements.begin(), elements.end(),                   std::inserter(tmp, tmp.end()),                   local::dereference);    result.insert(tmp);    if (!elements.empty() && ++elements.back() == set.end())    {      elements.pop_back();    }    else    {      set_iter iter;      if (elements.empty())      {        iter = set.begin();      }      else      {        iter = elements.back();        ++iter;      }      for (; iter != set.end(); ++iter)      {        elements.push_back(iter);      }    }  } while (!elements.empty());   return result;} int main(){  int values[4] = { 2, 3, 5, 7 };  set_type test_set(values, values+4);   powerset_type test_powerset = powerset(test_set);   for (powerset_type::iterator iter = test_powerset.begin();       iter != test_powerset.end();       ++iter)  {    std::cout << "{ ";    char const* prefix = "";    for (set_type::iterator iter2 = iter->begin();         iter2 != iter->end();         ++iter2)    {      std::cout << prefix << *iter2;      prefix = ", ";    }    std::cout << " }\n";  }}

Output:

{  }
{ 2 }
{ 2, 3 }
{ 2, 3, 5 }
{ 2, 3, 5, 7 }
{ 2, 3, 7 }
{ 2, 5 }
{ 2, 5, 7 }
{ 2, 7 }
{ 3 }
{ 3, 5 }
{ 3, 5, 7 }
{ 3, 7 }
{ 5 }
{ 5, 7 }
{ 7 }


###  Recursive version

#include <iostream>#include <set> template<typename Set> std::set<Set> powerset(const Set& s, size_t n){    typedef typename Set::const_iterator SetCIt;    typedef typename std::set<Set>::const_iterator PowerSetCIt;    std::set<Set> res;    if(n > 0) {        std::set<Set> ps = powerset(s, n-1);        for(PowerSetCIt ss = ps.begin(); ss != ps.end(); ss++)            for(SetCIt el = s.begin(); el != s.end(); el++) {                Set subset(*ss);                subset.insert(*el);                res.insert(subset);            }        res.insert(ps.begin(), ps.end());    } else        res.insert(Set());    return res;}template<typename Set> std::set<Set> powerset(const Set& s){    return powerset(s, s.size());}

## C#

 public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list){    return from m in Enumerable.Range(0, 1 << list.Count)                  select                      from i in Enumerable.Range(0, list.Count)                      where (m & (1 << i)) != 0                      select list[i];} public void PowerSetofColors(){    var colors = new List<KnownColor> { KnownColor.Red, KnownColor.Green,         KnownColor.Blue, KnownColor.Yellow };     var result = GetPowerSet(colors);     Console.Write( string.Join( Environment.NewLine,         result.Select(subset =>             string.Join(",", subset.Select(clr => clr.ToString()).ToArray())).ToArray()));}

Output:

   Red  Green  Red,Green  Blue  Red,Blue  Green,Blue  Red,Green,Blue  Yellow  Red,Yellow  Green,Yellow  Red,Green,Yellow  Blue,Yellow  Red,Blue,Yellow  Green,Blue,Yellow  Red,Green,Blue,Yellow

An alternative implementation for an arbitrary number of elements:

   public IEnumerable<IEnumerable<T>> GetPowerSet<T>(IEnumerable<T> input) {    var seed = new List<IEnumerable<T>>() { Enumerable.Empty<T>() }      as IEnumerable<IEnumerable<T>>;     return input.Aggregate(seed, (a, b) =>      a.Concat(a.Select(x => x.Concat(new List<T>() { b }))));  }

## Clojure

(use '[clojure.math.combinatorics :only [subsets] ]) (def S #{1 2 3 4}) user> (subsets S)(() (1) (2) (3) (4) (1 2) (1 3) (1 4) (2 3) (2 4) (3 4) (1 2 3) (1 2 4) (1 3 4) (2 3 4) (1 2 3 4))

Alternate solution, with no dependency on third-party library:

(defn powerset [coll]   (reduce (fn [a x]            (->> a                 (map #(set (concat #{x} %)))                 (concat a)                 set))          #{#{}} coll)) (powerset #{1 2 3})
#{#{} #{1} #{2} #{1 2} #{3} #{1 3} #{2 3} #{1 2 3}}

## CoffeeScript

 print_power_set = (arr) ->  console.log "POWER SET of #{arr}"  for subset in power_set(arr)    console.log subset power_set = (arr) ->    result = []  binary = (false for elem in arr)  n = arr.length  while binary.length <= n    result.push bin_to_arr binary, arr    i = 0    while true      if binary[i]        binary[i] = false        i += 1      else        binary[i] = true        break    binary[i] = true  result bin_to_arr = (binary, arr) ->  (arr[i] for i of binary when binary[arr.length - i  - 1]) print_power_set []print_power_set [4, 2, 1] print_power_set ['dog', 'c', 'b', 'a']

output

 > coffee power_set.coffee POWER SET of []POWER SET of 4,2,1[][ 1 ][ 2 ][ 2, 1 ][ 4 ][ 4, 1 ][ 4, 2 ][ 4, 2, 1 ]POWER SET of dog,c,b,a[][ 'a' ][ 'b' ][ 'b', 'a' ][ 'c' ][ 'c', 'a' ][ 'c', 'b' ][ 'c', 'b', 'a' ][ 'dog' ][ 'dog', 'a' ][ 'dog', 'b' ][ 'dog', 'b', 'a' ][ 'dog', 'c' ][ 'dog', 'c', 'a' ][ 'dog', 'c', 'b' ][ 'dog', 'c', 'b', 'a' ]

## ColdFusion

Port from the JavaScript version, compatible with ColdFusion 8+ or Railo 3+

public array function powerset(required array data){  var ps = [""];  var d = arguments.data;  var lenData = arrayLen(d);  var lenPS = 0;  for (var i=1; i LTE lenData; i++)  {    lenPS = arrayLen(ps);    for (var j = 1; j LTE lenPS; j++)    {      arrayAppend(ps, listAppend(ps[j], d[i]));    }  }  return ps;} var res = powerset([1,2,3,4]);

Outputs:

["","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"]

## Common Lisp

(defun power-set (s)  (reduce #'(lambda (item ps)              (append (mapcar #'(lambda (e) (cons item e))                              ps)                      ps))          s          :from-end t          :initial-value '(())))

Output:

>(power-set '(1 2 3))
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) NIL)


Alternate, more recursive (same output):

(defun powerset (l)  (if (null l)      (list nil)      (let ((prev (powerset (cdr l))))	(append (mapcar #'(lambda (elt) (cons (car l) elt)) prev)		prev))))

Imperative-style using LOOP:

(defun powerset (xs)  (loop for i below (expt 2 (length xs)) collect       (loop for j below i for x in xs if (logbitp j i) collect x)))

Output:

>(powerset '(1 2 3)
(NIL (1) (2) (1 2) (3) (1 3) (2 3) (1 2 3))


Yet another imperative solution, this time with dolist.

(defun power-set (list)    (let ((pow-set (list nil)))      (dolist (element (reverse list) pow-set)        (dolist (set pow-set)          (push (cons element set) pow-set)))))

Output:

>(power-set '(1 2 3))
((1) (1 3) (1 2 3) (1 2) (2) (2 3) (3) NIL)


## D

Version using just arrays (it assumes the input to contain distinct items):

T[][] powerSet(T)(in T[] s) pure nothrow @safe {    auto r = new typeof(return)(1, 0);    foreach (e; s) {        typeof(return) rs;        foreach (x; r)            rs ~= x ~ [e];        r ~= rs;    }    return r;} void main() {    import std.stdio;     [1, 2, 3].powerSet.writeln;}
Output:
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

### Lazy Version

Compile with -version=power_set2_main to run the main.

auto powerSet(T)(T[] xs) pure nothrow @safe {    static struct Result {        T[] xsLocal, output;        size_t len;        size_t bits;         this(T[] xs_) pure nothrow @safe {            this.xsLocal = xs_;            this.output.length = xs_.length;            this.len = 1U << xs_.length;        }         @property empty() const pure nothrow @safe {            return bits == len;        }         void popFront() pure nothrow @safe { bits++; }        @property save() pure nothrow @safe { return this; }         T[] front() pure nothrow @safe {            size_t pos = 0;            foreach (immutable size_t i; 0 .. xsLocal.length)                if (bits & (1 << i))                    output[pos++] = xsLocal[i];            return output[0 .. pos];        }    }     return Result(xs);} version (power_set2_main) {    void main() {        import std.stdio;        [1, 2, 3].powerSet.writeln;    }}

Same output.

A set implementation and its power set function.

## Déjà Vu

In Déjà Vu, sets are dictionaries with all values true and the default set to false.

powerset s:	local :out [ set{ } ]	for value in keys s:		for subset in copy out:			local :subset+1 copy subset			set-to subset+1 value true			push-to out subset+1	out !. powerset set{ 1 2 3 4 }
Output:
[ set{ } set{ 4 } set{ 3 4 } set{ 3 } set{ 2 3 } set{ 2 3 4 } set{ 2 4 } set{ 2 } set{ 1 2 } set{ 1 2 4 } set{ 1 2 3 4 } set{ 1 2 3 } set{ 1 3 } set{ 1 3 4 } set{ 1 4 } set{ 1 } ]

## E

pragma.enable("accumulator") def powerset(s) {  return accum [].asSet() for k in 0..!2**s.size() {    _.with(accum [].asSet() for i ? ((2**i & k) > 0) => elem in s {      _.with(elem)    })  }}

It would also be possible to define an object which is the powerset of a provided set without actually instantiating all of its members immediately.

## Erlang

Generates all subsets of a list with the help of binary:

For [1 2 3]:
[     ] | 0 0 0 | 0
[    3] | 0 0 1 | 1
[  2  ] | 0 1 0 | 2
[  2 3] | 0 1 1 | 3
[1    ] | 1 0 0 | 4
[1   3] | 1 0 1 | 5
[1 2  ] | 1 1 0 | 6
[1 2 3] | 1 1 1 | 7
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

powerset(Lst) ->    N = length(Lst),    Max = trunc(math:pow(2,N)),    [[lists:nth(Pos+1,Lst) || Pos <- lists:seq(0,N-1), I band (1 bsl Pos) =/= 0]      || I <- lists:seq(0,Max-1)].

Which outputs: [[], [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]]

Alternate shorter and more efficient version:

powerset([]) -> [[]];powerset([H|T]) -> PT = powerset(T),  [ [H|X] || X <- PT ] ++ PT.

or even more efficient version:

powerset([]) -> [[]];powerset([H|T]) -> PT = powerset(T),  powerset(H, PT, PT). powerset(_, [], Acc) -> Acc;powerset(X, [H|T], Acc) -> powerset(X, T, [[X|H]|Acc]).

## F#

almost exact copy of OCaml version

 let subsets xs = List.foldBack (fun x rest -> rest @ List.map (fun ys -> x::ys) rest) xs [[]]

alternatively with list comprehension

 let rec pow =     function    | [] -> [[]]    | x::xs -> [for i in pow xs do yield! [i;x::i]]

## Factor

We use hash sets, denoted by HS{ } brackets, for our sets. members converts from a set to a sequence, and <hash-set> converts back.

USING: kernel prettyprint sequences arrays sets hash-sets ;IN: powerset : add ( set elt -- newset ) 1array <hash-set> union ;: powerset ( set -- newset ) members { HS{ } } [ dupd [ add ] curry map append ] reduce <hash-set> ;

Usage:

( scratchpad ) HS{ 1 2 3 4 } powerset .HS{    HS{ 1 2 3 4 }    HS{ 1 2 }    HS{ 1 3 }    HS{ 2 3 }    HS{ 1 2 3 }    HS{ 1 4 }    HS{ 2 4 }    HS{ }    HS{ 1 }    HS{ 2 }    HS{ 3 }    HS{ 4 }    HS{ 1 2 4 }    HS{ 3 4 }    HS{ 1 3 4 }    HS{ 2 3 4 }}

## Forth

Works with: 4tH version 3.61.0
.
Translation of: C
: ?print dup 1 and if over args type space then ;: .set begin dup while ?print >r 1+ r> 1 rshift repeat drop drop ;: .powerset 0 do ." ( " 1 i .set ." )" cr loop ;: check-none dup 2 < abort" Usage: powerset [val] .. [val]" ;: check-size dup /cell 8 [*] >= abort" Set too large" ;: powerset 1 argn check-none check-size 1- lshift .powerset ; powerset

Output:

$4th cxq powerset.4th 1 2 3 4 ( ) ( 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 )  ## Frink Frink's set and array classes have built-in subsets[] methods that return all subsets. If called with an array, the results are arrays. If called with a set, the results are sets.  a = new set[1,2,3,4] a.subsets[]  ## FunL FunL uses Scala type scala.collection.immutable.Set as it's set type, which has a built-in method subsets returning an (Scala) iterator over subsets. def powerset( s ) = s.subsets().toSet() The powerset function could be implemented in FunL directly as: def powerset( {} ) = {{}} powerset( s ) = acc = powerset( s.tail() ) acc + map( x -> {s.head()} + x, acc ) or, alternatively as: import lists.foldr def powerset( s ) = foldr( (x, acc) -> acc + map( a -> {x} + a, acc), {{}}, s ) println( powerset({1, 2, 3, 4}) ) Output: {{}, {4}, {1, 2}, {1, 3}, {2, 3, 4}, {3}, {1, 2, 3, 4}, {1, 4}, {1, 2, 3}, {2}, {1, 2, 4}, {1}, {3, 4}, {2, 3}, {2, 4}, {1, 3, 4}}  ## GAP # Built-inCombinations([1, 2, 3]); # [ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 2, 3 ], [ 3 ] ] # Note that it handles duplicatesCombinations([1, 2, 3, 1]);# [ [ ], [ 1 ], [ 1, 1 ], [ 1, 1, 2 ], [ 1, 1, 2, 3 ], [ 1, 1, 3 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ], # [ 2 ], [ 2, 3 ], [ 3 ] ] ## Go No native set type in Go. While the associative array trick mentioned in the task description works well in Go in most situations, it does not work here because we need sets of sets, and converting a general set to a hashable value for a map key is non-trivial. Instead, this solution uses a simple (non-associative) slice as a set representation. To ensure uniqueness, the element interface requires an equality method, which is used by the set add method. Adding elements with the add method ensures the uniqueness property. The power set method implemented here does not need the add method though. The algorithm ensures that the result will be a valid set as long as the input is a valid set. This allows the more efficient append function to be used. package main import ( "bytes" "fmt" "strconv") // types needed to implement general purpose sets are element and set // element is an interface, allowing different kinds of elements to be// implemented and stored in sets.type elem interface { // an element must be distinguishable from other elements to satisfy // the mathematical definition of a set. a.eq(b) must give the same // result as b.eq(a). Eq(element) bool // String result is used only for printable output. Given a, b where // a.eq(b), it is not required that a.String() == b.String(). fmt.Stringer} // integer type satisfying element interfacetype Int int func (i Int) Eq(e elem) bool { j, ok := e.(Int) return ok && i == j} func (i Int) String() string { return strconv.Itoa(int(i))} // a set is a slice of elem's. methods are added to implement// the element interface, to allow nesting.type set []elem // uniqueness of elements can be ensured by using add methodfunc (s *set) add(e elem) { if !s.has(e) { *s = append(*s, e) }} func (s *set) has(e elem) bool { for _, ex := range *s { if e.Eq(ex) { return true } } return false} // elem.Eqfunc (s set) Eq(e elem) bool { t, ok := e.(set) if !ok { return false } if len(s) != len(t) { return false } for _, se := range s { if !t.has(se) { return false } } return true} // elem.Stringfunc (s set) String() string { var buf bytes.Buffer buf.WriteRune('{') for _, e := range s { if len(r) > 1 { buf.WriteRune(' ') } buf.WriteString(e.String()) } buf.WriteRune('}') return buf.String()} // method required for taskfunc (s set) powerSet() set { r := set{set{}} for _, es := range s { var u set for _, er := range r { u = append(u, append(er.(set), es)) } r = append(r, u...) } return r} func main() { var s set for _, i := range []Int{1, 2, 2, 3, 4, 4, 4} { s.add(i) } fmt.Println(s) fmt.Println("length =", len(s)) ps := s.powerSet() fmt.Println(ps) fmt.Println("length =", len(ps))} Output: {1 2 3 4} length = 4 {{} {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}} length = 16  ## Groovy Builds on the Combinations solution. Sets are not a "natural" collection type in Groovy. Lists are much more richly supported. Thus, this solution is liberally sprinkled with coercion from Set to List and from List to Set. def combcomb = { m, List list -> def n = list.size() m == 0 ? [[]] : (0..(n-m)).inject([]) { newlist, k -> def sublist = (k+1 == n) ? [] : list[(k+1)..<n] newlist += comb(m-1, sublist).collect { [list[k]] + it } }} def powerSet = { set -> (0..(set.size())).inject([]){ list, i -> list + comb(i,set as List)}.collect { it as LinkedHashSet } as LinkedHashSet} Test program: def vocalists = [ "C", "S", "N", "Y" ] as LinkedHashSetprintln "${vocalists}"println powerSet(vocalists)

Output:

[C, S, N, Y]
[[], [C], [S], [N], [Y], [C, S], [C, N], [C, Y], [S, N], [S, Y], [N, Y], [C, S, N], [C, S, Y], [C, N, Y], [S, N, Y], [C, S, N, Y]]

Note: In this example, LinkedHashSet was used throughout for Set coercion. This is because LinkedHashSet preserves the order of input, like a List. However, if order does not matter you could replace all references to LinkedHashSet with Set.

import Data.Setimport Control.Monad powerset :: Ord a => Set a -> Set (Set a)powerset = fromList . fmap fromList . listPowerset . toList listPowerset :: [a] -> [[a]]listPowerset = filterM (const [True, False])

listPowerset describes the result as all possible (using the list monad) filterings (using filterM) of the input list, regardless (using const) of each item's value. powerset simply converts the input and output from lists to sets.

Alternate Solution

powerset [] = [[]]powerset (head:tail) = acc ++ map (head:) acc where acc = powerset tail

or

powerset = foldr (\x acc -> acc ++ map (x:) acc) [[]]

Examples:

*Main> listPowerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
*Main> powerset (Data.Set.fromList [1,2,3])
{{},{1},{1,2},{1,2,3},{1,3},{2},{2,3},{3}}

Works with: GHC version 6.10
Prelude> import Data.List
Prelude Data.List> subsequences [1,2,3]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]


Alternate solution

A method using only set operations and set mapping is also possible. Ideally, Set would be defined as a Monad, but that's impossible given the constraint that the type of inputs to Set.map (and a few other functions) be ordered.

import qualified Data.Set as Settype Set=Set.SetunionAll :: (Ord a) => Set (Set a) -> Set aunionAll = Set.fold Set.union Set.empty --slift is the analogue of liftA2 for sets.slift :: (Ord a, Ord b, Ord c) => (a->b->c) -> Set a -> Set b -> Set cslift f s0 s1 = unionAll (Set.map (\e->Set.map (f e) s1) s0) --a -> {{},{a}}makeSet :: (Ord a) => a -> Set (Set a)makeSet = (Set.insert Set.empty) . Set.singleton.Set.singleton powerSet :: (Ord a) => Set a -> Set (Set a)powerSet = (Set.fold (slift Set.union) (Set.singleton Set.empty)) . Set.map makeSet

Usage:

 Prelude Data.Set> powerSet fromList [1,2,3]fromList [fromList [], fromList [1], fromList [1,2], fromList [1,2,3], fromList [1,3], fromList [2], fromList [2,3], fromList [3]]

## Icon and 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 immediately 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

The following version returns a set containing the powerset:

 procedure power_set (s)  result := set ()  if *s = 0     then insert (result, set ()) # empty set    else {      head := set(?s) # take a random element      # and find powerset of remaining part of set      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 ++ head)    }  return resultend

To test the above procedure:

 procedure main ()  every s := !power_set (set(1,2,3,4)) do { # requires '!' to generate items in the result set    writes ("[ ")    every writes (!s || " ")    write ("]")  }end

Output:

[ 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 ]


### Generator

An alternative version, which generates each item in the power set in turn:

 procedure power_set (s)  if *s = 0     then suspend set ()    else {      head := set(?s)      every ps := power_set (s -- head) do {        suspend ps        suspend ps ++ head      }    }end procedure main ()  every s := power_set (set(1,2,3,4)) do { # power_set's values are generated by 'every'    writes ("[ ")    every writes (!s || " ")    write ("]")  }end

## J

There are a number of ways to generate a power set in J. Here's one:

ps =: #~ 2 #:@i.@^ #

For example:

   ps 'ACE' E  C  CE A  AE AC ACE

In the typical use, this operation makes sense on collections of unique elements.

   ~.1 2 3 2 11 2 3   #ps 1 2 3 2 132   #ps ~.1 2 3 2 18

In other words, the power set of a 5 element set has 32 sets where the power set of a 3 element set has 8 sets. Thus if elements of the original "set" were not unique then sets of the power "set" will also not be unique sets.

## Java

Works with: Java version 1.5+

### Recursion

This implementation sorts each subset, but not the whole list of subsets (which would require a custom comparator). It also destroys the original set.

public static ArrayList<String> getpowerset(int a[],int n,ArrayList<String> ps)    {        if(n<0)        {            return null;        }        if(n==0)        {            if(ps==null)                ps=new ArrayList<String>();            ps.add(" ");            return ps;        }        ps=getpowerset(a, n-1, ps);        ArrayList<String> tmp=new ArrayList<String>();        for(String s:ps)        {            if(s.equals(" "))                tmp.add(""+a[n-1]);            else                tmp.add(s+a[n-1]);        }        ps.addAll(tmp);        return ps;    }

### Iterative

The iterative implementation of the above idea. Each subset is in the order that the element appears in the input list. This implementation preserves the input.

 public static <T> List<List<T>> powerset(Collection<T> list) {  List<List<T>> ps = new ArrayList<List<T>>();  ps.add(new ArrayList<T>());   // add the empty set   // for every item in the original list  for (T item : list) {    List<List<T>> newPs = new ArrayList<List<T>>();     for (List<T> subset : ps) {      // copy all of the current powerset's subsets      newPs.add(subset);       // plus the subsets appended with the current item      List<T> newSubset = new ArrayList<T>(subset);      newSubset.add(item);      newPs.add(newSubset);    }     // powerset is now powerset of list.subList(0, list.indexOf(item)+1)    ps = newPs;  }  return ps;}

### Binary String

This implementation works on idea that each element in the original set can either be in the power set or not in it. With n elements in the original set, each combination can be represented by a binary string of length n. To get all possible combinations, all you need is a counter from 0 to 2n - 1. If the kth bit in the binary string is 1, the kth element of the original set is in this combination.

public static <T extends Comparable<? super T>> LinkedList<LinkedList<T>> BinPowSet(		LinkedList<T> A){	LinkedList<LinkedList<T>> ans= new LinkedList<LinkedList<T>>();	int ansSize = (int)Math.pow(2, A.size());	for(int i= 0;i< ansSize;++i){		String bin= Integer.toBinaryString(i); //convert to binary		while(bin.length() < A.size()) bin = "0" + bin; //pad with 0's		LinkedList<T> thisComb = new LinkedList<T>(); //place to put one combination		for(int j= 0;j< A.size();++j){			if(bin.charAt(j) == '1')thisComb.add(A.get(j));		}		Collections.sort(thisComb); //sort it for easy checking		ans.add(thisComb); //put this set in the answer list	}	return ans;}

## JavaScript

Uses a JSON stringifier from http://www.json.org/js.html

Works with: SpiderMonkey
function powerset(ary) {    var ps = [[]];    for (var i=0; i < ary.length; i++) {        for (var j = 0, len = ps.length; j < len; j++) {            ps.push(ps[j].concat(ary[i]));        }    }    return ps;} var res = powerset([1,2,3,4]); load('json2.js');print(JSON.stringify(res));

Outputs:

[[],[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]]

## Julia

function powerset (x)  result = {{}}  for i in x, j = 1:length(result)    push!(result, [result[j],i])  end  resultend
Output:
julia> show(powerset({1,2,3}))
{{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}}

## K

    ps:{x@&:'+2_vs!_2^#x}

Usage:

    ps "ABC"("" ,"C" ,"B" "BC" ,"A" "AC" "AB" "ABC")

## Logo

to powerset :set  if empty? :set [output [[]]]  localmake "rest powerset butfirst :set  output sentence  map [sentence first :set ?] :rest  :restend show powerset [1 2 3][[1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []]

## Logtalk

:- object(set).     :- public(powerset/2).     powerset(Set, PowerSet) :-        reverse(Set, RSet),        powerset_1(RSet, [[]], PowerSet).     powerset_1([], PowerSet, PowerSet).    powerset_1([X| Xs], Yss0, Yss) :-        powerset_2(Yss0, X, Yss1),        powerset_1(Xs, Yss1, Yss).     powerset_2([], _, []).    powerset_2([Zs| Zss], X, [Zs, [X| Zs]| Yss]) :-        powerset_2(Zss, X, Yss).     reverse(List, Reversed) :-        reverse(List, [], Reversed).     reverse([], Reversed, Reversed).    reverse([Head| Tail], List, Reversed) :-        reverse(Tail, [Head| List], Reversed). :- end_object.

Usage example:

| ?- set::powerset([1, 2, 3, 4], PowerSet). PowerSet = [[],[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]]yes

## Lua

 --returns the powerset of s, out of order.function powerset(s, start)  start = start or 1  if(start > #s) then return {{}} end  local ret = powerset(s, start + 1)  for i = 1, #ret do    ret[#ret + 1] = {s[start], unpack(ret[i])}  end  return retend --non-recurse implementationfunction powerset(s)   local t = {{}}   for i = 1, #s do      for j = 1, #t do         t[#t+1] = {s[i],unpack(t[j])}      end   end   return tend --alternative, copied from the Python implementationfunction powerset2(s)  local ret = {{}}  for i = 1, #s do    local k = #ret    for j = 1, k do      ret[k + j] = {s[i], unpack(ret[j])}    end  end  return retend

## Objective-C

#import <Foundation/Foundation.h> + (NSArray *)powerSetForArray:(NSArray *)array {	UInt32 subsetCount = 1 << array.count;	NSMutableArray *subsets = [NSMutableArray arrayWithCapacity:subsetCount];	for(int subsetIndex = 0; subsetIndex < subsetCount; subsetIndex++) {		NSMutableArray *subset = [[NSMutableArray alloc] init];		for (int itemIndex = 0; itemIndex < array.count; itemIndex++) {			if((subsetIndex >> itemIndex) & 0x1) {				[subset addObject:array[itemIndex]];			}		}				[subsets addObject:subset];	}	return subsets;}

## OCaml

The standard library already implements a proper Set datatype. As the base type is unspecified, the powerset must be parameterized as a module. Also, the library is lacking a map operation, which we have to implement first.

module PowerSet(S: Set.S) =struct   include Set.Make (S)   let map f s =    let work x r = add (f x) r in    fold work s empty  ;;   let powerset s =     let base = singleton (S.empty) in    let work x r = union r (map (S.add x) r) in     S.fold work s base  ;; end;; (* PowerSet *)

version for lists:

let subsets xs = List.fold_right (fun x rest -> rest @ List.map (fun ys -> x::ys) rest) xs [[]]

## OPL

 {string} s={"A","B","C","D"};range r=1.. ftoi(pow(2,card(s)));{string} s2 [k in r] = {i | i in s: ((k div (ftoi(pow(2,(ord(s,i))))) mod 2) == 1)}; execute{ writeln(s2);}  

which gives

  [{} {"A"} {"B"} {"A" "B"} {"C"} {"A" "C"} {"B" "C"} {"A" "B" "C"} {"D"} {"A"         "D"} {"B" "D"} {"A" "B" "D"} {"C" "D"} {"A" "C" "D"} {"B" "C" "D"}         {"A" "B" "C" "D"}]    

## Oz

Oz has a library for finite set constraints. Creating a power set is a trivial application of that:

declare  %% Given a set as a list, returns its powerset (again as a list)  fun {Powerset Set}     proc {Describe Root}        %% Describe sets by lower bound (nil) and upper bound (Set)        Root = {FS.var.bounds nil Set}        %% enumerate all possible sets        {FS.distribute naive [Root]}     end     AllSets = {SearchAll Describe}  in     %% convert to list representation     {Map AllSets FS.reflect.lowerBoundList}  endin  {Inspect {Powerset [1 2 3 4]}}

A more convential implementation without finite set constaints:

fun {Powerset2 Set}   case Set of nil then [nil]   [] H|T thens      Acc = {Powerset2 T}   in      {Append Acc {Map Acc fun {$A} H|A end}} endend ## PARI/GP vector(1<<#S,i,vecextract(S,i-1)) ## Perl Perl does not have a built-in set data-type. However, you can... • Use a third-party module The CPAN module Set::Object provides a set implementation for sets of arbitrary objects, for which a powerset function could be defined and used like so: use Set::Object qw(set); sub powerset { my$p = Set::Object->new( set() );    foreach my $i (shift->elements) {$p->insert( map { set($_->elements,$i) } $p->elements ); } return$p;} my $set = set(1, 2, 3);my$powerset = powerset($set); print$powerset->as_string, "\n";

Output:

Set::Object(Set::Object() Set::Object(1 2 3) Set::Object(1 2) Set::Object(1 3) Set::Object(1) Set::Object(2 3) Set::Object(2) Set::Object(3))
• Use a simple custom hash-based set type

It's also easy to define a custom type for sets of strings or numbers, using a hash as the underlying representation (like the task description suggests):

package Set {    sub new       { bless { map {$_ => undef} @_[1..$#_] }, shift; }    sub elements  { sort keys %{shift()} }    sub as_string { 'Set(' . join(' ', sort keys %{shift()}) . ')' }    # ...more set methods could be defined here...}

(Note: For a ready-to-use module that uses this approach, and comes with all the standard set methods that you would expect, see the CPAN module Set::Tiny)

The limitation of this approach is that only primitive strings/numbers are allowed as hash keys in Perl, so a Set of Set's cannot be represented, and the return value of our powerset function will thus have to be a list of sets rather than being a Set object itself.

We could implement the function as an imperative foreach loop similar to the Set::Object based solution above, but using list folding (with the help of Perl's List::Util core module) seems a little more elegant in this case:

use List::Util qw(reduce); sub powerset {    @{( reduce { [@$a, map { Set->new($_->elements, $b) } @$a ] }               [Set->new()], shift->elements )};} my $set = Set->new(1, 2, 3);my @subsets = powerset($set); print $_->as_string, "\n" for @subsets; Output: Set() Set(1) Set(2) Set(1 2) Set(3) Set(1 3) Set(2 3) Set(1 2 3)  • Use arrays If you don't actually need a proper set data-type that guarantees uniqueness of its elements, the simplest approach is to use arrays to store "sets" of items, in which case the implementation of the powerset function becomes quite short. Recursive solution: sub powerset { @_ ? map {$_, [$_[0], @$_] } powerset(@_[1..$#_]) : [];} List folding solution: use List::Util qw(reduce); sub powerset { @{( reduce { [@$a, map([@$_,$b], @$a)] } [[]], @_ )}} Usage & output: my @set = (1, 2, 3);my @powerset = powerset(@set); sub set_to_string { "{" . join(", ", map { ref$_ ? set_to_string(@$_) :$_ } @_) . "}"} print set_to_string(@powerset), "\n";
{{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}


## Perl 6

Works with: rakudo version 2014-02-25
sub powerset(Set $s) {$s.combinations.map(*.Set).Set }say powerset set <a b c d>;
Output:
set(set(), set(a), set(b), set(c), set(d), set(a, b), set(a, c), set(a, d), set(b, c), set(b, d), set(c, d), set(a, b, c), set(a, b, d), set(a, c, d), set(b, c, d), set(a, b, c, d))

If you don't care about the actual Set type, the .combinations method by itself may be good enough for you:

.say for <a b c d>.combinations
Output:

a
b
c
d
a b
a c
a d
b c
b d
c d
a b c
a b d
a c d
b c d
a b c d

## PHP

 <?phpfunction get_subset($binary,$arr) {  // based on true/false values in $binary array, include/exclude // values from$arr  $subset = array(); foreach (range(0, count($arr)-1) as $i) { if ($binary[$i]) {$subset[] = $arr[count($arr) - $i - 1]; } } return$subset;} function print_array($arr) { if (count($arr) > 0) {    echo join(" ", $arr); } else { echo "(empty)"; } echo '<br>';} function print_power_sets($arr) {  echo "POWER SET of [" . join(", ", $arr) . "]<br>"; foreach (power_set($arr) as $subset) { print_array($subset);  }} function power_set($arr) {$binary = array();  foreach (range(1, count($arr)) as$i) {    $binary[] = false; }$n = count($arr);$powerset = array();   while (count($binary) <= count($arr)) {    $powerset[] = get_subset($binary, $arr);$i = 0;    while (true) {      if ($binary[$i]) {        $binary[$i] = false;        $i += 1; } else {$binary[$i] = true; break; } }$binary[$i] = true; } return$powerset;} print_power_sets(array());print_power_sets(array('singleton'));print_power_sets(array('dog', 'c', 'b', 'a'));?> 

Output in browser:

 POWER SET of []POWER SET of [singleton](empty)singletonPOWER SET of [dog, c, b, a](empty)aba bca cb ca b cdoga dogb doga b dogc doga c dogb c doga b c dog 

## PicoLisp

(de powerset (Lst)   (ifn Lst      (cons)      (let L (powerset (cdr Lst))         (conc            (mapcar '((X) (cons (car Lst) X)) L)            L ) ) ) )

## PL/I

*process source attributes xref or(!); /*-------------------------------------------------------------------- * 06.01.2014 Walter Pachl  translated from REXX *-------------------------------------------------------------------*/ powerset: Proc Options(main); Dcl (hbound,index,left,substr) Builtin; Dcl sysprint Print; Dcl s(4) Char(5) Var Init('one','two','three','four'); Dcl ps   Char(1000) Var; Dcl (n,chunk,p) Bin Fixed(31); n=hbound(s);                      /* number of items in the list.   */ ps='{} ';                         /* start with a null power set.   */ Do chunk=1 To n;                  /* loop through the ...     .     */   ps=ps!!combn(chunk);            /* a CHUNK at a time.             */   End; Do While(ps>'');   p=index(ps,' ');   Put Edit(left(ps,p-1))(Skip,a);   ps=substr(ps,p+1);   End;  combn: Proc(y) Returns(Char(1000) Var); /*-------------------------------------------------------------------- * returns the list of subsets with y elements of set s *-------------------------------------------------------------------*/ Dcl (y,base,bbase,ym,p,j,d,u) Bin Fixed(31); Dcl (z,l) Char(1000) Var Init(''); Dcl a(20) Bin Fixed(31) Init((20)0); Dcl i Bin Fixed(31); base=hbound(s)+1; bbase=base-y; ym=y-1; Do p=1 To y;   a(p)=p;   End; Do j=1 By 1;   l='';   Do d=1 To y;     u=a(d);     l=l!!','!!s(u);     End;   z=z!!'{'!!substr(l,2)!!'} ';   a(y)=a(y)+1;   If a(y)=base Then     If combu(ym) Then       Leave;   End; /* Put Edit('combn',y,z)(Skip,a,f(2),x(1),a); */ Return(z);  combu: Proc(d) Recursive Returns(Bin Fixed(31)); Dcl (d,u) Bin Fixed(31); If d=0 Then   Return(1); p=a(d); Do u=d To y;   a(u)=p+1;   If a(u)=bbase+u Then     Return(combu(u-1));   p=a(u);   End; Return(0); End; End;  End;

output

{}
{one}
{two}
{three}
{four}
{one,two}
{one,three}
{one,four}
{two,three}
{two,four}
{three,four}
{one,two,three}
{one,two,four}
{one,three,four}
{two,three,four}
{one,two,three,four}

## Prolog

### Logical (cut-free) Definition

The predicate powerset(X,Y) defined here can be read as "Y is the powerset of X", it being understood that lists are used to represent sets.

The predicate subseq(X,Y) is true if and only if the list X is a subsequence of the list Y.

The definitions here are elementary, logical (cut-free), and efficient (within the class of comparably generic implementations).

powerset(X,Y) :- bagof( S, subseq(S,X), Y). subseq( [], []).subseq( [], [_|_]).subseq( [X|Xs], [X|Ys] ) :- subseq(Xs, Ys).subseq( [X|Xs], [_|Ys] ) :- append(_, [X|Zs], Ys), subseq(Xs, Zs). 

Output :

?- powerset([1,2,3], X).
X = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]].

% Symbolic:
?- powerset( [X,Y], S).
S = [[], [X], [X, Y], [Y]].

% In reverse:
?- powerset( [X,Y], [[], [1], [1, 2], [2]] ).
X = 1,
Y = 2.

### Single-Functor Definition

power_set( [], [[]]).power_set( [X|Xs], PS) :-  power_set(Xs, PS1),  maplist( append([X]), PS1, PS2 ), % i.e. prepend X to each PS1  append(PS1, PS2, PS).

Output :

?- power_set([1,2,3,4,5,6,7,8], X), length(X,N), writeln(N).
256


### Constraint Handling Rules

CHR is a programming language created by Professor Thom Frühwirth.
Works with SWI-Prolog and module chr written by Tom Schrijvers and Jan Wielemaker.

:- use_module(library(chr)). :- chr_constraint chr_power_set/2, chr_power_set/1, clean/0. clean @ clean \ chr_power_set(_) <=> true.clean @ clean <=> true. only_one @ chr_power_set(A) \ chr_power_set(A) <=> true.  creation @ chr_power_set([H | T], A) <=>           append(A, [H], B),	   chr_power_set(T, A),           chr_power_set(T, B),	   chr_power_set(B).  empty_element @ chr_power_set([], _) <=> chr_power_set([]). 

Example of output :

 ?- chr_power_set([1,2,3,4], []), findall(L, find_chr_constraint(chr_power_set(L)), LL), clean.
LL = [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,4],[1,3],[1,3,4],[1,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4],[]] .


## PureBasic

This code is for console mode.

If OpenConsole()  Define argc=CountProgramParameters()  If argc>=(SizeOf(Integer)*8) Or argc<1    PrintN("Set out of range.")    End 1  Else    Define i, j, text$Define.q bset=1<<argc Print("{") For i=0 To bset-1 ; check all binary combinations If Not i: text$=  "{"      Else    : text$=", {" EndIf k=0 For j=0 To argc-1 ; step through each bit If i&(1<<j) If k: text$+", ": EndIf         ; pad the output           text$+ProgramParameter(j): k+1 ; append each matching bit EndIf Next j Print(text$+"}")    Next i    PrintN("}")  EndIfEndIf

Sample output

C:\Users\PureBasic_User\Desktop>"Power Set.exe" 1 2 3 4
{{}, {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}}

## Python

def list_powerset(lst):    # the power set of the empty set has one element, the empty set    result = [[]]    for x in lst:        # for every additional element in our set        # the power set consists of the subsets that don't        # contain this element (just take the previous power set)        # plus the subsets that do contain the element (use list        # comprehension to add [x] onto everything in the        # previous power set)        result.extend([subset + [x] for subset in result])    return result # the above function in one statementdef list_powerset2(lst):    return reduce(lambda result, x: result + [subset + [x] for subset in result],                  lst, [[]]) def powerset(s):    return frozenset(map(frozenset, list_powerset(list(s))))

list_powerset computes the power set of a list of distinct elements. powerset simply converts the input and output from lists to sets. We use the frozenset type here for immutable sets, because unlike mutable sets, it can be put into other sets.

Example:

>>> list_powerset([1,2,3])
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
>>> powerset(frozenset([1,2,3]))
frozenset([frozenset([3]), frozenset([1, 2]), frozenset([]), frozenset([2, 3]), frozenset([1]), frozenset([1, 3]), frozenset([1, 2, 3]), frozenset([2])])


####  Further Explanation

If you take out the requirement to produce sets and produce list versions of each powerset element, then add a print to trace the execution, you get this simplified version of the program above where it is easier to trace the inner workings

def powersetlist(s):    r = [[]]    for e in s:        print "r: %-55r e: %r" % (r,e)        r += [x+[e] for x in r]    return r s= [0,1,2,3]    print "\npowersetlist(%r) =\n  %r" % (s, powersetlist(s))

Sample output:

r: [[]]                                                    e: 0
r: [[], [0]]                                               e: 1
r: [[], [0], [1], [0, 1]]                                  e: 2
r: [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]]  e: 3

powersetlist([0, 1, 2, 3]) =
[[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2], [3], [0, 3], [1, 3], [0, 1, 3], [2, 3], [0, 2, 3], [1, 2, 3], [0, 1, 2, 3]]


###  Binary Count method

If you list the members of the set and include them according to if the corresponding bit position of a binary count is true then you generate the powerset. (Note that only frozensets can be members of a set in the second function)

def powersequence(val):    ''' Generate a 'powerset' for sequence types that are indexable by integers.        Uses a binary count to enumerate the members and returns a list         Examples:            >>> powersequence('STR')   # String            ['', 'S', 'T', 'ST', 'R', 'SR', 'TR', 'STR']            >>> powersequence([0,1,2]) # List            [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]]            >>> powersequence((3,4,5)) # Tuple            [(), (3,), (4,), (3, 4), (5,), (3, 5), (4, 5), (3, 4, 5)]            >>>     '''    vtype = type(val); vlen = len(val); vrange = range(vlen)    return [ reduce( lambda x,y: x+y, (val[i:i+1] for i in vrange if 2**i & n), vtype())             for n in range(2**vlen) ] def powerset(s):    ''' Generate the powerset of s         Example:            >>> powerset(set([6,7,8]))            set([frozenset([7]), frozenset([8, 6, 7]), frozenset([6]), frozenset([6, 7]), frozenset([]), frozenset([8]), frozenset([8, 7]), frozenset([8, 6])])    '''    return set( frozenset(x) for x in powersequence(list(s)) )

###  Recursive Alternative

This is an (inefficient) recursive version that almost reflects the recursive definition of a power set as explained in http://en.wikipedia.org/wiki/Power_set#Algorithms. It does not create a sorted output.

 def p(l):    if not l: return [[]]    return p(l[1:]) + [[l[0]] + x for x in p(l[1:])] 

### Python: Standard documentation

Pythons documentation has a method that produces the groupings, but not as sets:

>>> from pprint import pprint as pp>>> from itertools import chain, combinations>>> >>> def powerset(iterable):    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"    s = list(iterable)    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) >>> pp(set(powerset({1,2,3,4}))){(), (1,), (1, 2), (1, 2, 3), (1, 2, 3, 4), (1, 2, 4), (1, 3), (1, 3, 4), (1, 4), (2,), (2, 3), (2, 3, 4), (2, 4), (3,), (3, 4), (4,)}>>> 

## Qi

Translation of: Scheme
 (define powerset  [] -> [[]]  [A|As] -> (append (map (cons A) (powerset As))                    (powerset As))) 

## R

### Non-recursive version

The conceptual basis for this algorithm is the following:

for each element in the set:	for each subset constructed so far:		new subset = (subset + element) 

This method is much faster than a recursive method, though the speed is still O(2^n).

powerset = function(set){	ps = list()	ps[[1]] = numeric()						#Start with the empty set.	for(element in set){						#For each element in the set, take all subsets		temp = vector(mode="list",length=length(ps))		#currently in "ps" and create new subsets (in "temp")		for(subset in 1:length(ps)){				#by adding "element" to each of them.			temp[[subset]] = c(ps[[subset]],element)		}		ps=c(ps,temp)						#Add the additional subsets ("temp") to "ps".	}	return(ps)} powerset(1:4) 

The list "temp" is a compromise between the speed costs of doing arithmetic and of creating new lists (since R lists are immutable, appending to a list means actually creating a new list object). Thus, "temp" collects new subsets that are later added to the power set. This improves the speed by 4x compared to extending the list "ps" at every step.

### Recursive version

Library: sets

The sets package includes a recursive method to calculate the power set. However, this method takes ~100 times longer than the non-recursive method above.

library(sets)

An example with a vector.

v <- (1:3)^2sv <- as.set(v)2^sv
{{}, {1}, {4}, {9}, {1, 4}, {1, 9}, {4, 9}, {1, 4, 9}}


An example with a list.

l <- list(a=1, b="qwerty", c=list(d=TRUE, e=1:3))sl <- as.set(l)2^sl
{{}, {1}, {"qwerty"}, {<<list(2)>>}, {1, <<list(2)>>}, {"qwerty",
1}, {"qwerty", <<list(2)>>}, {"qwerty", 1, <<list(2)>>}}


## Racket

 ;;; Direct translation of 'functional' ruby method(define (powerset s)  (for/fold ([outer-set (set(set))]) ([element s])    (set-union outer-set                (list->set (set-map outer-set                                   (λ(inner-set) (set-add inner-set element))))))) 

## Rascal

 import Set; public set[set[&T]] PowerSet(set[&T] s) = power(s); 

An example output:

 rascal>PowerSet({1,2,3,4})set[set[int]]: {  {4,3},  {4,2,1},  {4,3,1},  {4,2},  {4,3,2},  {4,1},  {4,3,2,1},  {4},  {3},  {2,1},  {3,1},  {2},  {3,2},  {1},  {3,2,1},  {}} 

## REXX

/*REXX program to display a power set, items may be anything (no blanks)*/parse arg S                               /*let user specify the set.   */if S=''  then S='one two three four'      /*None specified?  Use default*/N=words(S)                                /*number of items in the list.*/ps='{}'                                   /*start with a null power set.*/              do chunk=1  for N           /*traipse through the items.  */              ps=ps combN(N,chunk)        /*N items, a CHUNK at a time. */              end    /*chunk*/w=words(ps)              do k=1  for w               /*show combinations, one/line.*/              say right(k,length(w)) word(ps,k)              end    /*k*/exit                                      /*stick a fork in it, we done.*//*─────────────────────────────────────$COMBN subroutine────────────────*/combN: procedure expose$ S;     parse arg x,y;    $=!.=0; base=x+1; bbase=base-y; ym=y-1; do p=1 for y; !.p=p; end do j=1; L= do d=1 for y; _=!.d; L=L','word(S,_); end$=$'{'strip(L,'L',",")'}' !.y=!.y+1; if !.y==base then if .combU(ym) then leave end /*j*/return strip($)                           /*return with partial powerset*/ .combU: procedure expose !. y bbase;   parse arg d;  if d==0 then return 1p=!.d;    do u=d  to y;    !.u=p+1          if !.u==bbase+u  then return .combU(u-1)          p=!.u          end   /*u*/return 0

output when using the default input:

 1 {}
2 {one}
3 {two}
4 {three}
5 {four}
6 {one,two}
7 {one,three}
8 {one,four}
9 {two,three}
10 {two,four}
11 {three,four}
12 {one,two,three}
13 {one,two,four}
14 {one,three,four}
15 {two,three,four}
16 {one,two,three,four}


## Ruby

# Based on http://johncarrino.net/blog/2006/08/11/powerset-in-ruby/ # See the link if you want a shorter version. This was intended to show the reader how the method works. class Array  # Adds a power_set method to every array, i.e.: [1, 2].power_set  def power_set     # Injects into a blank array of arrays.    # acc is what we're injecting into    # you is each element of the array    inject([[]]) do |acc, you|      ret = []             # Set up a new array to add into      acc.each do |i|      # For each array in the injected array,        ret << i           # Add itself into the new array        ret << i + [you]   # Merge the array with a new array of the current element      end      ret       # Return the array we're looking at to inject more.    end   end   # A more functional and even clearer variant.  def func_power_set    inject([[]]) { |ps,item|    # for each item in the Array      ps +                      # take the powerset up to now and add      ps.map { |e| e + [item] } # it again, with the item appended to each element    }  endend #A direct translation of the "power array" version aboverequire 'set'class Set  def powerset     inject(Set[Set[]]) do |ps, item|       ps.union ps.map {|e| e.union (Set.new [item])}    end  endend p [1,2,3,4].power_setp %w(one two three).func_power_set p Set[1,2,3].powerset
Output:
[[], [4], [3], [3, 4], [2], [2, 4], [2, 3], [2, 3, 4], [1], [1, 4], [1, 3], [1, 3, 4], [1, 2], [1, 2, 4], [1, 2, 3], [1, 2, 3, 4]]
[[], ["one"], ["two"], ["one", "two"], ["three"], ["one", "three"], ["two", "three"], ["one", "two", "three"]]
#<Set: {#<Set: {}>, #<Set: {1}>, #<Set: {2}>, #<Set: {1, 2}>, #<Set: {3}>, #<Set: {1, 3}>, #<Set: {2, 3}>, #<Set: {1, 2, 3}>}>


## SAS

 options mprint mlogic symbolgen source source2; %macro SubSets (FieldCount = );data _NULL_;	Fields = &FieldCount;	SubSets = 2**Fields;	call symput ("NumSubSets", SubSets);run; %put &NumSubSets; data inital;	%do j = 1 %to &FieldCount;		F&j. = 1;	%end;run; data SubSets;	set inital;	RowCount =_n_;	call symput("SetCount",RowCount);run; %put SetCount ; %do %while (&SetCount < &NumSubSets); data loop;	%do j=1 %to &FieldCount;		if rand('GAUSSIAN') > rand('GAUSSIAN') then F&j. = 1;	%end; data SubSets_  ;set SubSets loop;run; proc sort data=SubSets_  nodupkey;	by F1 - F&FieldCount.;run; data Subsets;	set SubSets_;	RowCount =_n_;run; proc sql noprint;	select max(RowCount) into :SetCount	from SubSets;quit;run;  %end;%Mend SubSets; 

You can then call the macro as:

 %SubSets(FieldCount = 5);	 

The output will be the dataset SUBSETS and will have a 5 columns F1, F2, F3, F4, F5 and 32 columns, one with each combination of 1 and missing values.

Output:

Obs	F1	F2	F3	F4	F5	RowCount
1	.	.	.	.	.	1
2	.	.	.	.	1	2
3	.	.	.	1	.	3
4	.	.	.	1	1	4
5	.	.	1	.	.	5
6	.	.	1	.	1	6
7	.	.	1	1	.	7
8	.	.	1	1	1	8
9	.	1	.	.	.	9
10	.	1	.	.	1	10
11	.	1	.	1	.	11
12	.	1	.	1	1	12
13	.	1	1	.	.	13
14	.	1	1	.	1	14
15	.	1	1	1	.	15
16	.	1	1	1	1	16
17	1	.	.	.	.	17
18	1	.	.	.	1	18
19	1	.	.	1	.	19
20	1	.	.	1	1	20
21	1	.	1	.	.	21
22	1	.	1	.	1	22
23	1	.	1	1	.	23
24	1	.	1	1	1	24
25	1	1	.	.	.	25
26	1	1	.	.	1	26
27	1	1	.	1	.	27
28	1	1	.	1	1	28
29	1	1	1	.	.	29
30	1	1	1	.	1	30
31	1	1	1	1	.	31
32	1	1	1	1	1	32


## Scala

def powerset[A](s: Set[A]) = s.foldLeft(Set(Set.empty[A])) { case (ss, el) => ss ++ ss.map(_ + el) }

Another option that produces lazy sequence of the sets:

def powerset[A](s: Set[A]) = (0 to s.size).map(s.toSeq.combinations(_)).reduce(_ ++ _).map(_.toSet)

## Scheme

Translation of: Common Lisp
(define (power-set set)  (if (null? set)      '(())      (let ((rest (power-set (cdr set))))        (append (map (lambda (element) (cons (car set) element))                     rest)                rest)))) (display (power-set (list 1 2 3)))(newline) (display (power-set (list "A" "C" "E")))(newline)

Output:

((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())
((A C E) (A C) (A E) (A) (C E) (C) (E) ())

Call/cc generation:
(define (power-set lst)  (define (iter yield)    (let recur ((a '()) (b lst))      (if (null? b) (set! yield		      (call-with-current-continuation			(lambda (resume)			  (set! iter resume)			  (yield a))))	(begin (recur (append a (list (car b))) (cdr b))	       (recur a (cdr b)))))     ;; signal end of generation    (yield 'end-of-seq))   (lambda () (call-with-current-continuation iter))) (define x (power-set '(1 2 3)))(let loop ((a (x)))  (if (eq? a 'end-of-seq) #f    (begin      (display a)      (newline)      (loop (x)))))
output
(1 2)(1 3)(1)(2 3)(2)(3)()
Iterative:
 (define (power_set_iter set)  (let loop ((res '(())) (s set))    (if (empty? s)        res        (loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s))))) 
Output:
 '((e d c b a)  (e d c b)  (e d c a)  (e d c)  (e d b a)  (e d b)  (e d a)  (e d)  (e c b a)  (e c b)  (e c a)  (e c)  (e b a)  (e b)  (e a)  (e)  (d c b a)  (d c b)  (d c a)  (d c)  (d b a)  (d b)  (d a)  (d)  (c b a)  (c b)  (c a)  (c)  (b a)  (b)  (a)  ()) 

## TXR

Translation of: Common Lisp

The power set function can be written concisely like this:

(defun power-set (s) (reduce-right   (op append (mapcar (op cons @@1) @2) @2)   s '(())))

A complete program which takes command line arguments and prints the power set in comma-separated brace notation:

@(do (defun power-set (s)       (reduce-right           (op append (mapcar (op cons @@1) @2) @2)         s '(())))) @(bind pset @(power-set *args*))@(output)@  (repeat){@(rep)@pset, @(last)@pset@(empty)@(end)}@  (end)@(end)
$txr rosetta/power-set.txr 1 2 3 {1, 2, 3} {1, 2} {1, 3} {1} {2, 3} {2} {3} {} What is not obvious is that the above power-set function generalizes to strings and vectors. @(do (defun power-set (s) (reduce-right (op append (mapcar (op cons @@1) @2) @2) s '(()))) (prinl (power-set "abc")) (prinl (power-set "")) (prinl (power-set #(1 2 3)))) txr power-set-generic.txr ((#\a #\b #\c) (#\a #\b) (#\a #\c) (#\a) (#\b #\c) (#\b) (#\c) nil) ((nil) nil) ((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) nil) ## UnixPipes  | cat Aabc | cat A |\ xargs -n 1 ksh -c 'echo \{cat A\}' |\ xargs |\ sed -e 's; ;,;g' \ -e 's;^;echo ;g' \ -e 's;\},;}\\ ;g' |\ ksh |unfold wc -l A |\ xargs -n1 -I{} ksh -c 'echo {} |\ unfold 1 |sort -u |xargs' |sort -u aa ba b ca cbb cc  ## UNIX Shell From here p() { [$# -eq 0 ] && echo || (shift; p "$@") | while read r ; do echo -e "$1 $r\n$r"; done }

Usage

|p cat | sort | uniq                                                                        ACE^D

## Ursala

Sets are a built in type constructor in Ursala, represented as lexically sorted lists with duplicates removed. The powerset function is a standard library function, but could be defined as shown below.

powerset = ~&NiC+ ~&i&& ~&at^?\~&aNC ~&ahPfatPRXlNrCDrT

test program:

#cast %sSS test = powerset {'a','b','c','d'}

output:

{
{},
{'a'},
{'a','b'},
{'a','b','c'},
{'a','b','c','d'},
{'a','b','d'},
{'a','c'},
{'a','c','d'},
{'a','d'},
{'b'},
{'b','c'},
{'b','c','d'},
{'b','d'},
{'c'},
{'c','d'},
{'d'}}

## V

V has a built in called powerlist

[A C E] powerlist=[[A C E] [A C] [A E] [A] [C E] [C] [E] []]

its implementation in std.v is (like joy)

[powerlist   [null?]   [unitlist]   [uncons]   [dup swapd [cons] map popd swoncat]    linrec]. 

## zkl

Using a combinations function, build the power set from combinations of 1,2,... items.

fcn pwerSet(list){  (0).pump(list.len(),List, Utils.Helpers.pickNFrom.fp1(list),     T(Void.Write,Void.Write) ) .append(list)}
Output:
foreach n in (5){
ps:=pwerSet((1).pump(n,List)); ps.println(" Size = ",ps.len());
}

L(L()) Size = 1
L(L(),L(1)) Size = 2
L(L(),L(1),L(2),L(1,2)) Size = 4
L(L(),L(1),L(2),L(3),L(1,2),L(1,3),L(2,3),L(1,2,3)) Size = 8
L(L(),L(1),L(2),L(3),L(4),L(1,2),L(1,3),L(1,4),L(2,3),L(2,4),
L(3,4),L(1,2,3),L(1,2,4),L(1,3,4),L(2,3,4),L(1,2,3,4)) Size = 16
`