Power set

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 2^S, is the set of all subsets of S.
Task : By using a library or build-in set type, or defining a set type with necessary operations, write a function with a set S as input that yields a power set 2^S 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}}.

Ada

<lang ada>with Ada.Text_IO; use Ada.Text_IO;

procedure Power_Set is

  type Universe is (A,B,C,D,E);

  -- The type Set are subsets of Universe
  type Set is array (Universe) of Boolean;
  Empty : constant Set := (others => False);
  function Cardinality (X : Set) return Natural is
     N : Natural := 0;
  begin
     for I in X'Range loop
        if X (I) then
           N := N + 1;
        end if;
     end loop;
     return N;
  end Cardinality;
  function Element (X : Set; Position : Positive) return Universe is
     N : Natural := 0;
  begin
     for I in X'Range loop
        if X (I) then
           N := N + 1;
           if N = Position then
              return I;
           end if;
        end if;
     end loop;
     raise Constraint_Error;
  end Element;
  procedure Put (X : Set) is
     Empty : Boolean := True;
  begin
     for I in X'Range loop
        if X (I) then
           if Empty then
              Empty := False;
              Put (Universe'Image (I));
           else
              Put ("," & Universe'Image (I));
           end if;
        end if;
     end loop;
     if Empty then
        Put ("empty");
     end if;
  end Put;

  -- Set_Of_Set are sets of subsets of Universe
  type Set_Of_Sets is array (Positive range <>) of Set;

  function Power (X : Set) return Set_Of_Sets is
     Length : constant Natural := Cardinality (X);
     Index  : array (1..Length) of Integer := (others => 0);
     Result : Set_Of_Sets (1..2**Length)   := (others => Empty);
  begin
     for N in Result'Range loop
        for I in 1..Length loop -- Index determines the sample N
           exit when Index (I) = 0;
           Result (N) (Element (X, Index (I))) := True;
        end loop;
 Next : for I in 1..Length loop -- Computing the index of the following sample
           if Index (I) < Length then
              Index (I) := Index (I) + 1;
              if I = 1 or else Index (I - 1) > Index (I) then
                 for J in reverse 2..I loop
                    Index (J - 1) := Index (J) + 1;
                 end loop;
                 exit Next;
              end if;
           end if;
        end loop Next;
     end loop;
     return Result;
  end Power;

  P : Set_Of_Sets := Power ((A|C|E => True, others => False));

begin

  for I in P'Range loop
     New_Line;
     Put (P (I));
  end loop;

end Power_Set;</lang> This example computes the power set of {A,C,E}. Sample output:

empty
A
C
E
A,C
A,E
C,E
A,C,E

ALGOL 68

Requires: ALGOL 68g mk14.1+ <lang algol68>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

);</lang> Example: <lang algol68>[][]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</lang> Output: <lang algol68>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);</lang>

AutoHotkey

ahk discussion <lang autohotkey>a = 1,a,-- ; elements separated by commas StringSplit 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),",}","}")</lang>

C

<lang c>#include <stdio.h>

include <stdlib.h>

typedef const char *SetType; typedef int bool;

typedef struct setStruct {

   int	    count;
   SetType *elements;
   void   (*printer)(SetType );
   bool    nlAfterElements;

} *Set;

/* Could probly use same struct as above for this */ typedef struct powerSetStruct {

   int     count;
   Set	    *elements;
   void    (*printer)(Set);
   bool    nlAfterElements;

} *PowerSet;

void PrintSet( Set s);

PowerSet GetPowerSet( Set set) {

   int ix, n, j;
   int max = 1<<set->count;		// Assuming count < 32

   PowerSet ps = (PowerSet)malloc( sizeof(struct powerSetStruct));

   if (ps) {
       ps->elements = (Set*)malloc( max*sizeof(Set));
       ps->count = max;
       ps->printer = PrintSet;
       ps->nlAfterElements = 1;

       for (ix=0; ix<max; ix++) {
           int setsize = 0;
           Set se = (Set)malloc(sizeof(struct setStruct));

           for (j=0; j<set->count; j++) 
               if (ix & (1<<j)) setsize++;
           if (setsize > 0) {
               se->elements = (SetType *)malloc(setsize *sizeof(SetType));
               n = 0;
               for (j=0; j<set->count; j++) {
                   if (ix & (1<<j)) {
                       se->elements[n] = set->elements[j];
                       n++;
                   }
               }
           }
           else {
               printf("No elements in set %d\n", ix);
               se->elements = NULL;
           }
           se->count = setsize;
           se->printer = set->printer;
           se->nlAfterElements = set->nlAfterElements;
           ps->elements[ix] = se;
       }
   }
   return ps;

}

void PrintSet( Set s) {

   const char *sep = "";
   int ix;
   printf("{");
   for (ix=0; ix<s->count; ix++) {
       printf("%s ", sep); 
       s->printer(s->elements[ix]);		
       sep = (s->nlAfterElements)? ",\n " :",";
   }
   printf(" }");

}

void PrintString( const char *str) {

   printf("%s", str);

}

int main() {

   const char *eles[] = {"Red","Grn","Blu","Ylo"};
   struct setStruct aSet = { 4, eles, PrintString, 0 };
   PowerSet p = GetPowerSet( &aSet);

   PrintSet(&aSet); printf("\n");
   PrintSet( (Set)p ); printf("\n");
   return 0;

}</lang> Output:

{ Red, Grn, Blu, Ylo }
{ {  },
  { Red },
  { Grn },
  { Red, Grn },
  { Blu },
  { Red, Blu },
  { Grn, Blu },
  { Red, Grn, Blu },
  { Ylo },
  { Red, Ylo },
  { Grn, Ylo },
  { Red, Grn, Ylo },
  { Blu, Ylo },
  { Red, Blu, Ylo },
  { Grn, Blu, Ylo },
  { Red, Grn, Blu, Ylo }}

C++

<lang cpp>#include <iostream>

include <set>
include <vector>
include <iterator>

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";
 }

}</lang>

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 }

Common Lisp

<lang lisp>(defun power-set (s)

 (reduce #'(lambda (item ps)
             (append (mapcar #'(lambda (e) (cons item e))
                             ps)
                     ps))
         s
         :from-end t
         :initial-value '(())))</lang>

Output:

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

Alternate, more recursive (same output): <lang lisp>(defun powerset (l)

 (if (null l)
     (list nil)
     (let ((prev (powerset (cdr l))))

(append (mapcar #'(lambda (elt) (cons (car l) elt)) prev) prev))))</lang>

D

Implements an (incomplete) immutable set type mimic python's frozenset, then the powset function is defined. <lang d>module powset ; import std.stdio, std.format : fmx = format ;

class Set(T) {

 alias Set!(T) Z ;
 alias bool[T] S ; 
 private const S set ;
 private const size_t len ;
 private const hash_t hash ;
 private T[] memberList ;
 static Z emptySet() { return new Z ; }
 this() { this(cast(T[])null) ; }
 this(T k) { this([k]) ; }
 this(T[] k) { 
   S mset ; 
   foreach(e ; k) mset[e] = true ; 
   set = mset ; 
   memberList = set.keys.sort ;
   len = set.length ;
   hash_t h ;
   foreach(e ; memberList)
     h = h*0xfff1 + typeid(T).getHash(&e) ;
   hash = h ;
 }
 Z dup() { return new Z(memberList) ; }
 alias add opCat ;
 Z add(T k) { return new Z(memberList ~ k) ; }
 Z add(T[] k) { return new Z(memberList ~ k) ; }
 Z add(Z k) { return new Z(memberList ~ k.members) ; }
 alias contains opIn_r;
 bool contains(T k) { return (k in set)||false ; }
 bool isEmpty() { return len == 0 ; }
 T[] members() { return memberList.dup ; }
 size_t length() { return len ; }
 hash_t toHash() { return hash ; }
 string toString() { return fmx("<%s>", fmx("%s", memberList)[1..$-1]) ; } 
 private Z toZ(Object o) { 
   auto c = cast(Z) o ;
   if(c is null) throw new Exception("Compare to different type") ;
   return c ;
 }
 int opEquals(Object rhs) { return hash == toZ(rhs).toHash ;  }
 // opCmp only for sort, should not be equivalent <= to subsetof
 int opCmp(Object rhs) { return len - toZ(rhs).length ;  }
 int opApply(int delegate(inout T) dg) {
   foreach(e ; memberList) if(dg(e)) break ;
   return 1 ;
 }

}

Set!(Set!(T)) powSet(T)(Set!(T) set) {

   Set!(T)[] ps = [Set!(T).emptySet] ;
   foreach(e ; set)
     foreach(ss ; ps)
       ps ~= ss.add(e) ;
   return new Set!(Set!(T))(ps) ;

}

void main() {

 Set!(int) iset = new Set!(int)([2,1]) ;

 auto pset = powSet(iset) ;
 writefln(iset) ;
 writefln(pset) ;
 writefln("set is in its powset? ", iset in pset) ;
 writefln(powSet(pset)) ;

}</lang>

Short alternative version, using just arrays:

<lang d>import std.stdio: writefln;

T[][] powerset(T)(T[] s) {

   auto r = new T[][](1, 0);
   foreach (e; s) {
       T[][] rs;
       foreach (x; r)
           rs ~= x ~ [e];
       r ~= rs;
   }
   return r;

}

void main() {

   writefln(powerset([1, 2, 3]));

}</lang>

E

<lang 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)
   })
 }

}</lang>

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
    ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

<lang erlang>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)].</lang>

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

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. <lang groovy>def comb comb = { 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

}</lang>

Test program: <lang groovy>def vocalists = [ "C", "S", "N", "Y" ] as LinkedHashSet println "${vocalists}" println powerSet(vocalists)</lang>

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.

Haskell

<lang Haskell>import Data.Set import Control.Monad

powerset :: Ord a => Set a -> Set (Set a) powerset = fromList . fmap fromList . listPowerset . toList

listPowerset :: [a] -> [[a]] listPowerset = filterM (const [True, False])</lang> 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: <lang Haskell>powerset [] = [[]] powerset (head:tail) = acc ++ map (head:) acc where acc = powerset tail</lang> or <lang Haskell>powerset = foldr (\x acc -> acc ++ map (x:) acc) [[]]</lang> 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]]

J

There are a number of ways to generate a power set in J. Here's one: <lang j>ps =: #~2#:@i.@^#</lang> For example: <lang j> ps 'ACE'

E C CE A AE AC ACE</lang>

Testing that there are no repeated values can occur through either error-avoidance or boolean result: <lang j>nrv=: 3 : 'assert. y -: ~.y' allunique=: -: ~.</lang>

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. <lang java5>public static <T extends Comparable<? super T>> LinkedList<LinkedList<T>> powSet( LinkedList<T> A){ LinkedList<LinkedList<T>> ans= new LinkedList<LinkedList<T>>(); if(A.size() == 1){//if there's only one element, we know the answer ans.add(new LinkedList<T>());//empty set LinkedList<T> temp= new LinkedList<T>(); temp.add(A.peekFirst());//and the only element in the original set ans.add(temp); }else{ T first= A.removeFirst();//save the first element LinkedList<LinkedList<T>> partial= powSet(A);//recursion call for(LinkedList<T> subset: partial){//for each set in the partial set ans.add(subset);//add it to the answer LinkedList<T> temp= new LinkedList<T>(subset); temp.add(first);//add the saved element to it Collections.sort(temp);//sort that set ans.add(temp);//add the new set to the answer } } return ans; }</lang>

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 2ⁿ - 1. If the k^th bit in the binary string is 1, the k^th element of the original set is in this combination. <lang java5>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(Integer i= 0;i< ansSize;++i){ String bin= Integer.toString(i, 2); //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; }</lang>

JavaScript

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

Works with: SpiderMonkey

<lang javascript>function powerset(ary) {

   var ps = new Array(new Array());
   for (var i=0; i < ary.length; i++) {
       // we modify the ps array in the next loop,
       // so can't use the ps.length property directly in the loop condition.
       var current_length = ps.length;
       for (var j = 0; j < current_length; j++) {
           ps.push(ps[j].concat(ary[i]));
       }
   }
   return ps;

}

var res = powerset([1,2,3,4]);

load('json2.js'); print(JSON.stringify(res));</lang>

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

Logo

<lang logo>to powerset :set

 if empty? :set [output [[]]]
 localmake "rest powerset butfirst :set
 output sentence  map [sentence first :set ?] :rest  :rest

end

show powerset [1 2 3] [[1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []]</lang>

Lua

<lang 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 ret

end

--alternative, copied from the Python implementation function 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 ret

end </lang>

M4

<lang M4>define(`for',`ifelse($#,0,``$0,`ifelse(eval($2<=$3),1,`pushdef(`$1',$2)$4`'popdef(`$1')$0(`$1',incr($2),$3,`$4')')')')dnl define(`nth',`ifelse($1,1,$2,`nth(decr($1),shift(shift($@)))')')dnl define(`range',`for(`x',eval($1+2),eval($2+2),`nth(x,$@)`'ifelse(x,eval($2+2),`',`,')')')dnl define(`powerpart',`{range(2,incr($1),$@)}`'ifelse(incr($1),$#,`',`for(`x',eval($1+2),$#,`,powerpart(incr($1),ifelse(eval(2<=($1+1)),1,`range(2,incr($1),$@),')`'nth(x,$@)`'ifelse(eval((x+1)<=$#),1,`,range(incr(x),$#,$@)'))')')')dnl define(`powerset',`{powerpart(0,substr(`$1',1,eval(len(`$1')-2)))}')dnl dnl powerset(`{a,b,c}')</lang>

Output:

{{},{a},{a,b},{a,b,c},{a,c},{b},{b,c},{c}}

Mathematica

Built-in function that either gives all possible subsets, subsets with at most n elements, subsets with exactly n elements or subsets containing between n and m elements. Example of all subsets: <lang Mathematica>Subsets[{a, b, c}]</lang> gives: <lang Mathematica>{{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}</lang> Subsets[list, {n, Infinity}] gives all the subsets that have n elements or more.

Subsets[list, n] gives all the subsets that have at most n elements.

Subsets[list, {n}] gives all the subsets that have exactly n elements.

Subsets[list, {m,n}] gives all the subsets that have between m and n elements.

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.

<lang ocaml>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 *)</lang>

version for lists: <lang ocaml>let subsets xs = List.fold_right (fun x rest -> rest @ List.map (fun ys -> x::ys) rest) xs [[]]</lang>

Oz

Oz has a library for finite set constraints. Creating a power set is a trivial application of that: <lang oz>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}
 end

in

 {Inspect {Powerset [1 2 3 4]}}</lang>

A more convential implementation without finite set constaints: <lang oz>fun {Powerset2 Set}

  case Set of nil then [nil]
  [] H|T then
     Acc = {Powerset2 T}
  in
     {Append Acc {Map Acc fun {$ A} H|A end}}
  end

end</lang>

Perl

<lang perl>sub p{@_?map{$_,[$_[0],@$_]}p(@_[1..$#_]):[]}</lang> or <lang perl>use List::Util qw(reduce); sub powerset {

 @{ (reduce { [@$a, map([@$_, $b], @$a)] } [[]], @_) }

}</lang>

Python

<lang 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 statement

def 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))))</lang>

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 <lang python>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))</lang>

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) <lang python>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)) )</lang>

R

Library: sets

R does not have a definition of a set in the standard distribution. We need to use the sets package. <lang R>library(sets)</lang> An example with a vector. <lang R>v <- (1:3)^2 sv <- as.set(v) 2^sv</lang>

{{}, {1}, {4}, {9}, {1, 4}, {1, 9}, {4, 9}, {1, 4, 9}}

An example with a list. <lang R>l <- list(a=1, b="qwerty", c=list(d=TRUE, e=1:3)) sl <- as.set(l) 2^sl</lang>

{{}, {1}, {"qwerty"}, {<<list(2)>>}, {1, <<list(2)>>}, {"qwerty",
 1}, {"qwerty", <<list(2)>>}, {"qwerty", 1, <<list(2)>>}}

Ruby

<lang 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|
 
     # Set up a new array to add into
     ret = []
     
     # For each array in the injected array,
     acc.each do |i|
   
       # Add itself into the new array
       ret << i
       
       # Merge the array with a new array of the current element
       ret << i + [you]
     end
     
     # Return the array we're looking at to inject more.
     ret
   
   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
   }
 end

end</lang>

Scala

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

Scheme

Translation of: Common Lisp

<lang scheme>(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)</lang> 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) ())

Smalltalk

Works with: GNU Smalltalk

Code from Bonzini's blog

<lang smalltalk>Collection extend [

   power [
       ^(0 to: (1 bitShift: self size) - 1) readStream collect: [ :each || i |
           i := 0.
           self select: [ :elem | (each bitAt: (i := i + 1)) = 1 ] ]
   ]

].</lang>

<lang smalltalk>#(1 2 4) power do: [ :each |

   each asArray printNl ].

( 'A' 'C' 'E' ) power do: [ :each |

   each asArray printNl ].</lang>

Standard ML

version for lists: <lang sml>fun subsets xs = foldr (fn (x, rest) => rest @ map (fn ys => x::ys) rest) [[]] xs</lang>

Tcl

<lang tcl>proc subsets {l} {

   set res [list [list]]
   foreach e $l {
       foreach subset $res {lappend res [lappend subset $e]}
   }
   return $res

} puts [subsets {a b c d}]</lang> Output:

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

Binary Count Method

<lang tcl>proc powersetb set {

  set res {}
  for {set i 0} {$i < 2**[llength $set]} {incr i} {
     set pos -1
     set pset {}
     foreach el $set {
         if {$i & 1<<[incr pos]} {lappend pset $el}
     }
     lappend res $pset
  }
  return $res

}</lang>

UNIX Shell

From here <lang bash>p() { [ $# -eq 0 ] && echo || (shift; p "$@") | while read r ; do echo -e "$1 $r\n$r"; done }</lang> Usage <lang bash>|p `cat` | sort | uniq A C E ^D</lang>

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. The algorithm is to enumerate all binary numbers whose width matches the cardinality of the set, and mask a copy of the set against each. <lang Ursala>#import std

import nat

powerset = -<&@rFlSPS+ zipp0^*D/~& iota+ --<&>+ 0!*</lang> test program: <lang Ursala>#cast %sSS

test = powerset {'a','b','c','d'}</lang> 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 <lang v>[A C E] powerlist =[[A C E] [A C] [A E] [A] [C E] [C] [E] []]</lang>

its implementation in std.v is (like joy) <lang v>[powerlist

  [null?]
  [unitlist]
  [uncons]
  [dup swapd [cons] map popd swoncat]</lang>
   linrec].