Power set: Difference between revisions
m "header|F_sharp" -> "header|F Sharp" |
|||
Line 514: | Line 514: | ||
<code>[[], [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]]</code> |
<code>[[], [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]]</code> |
||
=={{header| |
=={{header|F Sharp|F#}}== |
||
almost exact copy of OCaml version |
almost exact copy of OCaml version |
||
<lang fsharp> |
<lang fsharp> |
Revision as of 12:24, 26 April 2010
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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 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 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}}.
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]]
F#
almost exact copy of OCaml version <lang fsharp> let subsets xs = List.foldBack (fun x rest -> rest @ List.map (fun ys -> x::ys) rest) xs [[]] </lang>
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}}
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
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 2n - 1. If the kth bit in the binary string is 1, the kth 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
<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>
Prolog
<lang prolog> %powerset(Lst, PLst). addhead(Hd,Lst,Res):-
Res = [Hd |Lst].
head([H|_],H). tail([_|T],T).
powerset([], [[]]). powerset(Lst, PLst):-
head(Lst,Hd), tail(Lst,Tl), powerset(Tl,Rest), maplist(addhead(Hd), Rest, Ans), append(Rest, Ans, PLst).
e.g powerset([1,2,3,4], R), write_term(R, [max_depth(100)]). [[],
[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]]
</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
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
<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
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>
UnixPipes
<lang ksh> | cat A a b c
| 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
a a b a b c a c b b c c </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] linrec].
</lang>