Power set: Difference between revisions
(→{{header|Scala}}: reverse_::: used for speed improvemet) |
|||
Line 2: | Line 2: | ||
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. |
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 [[wp:Power_set|power set]] (or powerset) of S, written P(S), or 2<sup>S</sup>, is the set of all subsets of S.< |
Given a set S, the [[wp:Power_set|power set]] (or powerset) of S, written P(S), or 2<sup>S</sup>, is the set of all subsets of S.<p>'''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 2<sup>S</sup> of S.</p><p>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}}.</p> |
||
'''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 2<sup>S</sup> of S. |
|||
For a set which contains n elements, the corresponding power set has 2<sup>n</sup> elements, including the edge cases of [[wp:Empty_set|empty set]].<p>The power set of the empty set is the set which contains itself (2<sup>0</sup> = 1):</p> |
|||
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}}. |
|||
<math>\mathcal{P}</math>(<math>\varnothing</math>) = { <math>\varnothing</math> } |
|||
<p>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 (2<sup>1</sup> = 2):</p> |
|||
The power set of the empty set is the set which contains itself (2<sup>0</sup> = 1):<br /> |
|||
<math>\mathcal{P}</math>(<math>\varnothing</math>) = { <math>\varnothing</math> }<br /> |
|||
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 (2<sup>1</sup> = 2):<br /> |
|||
<math>\mathcal{P}</math>({<math>\varnothing</math>}) = { <math>\varnothing</math>, { <math>\varnothing</math> } } |
<math>\mathcal{P}</math>({<math>\varnothing</math>}) = { <math>\varnothing</math>, { <math>\varnothing</math> } } |
||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
{{incomplete|Ada|It shows no proof of the cases with empty sets.}}This solution prints the power set of words read from the command line.<lang ada>with Ada.Text_IO, Ada.Command_Line; |
|||
This solution prints the power set of words read from the command line. |
|||
<lang ada>with Ada.Text_IO, Ada.Command_Line; |
|||
procedure Power_Set is |
procedure Power_Set is |
||
Line 56: | Line 50: | ||
end loop; |
end loop; |
||
Print_All_Subsets(Set); -- do the work |
Print_All_Subsets(Set); -- do the work |
||
end Power_Set;</lang> |
end Power_Set;</lang>{{out}}<pre>>./power_set cat dog mouse |
||
{{out}} |
|||
<pre>>./power_set cat dog mouse |
|||
{ cat, dog, mouse } |
{ cat, dog, mouse } |
||
{ cat, dog } |
{ cat, dog } |
||
Line 74: | Line 64: | ||
{ 2 } |
{ 2 } |
||
{ }</pre> |
{ }</pre> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{incomplete|ALGOL 68|It shows no proof of the cases with empty sets.}}{{works with|ALGOL 68|Revision 1 - no extensions to language used}}{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of FORMATted transput}} |
|||
{{works with|ALGOL 68|Revision 1 - no extensions to language used}} |
|||
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}} |
|||
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of FORMATted transput}} |
|||
Requires: ALGOL 68g mk14.1+ |
Requires: ALGOL 68g mk14.1+<lang algol68>MODE MEMBER = INT; |
||
<lang algol68>MODE MEMBER = INT; |
|||
PROC power set = ([]MEMBER s)[][]MEMBER:( |
PROC power set = ([]MEMBER s)[][]MEMBER:( |
||
Line 108: | Line 93: | ||
printf(($"set["d"] = "$,member, repr set, set[member],$l$)) |
printf(($"set["d"] = "$,member, repr set, set[member],$l$)) |
||
OD |
OD |
||
)</lang> |
)</lang>{{out}}<pre>set[1] = (); |
||
Output: |
|||
<pre> |
|||
set[1] = (); |
|||
set[2] = (1); |
set[2] = (1); |
||
set[3] = (2); |
set[3] = (2); |
||
Line 118: | Line 100: | ||
set[6] = (1, 4); |
set[6] = (1, 4); |
||
set[7] = (2, 4); |
set[7] = (2, 4); |
||
set[8] = (1, 2, 4); |
set[8] = (1, 2, 4);</pre> |
||
</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
ahk [http://www.autohotkey.com/forum/viewtopic.php?t=44657&postdays=0&postorder=asc&start=147 discussion] |
{{incomplete|AutoHotkey|It shows no proof of the cases with empty sets.}}ahk [http://www.autohotkey.com/forum/viewtopic.php?t=44657&postdays=0&postorder=asc&start=147 discussion]<lang autohotkey>a = 1,a,-- ; elements separated by commas |
||
<lang autohotkey>a = 1,a,-- ; elements separated by commas |
|||
StringSplit a, a, `, ; a0 = #elements, a1,a2,... = elements of the set |
StringSplit a, a, `, ; a0 = #elements, a1,a2,... = elements of the set |
||
Line 134: | Line 113: | ||
} |
} |
||
MsgBox % RegExReplace(SubStr(t,1,StrLen(t)-1),",}","}")</lang> |
MsgBox % RegExReplace(SubStr(t,1,StrLen(t)-1),",}","}")</lang> |
||
=={{header|BBC BASIC}}== |
=={{header|BBC BASIC}}== |
||
The elements of a set are represented as the bits in an integer (hence the maximum size of set is 32). |
{{incomplete|BBC BASIC|It shows no proof of the cases with empty sets.}}The elements of a set are represented as the bits in an integer (hence the maximum size of set is 32).<lang bbcbasic> DIM list$(3) : list$() = "1", "2", "3", "4" |
||
<lang bbcbasic> DIM list$(3) : list$() = "1", "2", "3", "4" |
|||
PRINT FNpowerset(list$()) |
PRINT FNpowerset(list$()) |
||
END |
END |
||
Line 153: | Line 130: | ||
s$ += "}," |
s$ += "}," |
||
NEXT i% |
NEXT i% |
||
= LEFT$(s$) + "}"</lang> |
= LEFT$(s$) + "}"</lang>{{out}} |
||
{{},{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}} |
|||
'''Output:''' |
|||
<pre> |
|||
{{},{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}} |
|||
</pre> |
|||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
<lang bracmat>( ( powerset |
{{incomplete|Bracmat|It shows no proof of the cases with empty sets.}}<lang bracmat>( ( powerset |
||
= done todo first |
= done todo first |
||
. !arg:(?done.?todo) |
. !arg:(?done.?todo) |
||
Line 169: | Line 142: | ||
) |
) |
||
& out$(powerset$(.1 2 3 4)) |
& out$(powerset$(.1 2 3 4)) |
||
);</lang> |
);</lang>{{out}}<pre> 1 2 3 4 |
||
Output: |
|||
<pre> 1 2 3 4 |
|||
, 1 2 3 |
, 1 2 3 |
||
, 1 2 4 |
, 1 2 4 |
||
Line 187: | Line 158: | ||
, 4 |
, 4 |
||
,</pre> |
,</pre> |
||
=={{header|Burlesque}}== |
=={{header|Burlesque}}== |
||
{{incomplete|Burlesque|It shows no proof of the cases with empty sets.}}<lang 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}}</lang> |
|||
<lang 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}} |
|||
</lang> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
<lang c>#include <stdio.h> |
{{incomplete|C|It shows no proof of the cases with empty sets.}}<lang c>#include <stdio.h> |
||
struct node { |
struct node { |
||
Line 226: | Line 193: | ||
powerset(argv + 1, argc - 1, 0); |
powerset(argv + 1, argc - 1, 0); |
||
return 0; |
return 0; |
||
}</lang> |
}</lang>{{out}}<pre>% ./a.out 1 2 3 |
||
{{out}} |
|||
<pre> |
|||
% ./a.out 1 2 3 |
|||
[ ] |
[ ] |
||
[ 3 ] |
[ 3 ] |
||
Line 237: | Line 201: | ||
[ 3 1 ] |
[ 3 1 ] |
||
[ 2 1 ] |
[ 2 1 ] |
||
[ 3 2 1 ] |
[ 3 2 1 ]</pre> |
||
</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{incomplete|C++|It shows no proof of the cases with empty sets.}} |
|||
=== Non-recursive version === |
=== Non-recursive version === |
||
<lang cpp>#include <iostream> |
<lang cpp>#include <iostream> |
||
#include <set> |
#include <set> |
||
Line 321: | Line 282: | ||
std::cout << " }\n"; |
std::cout << " }\n"; |
||
} |
} |
||
}</lang> |
}</lang>{{out}}<pre> |
||
Output: |
|||
<pre> |
|||
{ } |
{ } |
||
{ 2 } |
{ 2 } |
||
Line 344: | Line 302: | ||
=== Recursive version === |
=== Recursive version === |
||
<lang cpp>#include <iostream> |
<lang cpp>#include <iostream> |
||
#include <set> |
#include <set> |
||
Line 369: | Line 326: | ||
{ |
{ |
||
return powerset(s, s.size()); |
return powerset(s, s.size()); |
||
}</lang> |
|||
} |
|||
</lang> |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
{{incomplete|C sharp|It shows no proof of the cases with empty sets.}}<lang csharp>public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list) |
|||
<lang csharp> |
|||
public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list) |
|||
{ |
{ |
||
return from m in Enumerable.Range(0, 1 << list.Count) |
return from m in Enumerable.Range(0, 1 << list.Count) |
||
Line 393: | Line 348: | ||
result.Select(subset => |
result.Select(subset => |
||
string.Join(",", subset.Select(clr => clr.ToString()).ToArray())).ToArray())); |
string.Join(",", subset.Select(clr => clr.ToString()).ToArray())).ToArray())); |
||
}</lang> |
|||
} |
|||
</lang> |
|||
Output: |
|||
<lang> |
|||
Red |
Red |
||
Green |
Green |
||
Line 415: | Line 364: | ||
Green,Blue,Yellow |
Green,Blue,Yellow |
||
Red,Green,Blue,Yellow |
Red,Green,Blue,Yellow |
||
</lang> |
|||
An alternative implementation for an arbitrary number of elements: |
An alternative implementation for an arbitrary number of elements: |
||
<lang csharp> public IEnumerable<IEnumerable<T>> GetPowerSet<T>(IEnumerable<T> input) { |
|||
<lang csharp> |
|||
public IEnumerable<IEnumerable<T>> GetPowerSet<T>(IEnumerable<T> input) { |
|||
var seed = new List<IEnumerable<T>>() { Enumerable.Empty<T>() } |
var seed = new List<IEnumerable<T>>() { Enumerable.Empty<T>() } |
||
as IEnumerable<IEnumerable<T>>; |
as IEnumerable<IEnumerable<T>>; |
||
Line 426: | Line 371: | ||
return input.Aggregate(seed, (a, b) => |
return input.Aggregate(seed, (a, b) => |
||
a.Concat(a.Select(x => x.Concat(new List<T>() { b })))); |
a.Concat(a.Select(x => x.Concat(new List<T>() { b })))); |
||
} |
}</lang> |
||
</lang> |
|||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
<lang Clojure>(use '[clojure.math.combinatorics :only [subsets] ]) |
<lang Clojure>(use '[clojure.math.combinatorics :only [subsets] ]) |
||
Line 447: | Line 390: | ||
(powerset #{1 2 3})</lang> |
(powerset #{1 2 3})</lang> |
||
#{#{} #{1} #{2} #{1 2} #{3} #{1 3} #{2 3} #{1 2 3}} |
|||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
{{incomplete|CoffeeScript|It shows no proof of the cases with empty sets.}}<lang coffeescript>print_power_set = (arr) -> |
|||
<lang coffeescript> |
|||
print_power_set = (arr) -> |
|||
console.log "POWER SET of #{arr}" |
console.log "POWER SET of #{arr}" |
||
for subset in power_set(arr) |
for subset in power_set(arr) |
||
Line 478: | Line 420: | ||
print_power_set [] |
print_power_set [] |
||
print_power_set [4, 2, 1] |
print_power_set [4, 2, 1] |
||
print_power_set ['dog', 'c', 'b', 'a'] |
print_power_set ['dog', 'c', 'b', 'a']</lang>{{out}}<pre>> coffee power_set.coffee |
||
</lang> |
|||
output |
|||
<lang> |
|||
> coffee power_set.coffee |
|||
POWER SET of |
POWER SET of |
||
[] |
[] |
||
Line 510: | Line 448: | ||
[ 'dog', 'c', 'a' ] |
[ 'dog', 'c', 'a' ] |
||
[ 'dog', 'c', 'b' ] |
[ 'dog', 'c', 'b' ] |
||
[ 'dog', 'c', 'b', 'a' ] |
[ 'dog', 'c', 'b', 'a' ]</pre> |
||
</lang> |
|||
=={{header|ColdFusion}}== |
=={{header|ColdFusion}}== |
||
{{incomplete|ColdFusion|It shows no proof of the cases with empty sets.}}Port from the [[#JavaScript|JavaScript]] version, compatible with ColdFusion 8+ or Railo 3+<lang javascript>public array function powerset(required array data) |
|||
Port from the [[#JavaScript|JavaScript]] version, compatible with ColdFusion 8+ or Railo 3+ |
|||
<lang javascript>public array function powerset(required array data) |
|||
{ |
{ |
||
var ps = [""]; |
var ps = [""]; |
||
Line 533: | Line 467: | ||
} |
} |
||
var res = powerset([1,2,3,4]);</lang> |
var res = powerset([1,2,3,4]);</lang>{{out}} |
||
["","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"] |
|||
Outputs: |
|||
<pre>["","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"]</pre> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
<lang lisp>(defun power-set (s) |
{{incomplete|Common Lisp|It shows no proof of the cases with empty sets.}}<lang lisp>(defun power-set (s) |
||
(reduce #'(lambda (item ps) |
(reduce #'(lambda (item ps) |
||
(append (mapcar #'(lambda (e) (cons item e)) |
(append (mapcar #'(lambda (e) (cons item e)) |
||
Line 546: | Line 477: | ||
s |
s |
||
:from-end t |
:from-end t |
||
:initial-value '(())))</lang> |
:initial-value '(())))</lang>{{out}} |
||
Output: |
|||
>(power-set '(1 2 3)) |
>(power-set '(1 2 3)) |
||
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) NIL) |
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) NIL) |
||
Alternate, more recursive (same output): |
Alternate, more recursive (same output): |
||
<lang lisp>(defun powerset (l) |
<lang lisp>(defun powerset (l) |
||
Line 559: | Line 487: | ||
(append (mapcar #'(lambda (elt) (cons (car l) elt)) prev) |
(append (mapcar #'(lambda (elt) (cons (car l) elt)) prev) |
||
prev))))</lang> |
prev))))</lang> |
||
Imperative-style using LOOP: |
Imperative-style using LOOP: |
||
<lang lisp>(defun powerset (xs) |
<lang lisp>(defun powerset (xs) |
||
Line 578: | Line 504: | ||
>(power-set '(1 2 3)) |
>(power-set '(1 2 3)) |
||
((1) (1 3) (1 2 3) (1 2) (2) (2 3) (3) NIL) |
((1) (1 3) (1 2 3) (1 2) (2) (2 3) (3) NIL) |
||
=={{header|D}}== |
=={{header|D}}== |
||
Version using just arrays (it assumes the input to contain distinct items): |
{{incomplete|D|It shows no proof of the cases with empty sets.}}Version using just arrays (it assumes the input to contain distinct items):<lang d>T[][] powerSet(T)(in T[] s) pure nothrow @safe { |
||
<lang d>T[][] powerSet(T)(in T[] s) pure nothrow @safe { |
|||
auto r = new typeof(return)(1, 0); |
auto r = new typeof(return)(1, 0); |
||
foreach (e; s) { |
foreach (e; s) { |
||
Line 596: | Line 520: | ||
[1, 2, 3].powerSet.writeln; |
[1, 2, 3].powerSet.writeln; |
||
}</lang> |
}</lang>{{out}} |
||
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] |
|||
{{out}} |
|||
<pre>[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]</pre> |
|||
===Lazy Version=== |
===Lazy Version=== |
||
Compile with -version=power_set2_main to run the main. |
Compile with -version=power_set2_main to run the main. |
||
Line 638: | Line 560: | ||
[1, 2, 3].powerSet.writeln; |
[1, 2, 3].powerSet.writeln; |
||
} |
} |
||
}</lang> |
}</lang>Same output. |
||
Same output. |
|||
A [[Power_set/D|set implementation]] and its power set function. |
A [[Power_set/D|set implementation]] and its power set function. |
||
=={{header|Déjà Vu}}== |
=={{header|Déjà Vu}}== |
||
{{incomplete|Déjà Vu|It shows no proof of the cases with empty sets.}}In Déjà Vu, sets are dictionaries with all values <code>true</code> and the default set to <code>false</code>.<lang dejavu>powerset s: |
|||
In Déjà Vu, sets are dictionaries with all values <code>true</code> and the default set to <code>false</code>. |
|||
<lang dejavu>powerset s: |
|||
local :out [ set{ } ] |
local :out [ set{ } ] |
||
for value in keys s: |
for value in keys s: |
||
Line 656: | Line 573: | ||
out |
out |
||
!. powerset set{ 1 2 3 4 }</lang>{{out}}<pre>[ 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 } ]</pre> |
|||
!. powerset set{ 1 2 3 4 }</lang> |
|||
{{out}} |
|||
<pre>[ 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 } ]</pre> |
|||
=={{header|E}}== |
=={{header|E}}== |
||
{{incomplete|E|It shows no proof of the cases with empty sets.}}[[Category:E examples needing attention]]<lang e>pragma.enable("accumulator") |
|||
<lang e>pragma.enable("accumulator") |
|||
def powerset(s) { |
def powerset(s) { |
||
Line 671: | Line 583: | ||
}) |
}) |
||
} |
} |
||
}</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. |
|||
}</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. [[Category:E examples needing attention]] |
|||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
{{incomplete|Erlang|It shows no proof of the cases with empty sets.}} |
|||
Generates all subsets of a list with the help of binary |
{{out|Generates all subsets of a list with the help of binary}} |
||
<pre> |
<pre>For [1 2 3]: |
||
For [1 2 3]: |
|||
[ ] | 0 0 0 | 0 |
[ ] | 0 0 0 | 0 |
||
[ 3] | 0 0 1 | 1 |
[ 3] | 0 0 1 | 1 |
||
Line 688: | Line 596: | ||
[1 2 ] | 1 1 0 | 6 |
[1 2 ] | 1 1 0 | 6 |
||
[1 2 3] | 1 1 1 | 7 |
[1 2 3] | 1 1 1 | 7 |
||
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ |
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯</pre><lang erlang>powerset(Lst) -> |
||
</pre> |
|||
<lang erlang>powerset(Lst) -> |
|||
N = length(Lst), |
N = length(Lst), |
||
Max = trunc(math:pow(2,N)), |
Max = trunc(math:pow(2,N)), |
||
[[lists:nth(Pos+1,Lst) || Pos <- lists:seq(0,N-1), I band (1 bsl Pos) =/= 0] |
[[lists:nth(Pos+1,Lst) || Pos <- lists:seq(0,N-1), I band (1 bsl Pos) =/= 0] |
||
|| I <- lists:seq(0,Max-1)].</lang>{{out|Which outputs}}<pre>[[], [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]]</pre>Alternate shorter and more efficient version:<lang erlang>powerset([]) -> [[]]; |
|||
|| I <- lists:seq(0,Max-1)].</lang> |
|||
Which outputs: |
|||
<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> |
|||
Alternate shorter and more efficient version: |
|||
<lang erlang>powerset([]) -> [[]]; |
|||
powerset([H|T]) -> PT = powerset(T), |
powerset([H|T]) -> PT = powerset(T), |
||
[ [H|X] || X <- PT ] ++ PT.</lang> |
[ [H|X] || X <- PT ] ++ PT.</lang>or even more efficient version:<lang erlang>powerset([]) -> [[]]; |
||
or even more efficient version: |
|||
<lang erlang>powerset([]) -> [[]]; |
|||
powerset([H|T]) -> PT = powerset(T), |
powerset([H|T]) -> PT = powerset(T), |
||
powerset(H, PT, PT). |
powerset(H, PT, PT). |
||
Line 711: | Line 608: | ||
powerset(_, [], Acc) -> Acc; |
powerset(_, [], Acc) -> Acc; |
||
powerset(X, [H|T], Acc) -> powerset(X, T, [[X|H]|Acc]).</lang> |
powerset(X, [H|T], Acc) -> powerset(X, T, [[X|H]|Acc]).</lang> |
||
=={{header|F Sharp|F#}}== |
=={{header|F Sharp|F#}}== |
||
almost exact copy of OCaml version |
{{incomplete|F Sharp|It shows no proof of the cases with empty sets.}}almost exact copy of OCaml version |
||
<lang fsharp> |
<lang fsharp> |
||
let subsets xs = List.foldBack (fun x rest -> rest @ List.map (fun ys -> x::ys) rest) xs [[]] |
let subsets xs = List.foldBack (fun x rest -> rest @ List.map (fun ys -> x::ys) rest) xs [[]]</lang>alternatively with list comprehension<lang fsharp>let rec pow = |
||
</lang> |
|||
alternatively with list comprehension |
|||
<lang fsharp> |
|||
let rec pow = |
|||
function |
function |
||
| [] -> [[]] |
| [] -> [[]] |
||
| x::xs -> [for i in pow xs do yield! [i;x::i]] |
| x::xs -> [for i in pow xs do yield! [i;x::i]]</lang> |
||
</lang> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
We use hash sets, denoted by <code>HS{ }</code> brackets, for our sets. <code>members</code> converts from a set to a sequence, and <code><hash-set></code> converts back. |
{{incomplete|Factor|It shows no proof of the cases with empty sets.}}We use hash sets, denoted by <code>HS{ }</code> brackets, for our sets. <code>members</code> converts from a set to a sequence, and <code><hash-set></code> converts back.<lang factor>USING: kernel prettyprint sequences arrays sets hash-sets ; |
||
<lang factor>USING: kernel prettyprint sequences arrays sets hash-sets ; |
|||
IN: powerset |
IN: powerset |
||
: add ( set elt -- newset ) 1array <hash-set> union ; |
: add ( set elt -- newset ) 1array <hash-set> union ; |
||
: powerset ( set -- newset ) members { HS{ } } [ dupd [ add ] curry map append ] reduce <hash-set> ;</lang> |
: powerset ( set -- newset ) members { HS{ } } [ dupd [ add ] curry map append ] reduce <hash-set> ;</lang>{{out|Usage}}<pre>( scratchpad ) HS{ 1 2 3 4 } powerset . |
||
Usage: |
|||
<lang factor>( scratchpad ) HS{ 1 2 3 4 } powerset . |
|||
HS{ |
HS{ |
||
HS{ 1 2 3 4 } |
HS{ 1 2 3 4 } |
||
Line 753: | Line 638: | ||
HS{ 1 3 4 } |
HS{ 1 3 4 } |
||
HS{ 2 3 4 } |
HS{ 2 3 4 } |
||
}</ |
}</pre> |
||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
{{incomplete|Forth|It shows no proof of the cases with empty sets.}}{{works with|4tH|3.61.0}}.{{trans|C}}<lang forth>: ?print dup 1 and if over args type space then ; |
|||
{{works with|4tH|3.61.0}}. |
|||
{{trans|C}} |
|||
<lang forth>: ?print dup 1 and if over args type space then ; |
|||
: .set begin dup while ?print >r 1+ r> 1 rshift repeat drop drop ; |
: .set begin dup while ?print >r 1+ r> 1 rshift repeat drop drop ; |
||
: .powerset 0 do ." ( " 1 i .set ." )" cr loop ; |
: .powerset 0 do ." ( " 1 i .set ." )" cr loop ; |
||
Line 765: | Line 647: | ||
: powerset 1 argn check-none check-size 1- lshift .powerset ; |
: powerset 1 argn check-none check-size 1- lshift .powerset ; |
||
powerset</lang> |
powerset</lang>{{out}}<pre>$ 4th cxq powerset.4th 1 2 3 4 |
||
Output: |
|||
<pre> |
|||
$ 4th cxq powerset.4th 1 2 3 4 |
|||
( ) |
( ) |
||
( 1 ) |
( 1 ) |
||
Line 784: | Line 663: | ||
( 1 3 4 ) |
( 1 3 4 ) |
||
( 2 3 4 ) |
( 2 3 4 ) |
||
( 1 2 3 4 ) |
( 1 2 3 4 )</pre> |
||
</pre> |
|||
=={{header|Frink}}== |
=={{header|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. |
{{incomplete|Frink|It shows no proof of the cases with empty sets.}}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.<lang frink> |
||
<lang frink> |
|||
a = new set[1,2,3,4] |
a = new set[1,2,3,4] |
||
a.subsets[] |
a.subsets[]</lang> |
||
</lang> |
|||
=={{header|FunL}}== |
=={{header|FunL}}== |
||
FunL uses Scala type <code>scala.collection.immutable.Set</code> as it's set type, which has a built-in method <code>subsets</code> returning an (Scala) iterator over subsets. |
FunL uses Scala type <code>scala.collection.immutable.Set</code> as it's set type, which has a built-in method <code>subsets</code> returning an (Scala) iterator over subsets.<lang funl>def powerset( s ) = s.subsets().toSet()</lang> |
||
The powerset function could be implemented in FunL directly as:<lang funl>def |
|||
<lang funl>def powerset( s ) = s.subsets().toSet()</lang> |
|||
The powerset function could be implemented in FunL directly as: |
|||
<lang funl>def |
|||
powerset( {} ) = {{}} |
powerset( {} ) = {{}} |
||
powerset( s ) = |
powerset( s ) = |
||
Line 813: | Line 683: | ||
def powerset( s ) = foldr( \x, acc -> acc + map( a -> {x} + a, acc), {{}}, s ) |
def powerset( s ) = foldr( \x, acc -> acc + map( a -> {x} + a, acc), {{}}, s ) |
||
println( powerset({1, 2, 3, 4}) )</lang> |
println( powerset({1, 2, 3, 4}) )</lang>{{out}} |
||
{{}, {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}} |
|||
{{out}} |
|||
<pre> |
|||
{{}, {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}} |
|||
</pre> |
|||
=={{header|GAP}}== |
=={{header|GAP}}== |
||
<lang gap># Built-in |
{{incomplete|GAP|It shows no proof of the cases with empty sets.}}<lang gap># Built-in |
||
Combinations([1, 2, 3]); |
Combinations([1, 2, 3]); |
||
# [ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 2, 3 ], [ 3 ] ] |
# [ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 2, 3 ], [ 3 ] ] |
||
Line 830: | Line 694: | ||
# [ [ ], [ 1 ], [ 1, 1 ], [ 1, 1, 2 ], [ 1, 1, 2, 3 ], [ 1, 1, 3 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ], |
# [ [ ], [ 1 ], [ 1, 1 ], [ 1, 1, 2 ], [ 1, 1, 2, 3 ], [ 1, 1, 3 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ], |
||
# [ 2 ], [ 2, 3 ], [ 3 ] ]</lang> |
# [ 2 ], [ 2, 3 ], [ 3 ] ]</lang> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
No native set type in Go. |
{{incomplete|Go|It shows no proof of the cases with empty sets.}}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 |
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. |
||
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 |
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. |
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. |
||
<lang go>package main |
<lang go>package main |
||
Line 947: | Line 809: | ||
fmt.Println(ps) |
fmt.Println(ps) |
||
fmt.Println("length =", len(ps)) |
fmt.Println("length =", len(ps)) |
||
}</lang> |
}</lang>{{out}}<pre>{1 2 3 4} |
||
{{out}} |
|||
<pre> |
|||
{1 2 3 4} |
|||
length = 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}} |
{{} {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 |
length = 16</pre> |
||
</pre> |
|||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
Builds on the [[Combinations#Groovy|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'''. |
{{incomplete|Groovy|It shows no proof of the cases with empty sets.}}Builds on the [[Combinations#Groovy|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 |
||
<lang groovy>def comb |
|||
comb = { m, List list -> |
comb = { m, List list -> |
||
def n = list.size() |
def n = list.size() |
||
Line 971: | Line 828: | ||
def powerSet = { set -> |
def powerSet = { set -> |
||
(0..(set.size())).inject([]){ list, i -> list + comb(i,set as List)}.collect { it as LinkedHashSet } as LinkedHashSet |
(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 |
|||
}</lang> |
|||
Test program: |
|||
<lang groovy>def vocalists = [ "C", "S", "N", "Y" ] as LinkedHashSet |
|||
println "${vocalists}" |
println "${vocalists}" |
||
println powerSet(vocalists)</lang> |
println powerSet(vocalists)</lang> |
||
Line 985: | Line 839: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
<lang Haskell>import Data.Set |
{{incomplete|Haskell|It shows no proof of the cases with empty sets.}}<lang Haskell>import Data.Set |
||
import Control.Monad |
import Control.Monad |
||
Line 992: | Line 846: | ||
listPowerset :: [a] -> [[a]] |
listPowerset :: [a] -> [[a]] |
||
listPowerset = filterM (const [True, False])</lang><tt>listPowerset</tt> describes the result as all possible (using the list monad) filterings (using <tt>filterM</tt>) of the input list, regardless (using <tt>const</tt>) of each item's value. <tt>powerset</tt> simply converts the input and output from lists to sets. |
|||
listPowerset = filterM (const [True, False])</lang> |
|||
<tt>listPowerset</tt> describes the result as all possible (using the list monad) filterings (using <tt>filterM</tt>) of the input list, regardless (using <tt>const</tt>) of each item's value. <tt>powerset</tt> simply converts the input and output from lists to sets. |
|||
'''Alternate Solution''' |
'''Alternate Solution''' |
||
<lang Haskell>powerset [] = [[]] |
<lang Haskell>powerset [] = [[]] |
||
powerset (head:tail) = acc ++ map (head:) acc where acc = powerset tail</lang> |
powerset (head:tail) = acc ++ map (head:) acc where acc = powerset tail</lang> or <lang Haskell>powerset = foldr (\x acc -> acc ++ map (x:) acc) [[]]</lang> |
||
or |
|||
<lang Haskell>powerset = foldr (\x acc -> acc ++ map (x:) acc) [[]]</lang> |
|||
Examples: |
Examples: |
||
Line 1,014: | Line 865: | ||
'''Alternate solution''' |
'''Alternate solution''' |
||
A method using only set operations and set mapping is also possible. Ideally, <code>Set</code> 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. |
A method using only set operations and set mapping is also possible. Ideally, <code>Set</code> 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.<lang Haskell>import qualified Data.Set as Set |
||
<lang Haskell>import qualified Data.Set as Set |
|||
type Set=Set.Set |
type Set=Set.Set |
||
unionAll :: (Ord a) => Set (Set a) -> Set a |
unionAll :: (Ord a) => Set (Set a) -> Set a |
||
Line 1,030: | Line 880: | ||
powerSet :: (Ord a) => Set a -> Set (Set a) |
powerSet :: (Ord a) => Set a -> Set (Set a) |
||
powerSet = (Set.fold (slift Set.union) (Set.singleton Set.empty)) . Set.map makeSet</lang> |
powerSet = (Set.fold (slift Set.union) (Set.singleton Set.empty)) . Set.map makeSet</lang> |
||
Usage |
{{out|Usage}} |
||
Prelude Data.Set> powerSet fromList [1,2,3] |
|||
<lang Haskell> |
|||
fromList [fromList [], fromList [1], fromList [1,2], fromList [1,2,3], fromList [1,3], fromList [2], fromList [2,3], fromList [3]] |
|||
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]]</lang> |
|||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
{{incomplete|Icon|It shows no proof of the cases with empty sets.}}{{incomplete|Unicon|It shows no proof of the cases with empty sets.}}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. |
|||
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=== |
===Set building=== |
||
The following version returns a set containing the powerset:<lang Icon>procedure power_set (s) |
|||
The following version returns a set containing the powerset: |
|||
<lang Icon> |
|||
procedure power_set (s) |
|||
result := set () |
result := set () |
||
if *s = 0 |
if *s = 0 |
||
Line 1,057: | Line 899: | ||
} |
} |
||
return result |
return result |
||
end</lang>To test the above procedure:<lang Icon>procedure main () |
|||
end |
|||
</lang> |
|||
To test the above procedure: |
|||
<lang Icon> |
|||
procedure main () |
|||
every s := !power_set (set(1,2,3,4)) do { # requires '!' to generate items in the result set |
every s := !power_set (set(1,2,3,4)) do { # requires '!' to generate items in the result set |
||
writes ("[ ") |
writes ("[ ") |
||
Line 1,069: | Line 905: | ||
write ("]") |
write ("]") |
||
} |
} |
||
end |
end</lang> |
||
</lang> |
|||
Output: |
Output: |
||
Line 1,091: | Line 926: | ||
[ 2 1 ] |
[ 2 1 ] |
||
</pre> |
</pre> |
||
===Generator=== |
===Generator=== |
||
An alternative version, which generates each item in the power set in turn:<lang Icon>procedure power_set (s) |
|||
An alternative version, which generates each item in the power set in turn: |
|||
<lang Icon> |
|||
procedure power_set (s) |
|||
if *s = 0 |
if *s = 0 |
||
then suspend set () |
then suspend set () |
||
Line 1,115: | Line 945: | ||
write ("]") |
write ("]") |
||
} |
} |
||
end |
end</lang> |
||
</lang> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
{{incomplete|J|It shows no proof of the cases with empty sets.}}There are a [http://www.jsoftware.com/jwiki/Essays/Power_Set number of ways] to generate a power set in J. Here's one: |
|||
There are a [http://www.jsoftware.com/jwiki/Essays/Power_Set number of ways] to generate a power set in J. Here's one: |
|||
<lang j>ps =: #~ 2 #:@i.@^ #</lang> |
<lang j>ps =: #~ 2 #:@i.@^ #</lang> |
||
For example: |
For example: |
||
Line 1,131: | Line 958: | ||
AE |
AE |
||
AC |
AC |
||
ACE</lang>In the typical use, this operation makes sense on collections of unique elements.<lang J> ~.1 2 3 2 1 |
|||
ACE</lang> |
|||
In the typical use, this operation makes sense on collections of unique elements. |
|||
<lang J> ~.1 2 3 2 1 |
|||
1 2 3 |
1 2 3 |
||
#ps 1 2 3 2 1 |
#ps 1 2 3 2 1 |
||
32 |
32 |
||
#ps ~.1 2 3 2 1 |
#ps ~.1 2 3 2 1 |
||
8</lang>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. |
|||
8</lang> |
|||
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. |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|1.5+}} |
{{incomplete|Java|It shows no proof of the cases with empty sets.}}{{works with|Java|1.5+}} |
||
===Recursion=== |
===Recursion=== |
||
[[Category:Recursion]] |
[[Category: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. |
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 ArrayList<String> getpowerset(int a[],int n,ArrayList<String> ps) |
||
<lang java5>public static ArrayList<String> getpowerset(int a[],int n,ArrayList<String> ps) |
|||
{ |
{ |
||
if(n<0) |
if(n<0) |
||
Line 1,174: | Line 993: | ||
return ps; |
return ps; |
||
}</lang> |
}</lang> |
||
===Iterative=== |
===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. |
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.<lang java5>public static <T> List<List<T>> powerset(Collection<T> list) { |
||
<lang java5> |
|||
public static <T> List<List<T>> powerset(Collection<T> list) { |
|||
List<List<T>> ps = new ArrayList<List<T>>(); |
List<List<T>> ps = new ArrayList<List<T>>(); |
||
ps.add(new ArrayList<T>()); // add the empty set |
ps.add(new ArrayList<T>()); // add the empty set |
||
Line 1,200: | Line 1,016: | ||
} |
} |
||
return ps; |
return ps; |
||
}</lang> |
|||
} |
|||
</lang> |
|||
===Binary String=== |
===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 <tt>n</tt> elements in the original set, each combination can be represented by a binary string of length <tt>n</tt>. To get all possible combinations, all you need is a counter from 0 to 2<sup>n</sup> - 1. If the k<sup>th</sup> bit in the binary string is 1, the k<sup>th</sup> element of the original set is in this combination. |
This implementation works on idea that each element in the original set can either be in the power set or not in it. With <tt>n</tt> elements in the original set, each combination can be represented by a binary string of length <tt>n</tt>. To get all possible combinations, all you need is a counter from 0 to 2<sup>n</sup> - 1. If the k<sup>th</sup> bit in the binary string is 1, the k<sup>th</sup> element of the original set is in this combination.<lang java5>public static <T extends Comparable<? super T>> LinkedList<LinkedList<T>> BinPowSet( |
||
<lang java5>public static <T extends Comparable<? super T>> LinkedList<LinkedList<T>> BinPowSet( |
|||
LinkedList<T> A){ |
LinkedList<T> A){ |
||
LinkedList<LinkedList<T>> ans= new LinkedList<LinkedList<T>>(); |
LinkedList<LinkedList<T>> ans= new LinkedList<LinkedList<T>>(); |
||
Line 1,221: | Line 1,034: | ||
return ans; |
return ans; |
||
}</lang> |
}</lang> |
||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
Uses a JSON stringifier from http://www.json.org/js.html |
{{incomplete|JavaScript|It shows no proof of the cases with empty sets.}}Uses a JSON stringifier from http://www.json.org/js.html{{works with|SpiderMonkey}}<lang javascript>function powerset(ary) { |
||
{{works with|SpiderMonkey}} |
|||
<lang javascript>function powerset(ary) { |
|||
var ps = [[]]; |
var ps = [[]]; |
||
for (var i=0; i < ary.length; i++) { |
for (var i=0; i < ary.length; i++) { |
||
Line 1,239: | Line 1,048: | ||
load('json2.js'); |
load('json2.js'); |
||
print(JSON.stringify(res));</lang> |
print(JSON.stringify(res));</lang>{{out}} |
||
[[],[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]] |
|||
Outputs: |
|||
<pre>[[],[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]]</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
<lang julia>function powerset (x) |
{{incomplete|Julia|It shows no proof of the cases with empty sets.}}<lang julia>function powerset (x) |
||
result = {{}} |
result = {{}} |
||
for i in x, j = 1:length(result) |
for i in x, j = 1:length(result) |
||
Line 1,251: | Line 1,057: | ||
end |
end |
||
result |
result |
||
end</lang> |
end</lang>{{Out}} |
||
julia> show(powerset({1,2,3})) |
|||
{{Out}} |
|||
{{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}} |
|||
<pre>julia> show(powerset({1,2,3})) |
|||
{{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}}</pre> |
|||
=={{header|K}}== |
=={{header|K}}== |
||
{{incomplete|K|It shows no proof of the cases with empty sets.}}<lang K> |
|||
<lang K> |
|||
ps:{x@&:'+2_vs!_2^#x} |
ps:{x@&:'+2_vs!_2^#x} |
||
</lang> |
</lang>Usage:<pre> |
||
Usage: |
|||
<lang K> |
|||
ps "ABC" |
ps "ABC" |
||
("" |
("" |
||
Line 1,270: | Line 1,072: | ||
"AC" |
"AC" |
||
"AB" |
"AB" |
||
"ABC") |
"ABC")</pre> |
||
</lang> |
|||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
<lang logo>to powerset :set |
{{incomplete|Logo|It shows no proof of the cases with empty sets.}}<lang logo>to powerset :set |
||
if empty? :set [output [[]]] |
if empty? :set [output [[]]] |
||
localmake "rest powerset butfirst :set |
localmake "rest powerset butfirst :set |
||
Line 1,284: | Line 1,084: | ||
=={{header|Logtalk}}== |
=={{header|Logtalk}}== |
||
<lang logtalk>:- object(set). |
{{incomplete|Logtalk|It shows no proof of the cases with empty sets.}}<lang logtalk>:- object(set). |
||
:- public(powerset/2). |
:- public(powerset/2). |
||
Line 1,314: | Line 1,114: | ||
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]] |
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</lang> |
yes</lang> |
||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
{{incomplete|Lua|It shows no proof of the cases with empty sets.}}<lang lua> |
|||
<lang lua> |
|||
--returns the powerset of s, out of order. |
--returns the powerset of s, out of order. |
||
function powerset(s, start) |
function powerset(s, start) |
||
Line 1,351: | Line 1,150: | ||
end |
end |
||
</lang> |
</lang> |
||
=={{header|M4}}== |
=={{header|M4}}== |
||
<lang M4>define(`for', |
{{incomplete|M4|It shows no proof of the cases with empty sets.}}<lang M4>define(`for', |
||
`ifelse($#, 0, ``$0'', |
`ifelse($#, 0, ``$0'', |
||
eval($2 <= $3), 1, |
eval($2 <= $3), 1, |
||
Line 1,375: | Line 1,173: | ||
dnl |
dnl |
||
powerset(`{a,b,c}')</lang> |
powerset(`{a,b,c}')</lang> |
||
{{},{a},{a,b},{a,b,c},{a,c},{b},{b,c},{c}} |
|||
Output: |
|||
<pre> |
|||
{{},{a},{a,b},{a,b,c},{a,c},{b},{b,c},{c}} |
|||
</pre> |
|||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
{{incomplete|Maple|It shows no proof of the cases with empty sets.}}<lang Maple>with(combinat): |
|||
<lang Maple> |
|||
with(combinat): |
|||
powerset({1,2,3,4}); |
powerset({1,2,3,4});</lang>{{out}} |
||
{{}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, |
|||
</lang> |
|||
Output: |
|||
<pre> |
|||
{{}, {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}} |
{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}} |
||
</pre> |
|||
=={{header|Mathematica}}== |
=={{header|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: |
{{incomplete|Mathematica|It shows no proof of the cases with empty sets.}}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> |
<lang Mathematica>Subsets[{a, b, c}]</lang>gives: |
||
{{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} |
|||
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. |
|||
=={{header|MATLAB}}== |
=={{header|MATLAB}}== |
||
Sets are not an explicit data type in MATLAB, but cell arrays can be used for the same purpose. In fact, cell arrays have the benefit of containing any kind of data structure. So, this powerset function will work on a set of any type of data structure, without the need to overload any operators.<lang MATLAB>function pset = powerset(theSet) |
|||
Sets are not an explicit data type in MATLAB, but cell arrays can be used for the same purpose. In fact, cell arrays have the benefit of containing any kind of data structure. So, this powerset function will work on a set of any type of data structure, without the need to overload any operators. |
|||
<lang MATLAB>function pset = powerset(theSet) |
|||
pset = cell(size(theSet)); %Preallocate memory |
pset = cell(size(theSet)); %Preallocate memory |
||
Line 1,432: | Line 1,206: | ||
Sample Usage: |
Sample Usage: |
||
Powerset of the set of the empty set. |
Powerset of the set of the empty set.<lang MATLAB>powerset({{}}) |
||
<lang MATLAB>powerset({{}}) |
|||
ans = |
ans = |
||
Line 1,445: | Line 1,218: | ||
{1x0 cell} {1x1 cell} {1x1 cell} {1x2 cell} %This is the same as { {},{{1,2}},{3},{{1,2},3} }</lang> |
{1x0 cell} {1x1 cell} {1x1 cell} {1x2 cell} %This is the same as { {},{{1,2}},{3},{{1,2},3} }</lang> |
||
=={{header|Maxima}}== |
=={{header|Maxima}}== |
||
<lang maxima>powerset({1, 2, 3, 4}); |
{{incomplete|Maxima|It shows no proof of the cases with empty sets.}}<lang maxima>powerset({1, 2, 3, 4}); |
||
/* {{}, {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {1, 2, 4}, {1, 3}, {1, 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}} */</lang> |
{1, 4}, {2}, {2, 3}, {2, 3, 4}, {2, 4}, {3}, {3, 4}, {4}} */</lang> |
||
=={{header|Nimrod}}== |
=={{header|Nimrod}}== |
||
<lang nimrod>import sets, hashes |
{{incomplete|Nimrod|It shows no proof of the cases with empty sets.}}<lang nimrod>import sets, hashes |
||
proc hash(x): THash = |
proc hash(x): THash = |
||
Line 1,471: | Line 1,242: | ||
echo powerset(toSet([1,2,3,4]))</lang> |
echo powerset(toSet([1,2,3,4]))</lang> |
||
=={{header|Objective-C}}== |
=={{header|Objective-C}}== |
||
<lang objc>#import <Foundation/Foundation.h> |
{{incomplete|Objective-C|It shows no proof of the cases with empty sets.}}<lang objc>#import <Foundation/Foundation.h> |
||
+ (NSArray *)powerSetForArray:(NSArray *)array { |
+ (NSArray *)powerSetForArray:(NSArray *)array { |
||
Line 1,489: | Line 1,259: | ||
return subsets; |
return subsets; |
||
}</lang> |
}</lang> |
||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
{{incomplete|OCaml|It shows no proof of the cases with empty sets.}}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) = |
|||
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 |
struct |
||
Line 1,510: | Line 1,276: | ||
;; |
;; |
||
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> |
|||
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> |
|||
=={{header|OPL}}== |
=={{header|OPL}}== |
||
{{incomplete|OPL|It shows no proof of the cases with empty sets.}}<lang OPL>{string} s={"A","B","C","D"}; |
|||
<lang OPL> |
|||
{string} s={"A","B","C","D"}; |
|||
range r=1.. ftoi(pow(2,card(s))); |
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)}; |
{string} s2 [k in r] = {i | i in s: ((k div (ftoi(pow(2,(ord(s,i))))) mod 2) == 1)}; |
||
Line 1,526: | Line 1,285: | ||
{ |
{ |
||
writeln(s2); |
writeln(s2); |
||
}</lang>{{out|which gives}} |
|||
} |
|||
[{} {"A"} {"B"} {"A" "B"} {"C"} {"A" "C"} {"B" "C"} {"A" "B" "C"} {"D"} {"A" |
|||
</lang> |
|||
which gives |
|||
<lang result> |
|||
[{} {"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"} |
"D"} {"B" "D"} {"A" "B" "D"} {"C" "D"} {"A" "C" "D"} {"B" "C" "D"} |
||
{"A" "B" "C" "D"}] |
{"A" "B" "C" "D"}] |
||
</lang> |
|||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
Oz has a library for finite set constraints. Creating a power set is a trivial application of that: |
{{incomplete|Oz|It shows no proof of the cases with empty sets.}}Oz has a library for finite set constraints. Creating a power set is a trivial application of that:<lang oz>declare |
||
<lang oz>declare |
|||
%% Given a set as a list, returns its powerset (again as a list) |
%% Given a set as a list, returns its powerset (again as a list) |
||
fun {Powerset Set} |
fun {Powerset Set} |
||
Line 1,560: | Line 1,305: | ||
end |
end |
||
in |
in |
||
{Inspect {Powerset [1 2 3 4]}}</lang> |
{Inspect {Powerset [1 2 3 4]}}</lang>A more convential implementation without finite set constaints: |
||
A more convential implementation without finite set constaints: |
|||
<lang oz>fun {Powerset2 Set} |
<lang oz>fun {Powerset2 Set} |
||
case Set of nil then [nil] |
case Set of nil then [nil] |
||
Line 1,573: | Line 1,316: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
<lang parigp>vector(1<<#S,i,vecextract(S,i-1))</lang> |
{{incomplete|PARI/GP|It shows no proof of the cases with empty sets.}}<lang parigp>vector(1<<#S,i,vecextract(S,i-1))</lang> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{incomplete|Perl|It shows no proof of the cases with empty sets.}}Perl does not have a built-in set data-type. However, you can... |
|||
Perl does not have a built-in set data-type. However, you can... |
|||
<ul> |
<ul> |
||
<li><p>'''''Use a third-party module'''''</p> |
<li><p>'''''Use a third-party module'''''</p> |
||
Line 1,599: | Line 1,341: | ||
Output: |
Output: |
||
<pre>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))</pre> |
<pre>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))</pre></li><li><p>'''''Use a simple custom hash-based set type'''''</p> |
||
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):<lang perl>package Set { |
|||
</li> |
|||
<li><p>'''''Use a simple custom hash-based set type'''''</p> |
|||
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): |
|||
<lang perl>package Set { |
|||
sub new { bless { map {$_ => undef} @_[1..$#_] }, shift; } |
sub new { bless { map {$_ => undef} @_[1..$#_] }, shift; } |
||
sub elements { sort keys %{shift()} } |
sub elements { sort keys %{shift()} } |
||
sub as_string { 'Set(' . join(' ', sort keys %{shift()}) . ')' } |
sub as_string { 'Set(' . join(' ', sort keys %{shift()}) . ')' } |
||
# ...more set methods could be defined here... |
# ...more set methods could be defined here... |
||
}</lang>''(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 [https://metacpan.org/pod/Set::Tiny Set::Tiny])'' |
|||
}</lang> |
|||
''(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 [https://metacpan.org/pod/Set::Tiny 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. |
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 <code>Set::Object</code> based solution above, but using list folding (with the help of Perl's <code>List::Util</code> core module) seems a little more elegant in this case: |
We could implement the function as an imperative foreach loop similar to the <code>Set::Object</code> based solution above, but using list folding (with the help of Perl's <code>List::Util</code> core module) seems a little more elegant in this case:<lang perl>use List::Util qw(reduce); |
||
<lang perl>use List::Util qw(reduce); |
|||
sub powerset { |
sub powerset { |
||
Line 1,629: | Line 1,362: | ||
my @subsets = powerset($set); |
my @subsets = powerset($set); |
||
print $_->as_string, "\n" for @subsets;</lang> |
print $_->as_string, "\n" for @subsets;</lang>{{out}}<pre>Set() |
||
Output: |
|||
<pre> |
|||
Set() |
|||
Set(1) |
Set(1) |
||
Set(2) |
Set(2) |
||
Line 1,640: | Line 1,369: | ||
Set(1 3) |
Set(1 3) |
||
Set(2 3) |
Set(2 3) |
||
Set(1 2 3)</pre></li><li><p>'''''Use arrays'''''</p>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. |
|||
Set(1 2 3) |
|||
</pre> |
|||
Recursive solution:<lang perl>sub powerset { |
|||
</li> |
|||
<li><p>'''''Use arrays'''''</p> |
|||
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: |
|||
<lang perl>sub powerset { |
|||
@_ ? map { $_, [$_[0], @$_] } powerset(@_[1..$#_]) : []; |
@_ ? map { $_, [$_[0], @$_] } powerset(@_[1..$#_]) : []; |
||
}</lang>List folding solution:<lang perl>use List::Util qw(reduce); |
|||
}</lang> |
|||
List folding solution: |
|||
<lang perl>use List::Util qw(reduce); |
|||
sub powerset { |
sub powerset { |
||
@{( reduce { [@$a, map([@$_, $b], @$a)] } [[]], @_ )} |
@{( reduce { [@$a, map([@$_, $b], @$a)] } [[]], @_ )} |
||
}</lang>{{out|Usage & output}}<lang perl>my @set = (1, 2, 3); |
|||
}</lang> |
|||
Usage & output: |
|||
<lang perl>my @set = (1, 2, 3); |
|||
my @powerset = powerset(@set); |
my @powerset = powerset(@set); |
||
Line 1,671: | Line 1,385: | ||
print set_to_string(@powerset), "\n";</lang> |
print set_to_string(@powerset), "\n";</lang> |
||
{{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}</li></ul> |
|||
<pre> |
|||
{{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}} |
|||
</pre> |
|||
</li> |
|||
</ul> |
|||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
||
{{incomplete|Perl 6|It shows no proof of the cases with empty sets.}}{{works with|rakudo|2014-02-25}}<lang perl6>sub powerset(Set $s) { $s.combinations.map(*.Set).Set } |
|||
{{works with|rakudo|2014-02-25}} |
|||
say powerset set <a b c d>;</lang>{{out}} |
|||
<lang perl6>sub powerset(Set $s) { $s.combinations.map(*.Set).Set } |
|||
say powerset set <a b c d>;</lang> |
|||
{{out}} |
|||
<pre>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))</pre> |
<pre>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))</pre> |
||
If you don't care about the actual <tt>Set</tt> type, the <tt>.combinations</tt> method by itself may be good enough for you: |
If you don't care about the actual <tt>Set</tt> type, the <tt>.combinations</tt> method by itself may be good enough for you: |
||
<lang perl6>.say for <a b c d>.combinations</lang> |
<lang perl6>.say for <a b c d>.combinations</lang>{{out}}<pre> |
||
{{out}} |
|||
<pre> |
|||
a |
a |
||
b |
b |
||
Line 1,704: | Line 1,407: | ||
b c d |
b c d |
||
a b c d</pre> |
a b c d</pre> |
||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
{{incomplete|PHP|It shows no proof of the cases with empty sets.}} |
|||
<lang PHP> |
|||
<?php |
<lang PHP><?php |
||
function get_subset($binary, $arr) { |
function get_subset($binary, $arr) { |
||
// based on true/false values in $binary array, include/exclude |
// based on true/false values in $binary array, include/exclude |
||
Line 1,765: | Line 1,467: | ||
print_power_sets(array('singleton')); |
print_power_sets(array('singleton')); |
||
print_power_sets(array('dog', 'c', 'b', 'a')); |
print_power_sets(array('dog', 'c', 'b', 'a')); |
||
?></lang>{{out|Output in browser}}<pre>POWER SET of [] |
|||
?> |
|||
</lang> |
|||
Output in browser: |
|||
<lang> |
|||
POWER SET of [] |
|||
POWER SET of [singleton] |
POWER SET of [singleton] |
||
(empty) |
(empty) |
||
Line 1,789: | Line 1,487: | ||
a c dog |
a c dog |
||
b c dog |
b c dog |
||
a b c dog |
a b c dog</pre> |
||
</lang> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
<lang PicoLisp>(de powerset (Lst) |
{{incomplete|PicoLisp|It shows no proof of the cases with empty sets.}}<lang PicoLisp>(de powerset (Lst) |
||
(ifn Lst |
(ifn Lst |
||
(cons) |
(cons) |
||
Line 1,800: | Line 1,496: | ||
(mapcar '((X) (cons (car Lst) X)) L) |
(mapcar '((X) (cons (car Lst) X)) L) |
||
L ) ) ) )</lang> |
L ) ) ) )</lang> |
||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
<lang pli>*process source attributes xref or(!); |
{{incomplete|PL/I|It shows no proof of the cases with empty sets.}}<lang pli>*process source attributes xref or(!); |
||
/*-------------------------------------------------------------------- |
/*-------------------------------------------------------------------- |
||
* 06.01.2014 Walter Pachl translated from REXX |
* 06.01.2014 Walter Pachl translated from REXX |
||
Line 1,868: | Line 1,563: | ||
End;</lang> |
End;</lang> |
||
{{out}}<pre>{} |
|||
'''output''' |
|||
<pre>{} |
|||
{one} |
{one} |
||
{two} |
{two} |
||
Line 1,885: | Line 1,579: | ||
{two,three,four} |
{two,three,four} |
||
{one,two,three,four}</pre> |
{one,two,three,four}</pre> |
||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
{{incomplete|Prolog|It shows no proof of the cases with empty sets.}} |
|||
===Logical (cut-free) Definition=== |
===Logical (cut-free) Definition=== |
||
The predicate powerset(X,Y) defined here can be read as "Y is the |
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. |
powerset of X", it being understood that lists are used to represent sets. |
||
<p>The predicate subseq(X,Y) is true if and only if the list X is a subsequence of the list Y.</p>The definitions here are elementary, logical (cut-free), and efficient (within the class of comparably generic implementations). |
|||
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). |
|||
<lang Prolog>powerset(X,Y) :- bagof( S, subseq(S,X), Y). |
<lang Prolog>powerset(X,Y) :- bagof( S, subseq(S,X), Y). |
||
Line 1,900: | Line 1,590: | ||
subseq( [], [_|_]). |
subseq( [], [_|_]). |
||
subseq( [X|Xs], [X|Ys] ) :- subseq(Xs, Ys). |
subseq( [X|Xs], [X|Ys] ) :- subseq(Xs, Ys). |
||
subseq( [X|Xs], [_|Ys] ) :- append(_, [X|Zs], Ys), subseq(Xs, Zs). |
subseq( [X|Xs], [_|Ys] ) :- append(_, [X|Zs], Ys), subseq(Xs, Zs).</lang>{{out}}<pre>?- powerset([1,2,3], X). |
||
</lang> |
|||
Output : |
|||
<pre>?- powerset([1,2,3], X). |
|||
X = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]. |
X = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]. |
||
Line 1,914: | Line 1,601: | ||
X = 1, |
X = 1, |
||
Y = 2.</pre> |
Y = 2.</pre> |
||
===Single-Functor Definition=== |
===Single-Functor Definition=== |
||
<lang Prolog>power_set( [], [[]]). |
<lang Prolog>power_set( [], [[]]). |
||
Line 1,921: | Line 1,607: | ||
maplist( append([X]), PS1, PS2 ), % i.e. prepend X to each PS1 |
maplist( append([X]), PS1, PS2 ), % i.e. prepend X to each PS1 |
||
append(PS1, PS2, PS).</lang> |
append(PS1, PS2, PS).</lang> |
||
{{out}}<pre>?- power_set([1,2,3,4,5,6,7,8], X), length(X,N), writeln(N). |
|||
Output : |
|||
256</pre> |
|||
<pre>?- power_set([1,2,3,4,5,6,7,8], X), length(X,N), writeln(N). |
|||
256 |
|||
</pre> |
|||
===Constraint Handling Rules=== |
===Constraint Handling Rules=== |
||
CHR is a programming language created by '''Professor Thom Frühwirth'''.< |
{{libheader|chr}}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'''.<lang Prolog>:- use_module(library(chr)). |
||
Works with SWI-Prolog and module chr written by '''Tom Schrijvers''' and '''Jan Wielemaker'''. |
|||
<lang Prolog>:- use_module(library(chr)). |
|||
:- chr_constraint chr_power_set/2, chr_power_set/1, clean/0. |
:- chr_constraint chr_power_set/2, chr_power_set/1, clean/0. |
||
Line 1,937: | Line 1,619: | ||
only_one @ chr_power_set(A) \ chr_power_set(A) <=> true. |
only_one @ chr_power_set(A) \ chr_power_set(A) <=> true. |
||
creation @ chr_power_set([H | T], A) <=> |
creation @ chr_power_set([H | T], A) <=> |
||
Line 1,945: | Line 1,626: | ||
chr_power_set(B). |
chr_power_set(B). |
||
empty_element @ chr_power_set([], _) <=> chr_power_set([]).</lang>{{out|Example of output}}<pre> ?- 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],[]] .</pre> |
|||
empty_element @ chr_power_set([], _) <=> chr_power_set([]). |
|||
</lang> |
|||
Example of output : |
|||
<pre> ?- 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],[]] . |
|||
</pre> |
|||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
This code is for console mode. |
{{incomplete|PureBasic|It shows no proof of the cases with empty sets.}}This code is for console mode.<lang PureBasic>If OpenConsole() |
||
<lang PureBasic>If OpenConsole() |
|||
Define argc=CountProgramParameters() |
Define argc=CountProgramParameters() |
||
If argc>=(SizeOf(Integer)*8) Or argc<1 |
If argc>=(SizeOf(Integer)*8) Or argc<1 |
||
Line 1,979: | Line 1,653: | ||
PrintN("}") |
PrintN("}") |
||
EndIf |
EndIf |
||
EndIf</lang> |
EndIf</lang>{{out|Sample output}} |
||
<!-- Output modified with a line break to avoid being too long --> |
|||
Sample output |
|||
<pre>C:\Users\PureBasic_User\Desktop>"Power Set.exe" 1 2 3 4 |
<pre>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}, |
{{}, {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}}</pre> |
{2, 4}, {1, 2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}</pre> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{incomplete|Python|It shows no proof of the cases with empty sets.}} |
|||
<lang python>def list_powerset(lst): |
<lang python>def list_powerset(lst): |
||
# the power set of the empty set has one element, the empty set |
# the power set of the empty set has one element, the empty set |
||
Line 2,006: | Line 1,678: | ||
def powerset(s): |
def powerset(s): |
||
return frozenset(map(frozenset, list_powerset(list(s))))</lang><tt>list_powerset</tt> computes the power set of a list of distinct elements. <tt>powerset</tt> simply converts the input and output from lists to sets. We use the <tt>frozenset</tt> type here for immutable sets, because unlike mutable sets, it can be put into other sets. |
|||
return frozenset(map(frozenset, list_powerset(list(s))))</lang> |
|||
{{out|Example}}<pre> |
|||
<tt>list_powerset</tt> computes the power set of a list of distinct elements. <tt>powerset</tt> simply converts the input and output from lists to sets. We use the <tt>frozenset</tt> type here for immutable sets, because unlike mutable sets, it can be put into other sets. |
|||
Example: |
|||
<pre> |
|||
>>> list_powerset([1,2,3]) |
>>> list_powerset([1,2,3]) |
||
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] |
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] |
||
Line 2,018: | Line 1,686: | ||
</pre> |
</pre> |
||
==== Further Explanation ==== |
==== 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 |
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): |
||
<lang python>def powersetlist(s): |
|||
r = [[]] |
r = [[]] |
||
for e in s: |
for e in s: |
||
Line 2,027: | Line 1,694: | ||
s= [0,1,2,3] |
s= [0,1,2,3] |
||
print "\npowersetlist(%r) =\n %r" % (s, powersetlist(s))</lang> |
print "\npowersetlist(%r) =\n %r" % (s, powersetlist(s))</lang>{{out|Sample output}} |
||
r: [[]] e: 0 |
|||
r: [[], [0]] e: 1 |
|||
Sample output: |
|||
r: [[], [0], [1], [0, 1]] e: 2 |
|||
r: [[], [0]] |
r: [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]] e: 3 |
||
r: [[], [0], [1], [0, 1]] e: 2 |
|||
powersetlist([0, 1, 2, 3]) = |
|||
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]] |
[[], [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]] |
||
</pre> |
|||
=== Binary Count method === |
=== 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. |
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) |
(Note that only frozensets can be members of a set in the second function)<lang python>def powersequence(val): |
||
<lang python>def powersequence(val): |
|||
''' Generate a 'powerset' for sequence types that are indexable by integers. |
''' Generate a 'powerset' for sequence types that are indexable by integers. |
||
Uses a binary count to enumerate the members and returns a list |
Uses a binary count to enumerate the members and returns a list |
||
Line 2,067: | Line 1,730: | ||
''' |
''' |
||
return set( frozenset(x) for x in powersequence(list(s)) )</lang> |
return set( frozenset(x) for x in powersequence(list(s)) )</lang> |
||
=== Recursive Alternative === |
=== 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. |
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.<lang python>def p(l): |
||
<lang python> |
|||
def p(l): |
|||
if not l: return [[]] |
if not l: return [[]] |
||
return p(l[1:]) + [[l[0]] + x for x in p(l[1:])] |
return p(l[1:]) + [[l[0]] + x for x in p(l[1:])]</lang> |
||
</lang> |
|||
===Python: Standard documentation=== |
===Python: Standard documentation=== |
||
Pythons [http://docs.python.org/3/library/itertools.html?highlight=powerset#itertools-recipes documentation] has a method that produces the groupings, but not as sets: |
Pythons [http://docs.python.org/3/library/itertools.html?highlight=powerset#itertools-recipes documentation] has a method that produces the groupings, but not as sets:<lang python>>>> from pprint import pprint as pp |
||
<lang python>>>> from pprint import pprint as pp |
|||
>>> from itertools import chain, combinations |
>>> from itertools import chain, combinations |
||
>>> |
>>> |
||
Line 2,106: | Line 1,761: | ||
(4,)} |
(4,)} |
||
>>> </lang> |
>>> </lang> |
||
=={{header|Qi}}== |
=={{header|Qi}}== |
||
{{incomplete|Qi|It shows no proof of the cases with empty sets.}}{{trans|Scheme}}<lang qi>(define powerset |
|||
{{trans|Scheme}} |
|||
<lang qi> |
|||
(define powerset |
|||
[] -> [[]] |
[] -> [[]] |
||
[A|As] -> (append (map (cons A) (powerset As)) |
[A|As] -> (append (map (cons A) (powerset As)) |
||
(powerset As))) |
(powerset As)))</lang> |
||
</lang> |
|||
=={{header|R}}== |
=={{header|R}}== |
||
{{incomplete|R|It shows no proof of the cases with empty sets.}} |
|||
===Non-recursive version=== |
===Non-recursive version=== |
||
The conceptual basis for this algorithm is the following: |
The conceptual basis for this algorithm is the following:<lang>for each element in the set: |
||
<lang>for each element in the set: |
|||
for each subset constructed so far: |
for each subset constructed so far: |
||
new subset = (subset + element) |
new subset = (subset + element)</lang>This method is much faster than a recursive method, though the speed is still O(2^n).<lang R>powerset = function(set){ |
||
</lang> |
|||
This method is much faster than a recursive method, though the speed is still O(2^n). |
|||
<lang R>powerset = function(set){ |
|||
ps = list() |
ps = list() |
||
ps[[1]] = numeric() #Start with the empty set. |
ps[[1]] = numeric() #Start with the empty set. |
||
Line 2,139: | Line 1,784: | ||
} |
} |
||
powerset(1:4)</lang>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. |
|||
powerset(1:4) |
|||
</lang> |
|||
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=== |
===Recursive version=== |
||
{{libheader|sets}} |
{{libheader|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. |
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.<lang R>library(sets)</lang> |
||
An example with a vector.<lang R>v <- (1:3)^2 |
|||
<lang R>library(sets)</lang> |
|||
An example with a vector. |
|||
<lang R>v <- (1:3)^2 |
|||
sv <- as.set(v) |
sv <- as.set(v) |
||
2^sv</lang> |
2^sv</lang> |
||
{{}, {1}, {4}, {9}, {1, 4}, {1, 9}, {4, 9}, {1, 4, 9}} |
{{}, {1}, {4}, {9}, {1, 4}, {1, 9}, {4, 9}, {1, 4, 9}} |
||
An example with a list. |
An example with a list.<lang R>l <- list(a=1, b="qwerty", c=list(d=TRUE, e=1:3)) |
||
<lang R>l <- list(a=1, b="qwerty", c=list(d=TRUE, e=1:3)) |
|||
sl <- as.set(l) |
sl <- as.set(l) |
||
2^sl</lang> |
2^sl</lang> |
||
{{}, {1}, {"qwerty"}, {<<list(2)>>}, {1, <<list(2)>>}, {"qwerty", |
{{}, {1}, {"qwerty"}, {<<list(2)>>}, {1, <<list(2)>>}, {"qwerty", |
||
1}, {"qwerty", <<list(2)>>}, {"qwerty", 1, <<list(2)>>}} |
1}, {"qwerty", <<list(2)>>}, {"qwerty", 1, <<list(2)>>}} |
||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
{{incomplete|Racket|It shows no proof of the cases with empty sets.}}<lang racket>;;; Direct translation of 'functional' ruby method |
|||
<lang racket> |
|||
;;; Direct translation of 'functional' ruby method |
|||
(define (powerset s) |
(define (powerset s) |
||
(for/fold ([outer-set (set(set))]) ([element s]) |
(for/fold ([outer-set (set(set))]) ([element s]) |
||
(set-union outer-set |
(set-union outer-set |
||
(list->set (set-map outer-set |
(list->set (set-map outer-set |
||
(λ(inner-set) (set-add inner-set element))))))) |
(λ(inner-set) (set-add inner-set element)))))))</lang> |
||
</lang> |
|||
=={{header|Rascal}}== |
=={{header|Rascal}}== |
||
{{incomplete|Rascal|It shows no proof of the cases with empty sets.}} |
|||
<lang rascal> |
|||
import Set; |
<lang rascal>import Set; |
||
public set[set[&T]] PowerSet(set[&T] s) = power(s); |
public set[set[&T]] PowerSet(set[&T] s) = power(s);</lang>{{out|An example output}} |
||
rascal>PowerSet({1,2,3,4}) |
|||
</lang> |
|||
set[set[int]]: { |
|||
An example output: |
|||
<lang rascal> |
|||
rascal>PowerSet({1,2,3,4}) |
|||
set[set[int]]: { |
|||
{4,3}, |
{4,3}, |
||
{4,2,1}, |
{4,2,1}, |
||
Line 2,198: | Line 1,827: | ||
{3,2,1}, |
{3,2,1}, |
||
{} |
{} |
||
} |
} |
||
</lang> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
<lang rexx>/*REXX program to display a power set, items may be anything (no blanks)*/ |
{{incomplete|REXX|It shows no proof of the cases with empty sets.}}<lang rexx>/*REXX program to display a power set, items may be anything (no blanks)*/ |
||
parse arg S /*let user specify the set. */ |
parse arg S /*let user specify the set. */ |
||
if S='' then S='one two three four' /*None specified? Use default*/ |
if S='' then S='one two three four' /*None specified? Use default*/ |
||
Line 2,231: | Line 1,858: | ||
end /*u*/ |
end /*u*/ |
||
return 0</lang> |
return 0</lang> |
||
{{out|when using the default input}} |
|||
<pre> 1 {} |
|||
<pre style="overflow:scroll"> |
|||
1 {} |
|||
2 {one} |
2 {one} |
||
3 {two} |
3 {two} |
||
Line 2,248: | Line 1,874: | ||
14 {one,three,four} |
14 {one,three,four} |
||
15 {two,three,four} |
15 {two,three,four} |
||
16 {one,two,three,four} |
16 {one,two,three,four}</pre> |
||
</pre> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
<lang ruby># Based on http://johncarrino.net/blog/2006/08/11/powerset-in-ruby/ |
{{incomplete|Ruby|It shows no proof of the cases with empty sets.}}<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. |
# See the link if you want a shorter version. This was intended to show the reader how the method works. |
||
class Array |
class Array |
||
Line 2,294: | Line 1,918: | ||
p %w(one two three).func_power_set |
p %w(one two three).func_power_set |
||
p Set[1,2,3].powerset</lang> |
p Set[1,2,3].powerset</lang>{{out}}<pre> |
||
{{out}} |
|||
<pre> |
|||
[[], [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]] |
[[], [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"]] |
[[], ["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}>}> |
#<Set: {#<Set: {}>, #<Set: {1}>, #<Set: {2}>, #<Set: {1, 2}>, #<Set: {3}>, #<Set: {1, 3}>, #<Set: {2, 3}>, #<Set: {1, 2, 3}>}> |
||
</pre> |
</pre> |
||
=={{header|SAS}}== |
=={{header|SAS}}== |
||
{{incomplete|SAS|It shows no proof of the cases with empty sets.}}<lang SAS>options mprint mlogic symbolgen source source2; |
|||
<lang SAS> |
|||
options mprint mlogic symbolgen source source2; |
|||
%macro SubSets (FieldCount = ); |
%macro SubSets (FieldCount = ); |
||
Line 2,356: | Line 1,976: | ||
%end; |
%end; |
||
%Mend SubSets; |
%Mend SubSets;</lang>You can then call the macro as: |
||
<lang SAS>%SubSets(FieldCount = 5);</lang>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.{{out}}<pre> |
|||
</lang> |
|||
You can then call the macro as: |
|||
<lang SAS> |
|||
%SubSets(FieldCount = 5); |
|||
</lang> |
|||
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: |
|||
<pre> |
|||
Obs F1 F2 F3 F4 F5 RowCount |
Obs F1 F2 F3 F4 F5 RowCount |
||
1 . . . . . 1 |
1 . . . . . 1 |
||
Line 2,400: | Line 2,010: | ||
30 1 1 1 . 1 30 |
30 1 1 1 . 1 30 |
||
31 1 1 1 1 . 31 |
31 1 1 1 1 . 31 |
||
32 1 1 1 1 1 32 |
32 1 1 1 1 1 32</pre> |
||
</pre> |
|||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
[[Category:Scala Implementations]] |
[[Category:Scala Implementations]] |
||
Testing the cases: |
|||
#{1,2,3,4} |
|||
#<math>\mathcal{P}</math>(<math>\varnothing</math>) = { <math>\varnothing</math> } |
|||
#<math>\mathcal{P}</math>({<math>\varnothing</math>}) = { <math>\varnothing</math>, { <math>\varnothing</math> } } |
|||
<lang scala>import scala.compat.Platform.currentTime |
|||
object Powerset extends App { |
object Powerset extends App { |
||
Line 2,411: | Line 2,024: | ||
assert(powerset(Set(1, 2, 3, 4)) == Set(Set.empty, Set(1), Set(2), Set(3), Set(4), Set(1, 2), Set(1, 3), Set(1, 4), |
assert(powerset(Set(1, 2, 3, 4)) == Set(Set.empty, Set(1), Set(2), Set(3), Set(4), Set(1, 2), Set(1, 3), Set(1, 4), |
||
Set(2, 3), Set(2, 4), Set(3, 4), Set(1, 2, 3), Set(1, 3, 4), Set(1, 2, 4), Set(2, 3, 4), Set(1, 2, 3, 4))) |
Set(2, 3), Set(2, 4), Set(3, 4), Set(1, 2, 3), Set(1, 3, 4), Set(1, 2, 4), Set(2, 3, 4), Set(1, 2, 3, 4))) |
||
assert(powerset(Set()) == Set(Set())) |
|||
assert(powerset(Set(Set())) == Set(Set(), Set(Set()))) |
|||
println(s"Successfully completed without errors. [total ${currentTime - executionStart} ms]") |
println(s"Successfully completed without errors. [total ${currentTime - executionStart} ms]") |
||
}</lang>Another option that produces |
}</lang>Another option that produces a iterator of the sets:<lang scala>def powerset[A](s: Set[A]) = (0 to s.size).map(s.toSeq.combinations(_)).reduce(_ ++ _).map(_.toSet)</lang> |
||
<lang scala>def powerset[A](s: Set[A]) = (0 to s.size).map(s.toSeq.combinations(_)).reduce(_ ++ _).map(_.toSet)</lang> |
|||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
{{trans|Common Lisp}} |
{{incomplete|Scheme|It shows no proof of the cases with empty sets.}}{{trans|Common Lisp}} |
||
<lang scheme>(define (power-set set) |
<lang scheme>(define (power-set set) |
||
(if (null? set) |
(if (null? set) |
||
Line 2,429: | Line 2,043: | ||
(display (power-set (list "A" "C" "E"))) |
(display (power-set (list "A" "C" "E"))) |
||
(newline)</lang> |
(newline)</lang>{{out}} |
||
Output: |
|||
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ()) |
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ()) |
||
((A C E) (A C) (A E) (A) (C E) (C) (E) ()) |
((A C E) (A C) (A E) (A) (C E) (C) (E) ()) |
||
Call/cc generation:<lang lisp>(define (power-set lst) |
Call/cc generation:<lang lisp>(define (power-set lst) |
||
(define (iter yield) |
(define (iter yield) |
||
Line 2,462: | Line 2,074: | ||
(2) |
(2) |
||
(3) |
(3) |
||
()</lang>Iterative:<lang scheme>(define (power_set_iter set) |
|||
()</lang> |
|||
Iterative:<lang scheme> |
|||
(define (power_set_iter set) |
|||
(let loop ((res '(())) (s set)) |
(let loop ((res '(())) (s set)) |
||
(if (empty? s) |
(if (empty? s) |
||
res |
res |
||
(loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s))))) |
(loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s))))) |
||
</lang> |
</lang>{{out}} '((e d c b a) |
||
Output:<lang output> |
|||
'((e d c b a) |
|||
(e d c b) |
(e d c b) |
||
(e d c a) |
(e d c a) |
||
Line 2,505: | Line 2,111: | ||
(a) |
(a) |
||
()) |
()) |
||
</lang> |
|||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
<lang seed7>$ include "seed7_05.s7i"; |
{{incomplete|Seed7|It shows no proof of the cases with empty sets.}}<lang seed7>$ include "seed7_05.s7i"; |
||
const func array bitset: powerSet (in bitset: baseSet) is func |
const func array bitset: powerSet (in bitset: baseSet) is func |
||
Line 2,536: | Line 2,140: | ||
writeln(aSet); |
writeln(aSet); |
||
end for; |
end for; |
||
end func;</lang> |
end func;</lang>{{out}}<pre>{} |
||
Output: |
|||
<pre> |
|||
{} |
|||
{1} |
{1} |
||
{2} |
{2} |
||
Line 2,555: | Line 2,155: | ||
{1, 3, 4} |
{1, 3, 4} |
||
{2, 3, 4} |
{2, 3, 4} |
||
{1, 2, 3, 4} |
{1, 2, 3, 4}</pre> |
||
</pre> |
|||
=={{header|Smalltalk}}== |
=={{header|Smalltalk}}== |
||
{{incomplete|Smalltalk|It shows no proof of the cases with empty sets.}} |
|||
{{works with|GNU Smalltalk}} |
{{works with|GNU Smalltalk}} |
||
Code from [http://smalltalk.gnu.org/blog/bonzinip/fun-generators Bonzini's blog] |
Code from [http://smalltalk.gnu.org/blog/bonzinip/fun-generators Bonzini's blog]<lang smalltalk>Collection extend [ |
||
<lang smalltalk>Collection extend [ |
|||
power [ |
power [ |
||
^(0 to: (1 bitShift: self size) - 1) readStream collect: [ :each || i | |
^(0 to: (1 bitShift: self size) - 1) readStream collect: [ :each || i | |
||
Line 2,568: | Line 2,165: | ||
self select: [ :elem | (each bitAt: (i := i + 1)) = 1 ] ] |
self select: [ :elem | (each bitAt: (i := i + 1)) = 1 ] ] |
||
] |
] |
||
].</lang><lang smalltalk>#(1 2 4) power do: [ :each | |
|||
].</lang> |
|||
<lang smalltalk>#(1 2 4) power do: [ :each | |
|||
each asArray printNl ]. |
each asArray printNl ]. |
||
#( 'A' 'C' 'E' ) power do: [ :each | |
#( 'A' 'C' 'E' ) power do: [ :each | |
||
each asArray printNl ].</lang> |
each asArray printNl ].</lang> |
||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |
||
{{incomplete|Standard ML|It shows no proof of the cases with empty sets.}}Version for lists:<lang sml>fun subsets xs = foldr (fn (x, rest) => rest @ map (fn ys => x::ys) rest) [[]] xs</lang> |
|||
version for lists: |
|||
<lang sml>fun subsets xs = foldr (fn (x, rest) => rest @ map (fn ys => x::ys) rest) [[]] xs</lang> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
<lang tcl>proc subsets {l} { |
{{incomplete|Tcl|It shows no proof of the cases with empty sets.}}<lang tcl>proc subsets {l} { |
||
set res [list [list]] |
set res [list [list]] |
||
foreach e $l { |
foreach e $l { |
||
Line 2,589: | Line 2,180: | ||
return $res |
return $res |
||
} |
} |
||
puts [subsets {a b c d}]</lang> |
puts [subsets {a b c d}]</lang>{{out}} |
||
{} 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} |
|||
Output: |
|||
<pre>{} 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}</pre> |
|||
===Binary Count Method=== |
===Binary Count Method=== |
||
<lang tcl>proc powersetb set { |
<lang tcl>proc powersetb set { |
||
Line 2,605: | Line 2,195: | ||
return $res |
return $res |
||
}</lang> |
}</lang> |
||
=={{header|TXR}}== |
=={{header|TXR}}== |
||
{{incomplete|TXR|It shows no proof of the cases with empty sets.}} |
|||
{{trans|Common Lisp}}The power set function can be written concisely like this:<lang txr>(defun power-set (s) |
|||
{{trans|Common Lisp}} |
|||
The power set function can be written concisely like this: |
|||
<lang txr>(defun power-set (s) |
|||
(reduce-right |
(reduce-right |
||
(op append (mapcar (op cons @@1) @2) @2) |
(op append (mapcar (op cons @@1) @2) @2) |
||
s '(())))</lang>A complete program which takes command line arguments and prints the power set in comma-separated brace notation:<lang txr>@(do (defun power-set (s) |
|||
s '(())))</lang> |
|||
A complete program which takes command line arguments and prints the power set in comma-separated brace notation: |
|||
<lang txr>@(do (defun power-set (s) |
|||
(reduce-right |
(reduce-right |
||
(op append (mapcar (op cons @@1) @2) @2) |
(op append (mapcar (op cons @@1) @2) @2) |
||
Line 2,628: | Line 2,209: | ||
{@(rep)@pset, @(last)@pset@(empty)@(end)} |
{@(rep)@pset, @(last)@pset@(empty)@(end)} |
||
@ (end) |
@ (end) |
||
@(end)</lang> |
@(end)</lang><pre>$ txr rosetta/power-set.txr 1 2 3 |
||
<pre>$ txr rosetta/power-set.txr 1 2 3 |
|||
{1, 2, 3} |
{1, 2, 3} |
||
{1, 2} |
{1, 2} |
||
Line 2,638: | Line 2,217: | ||
{2} |
{2} |
||
{3} |
{3} |
||
{}</pre>What is not obvious is that the above <code>power-set</code> function generalizes to strings and vectors.<lang txr>@(do (defun power-set (s) |
|||
{}</pre> |
|||
What is not obvious is that the above <code>power-set</code> function generalizes to strings and vectors. |
|||
<lang txr>@(do (defun power-set (s) |
|||
(reduce-right |
(reduce-right |
||
(op append (mapcar (op cons @@1) @2) @2) |
(op append (mapcar (op cons @@1) @2) @2) |
||
Line 2,648: | Line 2,223: | ||
(prinl (power-set "abc")) |
(prinl (power-set "abc")) |
||
(prinl (power-set "")) |
(prinl (power-set "")) |
||
(prinl (power-set #(1 2 3))))</lang> |
(prinl (power-set #(1 2 3))))</lang>txr power-set-generic.txr |
||
((#\a #\b #\c) (#\a #\b) (#\a #\c) (#\a) (#\b #\c) (#\b) (#\c) nil) |
|||
((nil) nil) |
|||
<pre>txr power-set-generic.txr |
|||
(( |
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) nil) |
||
((nil) nil) |
|||
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) nil)</pre> |
|||
=={{header|UnixPipes}}== |
=={{header|UnixPipes}}== |
||
{{incomplete|UnixPipes|It shows no proof of the cases with empty sets.}}<lang ksh>| cat A |
|||
<lang ksh> |
|||
| cat A |
|||
a |
a |
||
b |
b |
||
Line 2,678: | Line 2,249: | ||
b |
b |
||
b c |
b c |
||
c</lang> |
|||
c |
|||
</lang> |
|||
=={{header|UNIX Shell}}== |
=={{header|UNIX Shell}}== |
||
{{incomplete|UNIX Shell|It shows no proof of the cases with empty sets.}} |
|||
From [http://www.catonmat.net/blog/set-operations-in-unix-shell/ here] |
From [http://www.catonmat.net/blog/set-operations-in-unix-shell/ here] |
||
<lang bash>p() { [ $# -eq 0 ] && echo || (shift; p "$@") | while read r ; do echo -e "$1 $r\n$r"; done }</lang> |
<lang bash>p() { [ $# -eq 0 ] && echo || (shift; p "$@") | while read r ; do echo -e "$1 $r\n$r"; done }</lang> |
||
Line 2,692: | Line 2,263: | ||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
{{incomplete|Ursala|It shows no proof of the cases with empty sets.}} |
|||
Sets are a built in type constructor in Ursala, represented as |
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. |
||
lexically sorted lists with duplicates removed. The powerset function |
|||
is a standard library function, but could be defined as shown |
|||
below. |
|||
<lang Ursala>powerset = ~&NiC+ ~&i&& ~&at^?\~&aNC ~&ahPfatPRXlNrCDrT</lang> |
<lang Ursala>powerset = ~&NiC+ ~&i&& ~&at^?\~&aNC ~&ahPfatPRXlNrCDrT</lang> |
||
test program: |
test program: |
||
Line 2,702: | Line 2,270: | ||
test = powerset {'a','b','c','d'}</lang> |
test = powerset {'a','b','c','d'}</lang> |
||
{{out}} |
|||
output: |
|||
{ |
|||
<pre>{ |
|||
{}, |
{}, |
||
{'a'}, |
{'a'}, |
||
Line 2,719: | Line 2,287: | ||
{'c'}, |
{'c'}, |
||
{'c','d'}, |
{'c','d'}, |
||
{'d'}} |
{'d'}} |
||
=={{header|V}}== |
=={{header|V}}== |
||
{{incomplete|V|It shows no proof of the cases with empty sets.}} |
|||
V has a built in called powerlist |
V has a built in called powerlist |
||
<lang v>[A C E] powerlist |
<lang v>[A C E] powerlist |
||
=[[A C E] [A C] [A E] [A] [C E] [C] [E] []]</lang> |
=[[A C E] [A C] [A E] [A] [C E] [C] [E] []]</lang> |
||
Its implementation in std.v is (like joy) |
|||
its implementation in std.v is (like joy) |
|||
<lang v>[powerlist |
<lang v>[powerlist |
||
[null?] |
[null?] |
||
Line 2,732: | Line 2,299: | ||
[uncons] |
[uncons] |
||
[dup swapd [cons] map popd swoncat] |
[dup swapd [cons] map popd swoncat] |
||
linrec]. |
linrec].</lang> |
||
</lang> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
Using a combinations function, build the power set from combinations of 1,2,... items. |
Using a combinations function, build the power set from combinations of 1,2,... items. |
||
Line 2,745: | Line 2,310: | ||
foreach n in (5){ |
foreach n in (5){ |
||
ps:=pwerSet((1).pump(n,List)); ps.println(" Size = ",ps.len()); |
ps:=pwerSet((1).pump(n,List)); ps.println(" Size = ",ps.len()); |
||
}</pre> |
|||
} |
|||
L(L()) Size = 1 |
|||
</pre> |
|||
L(L(),L(1)) Size = 2 |
|||
<pre> |
|||
L(L()) Size = |
L(L(),L(1),L(2),L(1,2)) Size = 4 |
||
L(L(),L(1)) Size = |
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(1,2)) |
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(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 |
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 |
||
</pre> |
|||
{{omit from|GUISS}} |
{{omit from|GUISS}} |
Revision as of 10:57, 3 September 2014
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):
() = { }
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):
({}) = { , { } }
Ada
This solution prints the power set of words read from the command line.<lang ada>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 work
end Power_Set;</lang>
- 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
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
);
- 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
)</lang>
- 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<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>
BBC BASIC
The elements of a set are represented as the bits in an integer (hence the maximum size of set is 32).<lang bbcbasic> 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$) + "}"</lang>
- 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
<lang 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))
);</lang>
- 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
<lang 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}}</lang>
C
<lang 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;
}</lang>
- Output:
% ./a.out 1 2 3[ ] [ 3 ] [ 2 ] [ 3 2 ] [ 1 ] [ 3 1 ] [ 2 1 ]
[ 3 2 1 ]
C++
Non-recursive version
<lang cpp>#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"; }
}</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 }
Recursive version
<lang cpp>#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());
}</lang>
C#
<lang csharp>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()));
}</lang>
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: <lang csharp> 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 })))); }</lang>
Clojure
<lang 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))</lang>
Alternate solution, with no dependency on third-party library: <lang Clojure>(defn powerset [coll]
(reduce (fn [a x] (->> a (map #(set (concat #{x} %))) (concat a) set)) #{#{}} coll))
(powerset #{1 2 3})</lang>
#{#{} #{1} #{2} #{1 2} #{3} #{1 3} #{2 3} #{1 2 3}}
CoffeeScript
<lang 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']</lang>
- Output:
> coffee power_set.coffeePOWER 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+<lang javascript>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]);</lang>
- 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"]
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> Imperative-style using LOOP: <lang lisp>(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)))</lang>
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. <lang lisp>(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)))))</lang>
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):<lang d>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;
}</lang>
- 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. <lang d>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; }
}</lang>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
.<lang dejavu>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 }</lang>
- 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
<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]]
Alternate shorter and more efficient version
powerset([H|T]) -> PT = powerset(T),
[ [H|X] || X <- PT ] ++ PT.</lang>or even more efficient version:<lang erlang>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]).</lang>
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>alternatively with list comprehension<lang fsharp>let rec pow =
function | [] -> [[]] | x::xs -> [for i in pow xs do yield! [i;x::i]]</lang>
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.<lang factor>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> ;</lang>
- 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
.
<lang forth>: ?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</lang>
- 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.<lang frink>
a = new set[1,2,3,4] a.subsets[]</lang>
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.<lang funl>def powerset( s ) = s.subsets().toSet()</lang>
The powerset function could be implemented in FunL directly as:<lang funl>def
powerset( {} ) = {{}} powerset( s ) = acc = powerset( s.tail() ) acc + map( x -> {s.head()} + x, acc )</lang>
or, alternatively as:
<lang funl>import lists.foldr
def powerset( s ) = foldr( \x, acc -> acc + map( a -> {x} + a, acc), {{}}, s )
println( powerset({1, 2, 3, 4}) )</lang>
- 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
<lang gap># Built-in
Combinations([1, 2, 3]);
- [ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 2, 3 ], [ 3 ] ]
- Note that it handles duplicates
Combinations([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 ] ]</lang>
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. <lang go>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 interface type 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 method func (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.Eq func (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.String func (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 task func (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))
}</lang>
- 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.<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]]
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.<lang Haskell>import qualified Data.Set as Set
type Set=Set.Set
unionAll :: (Ord a) => Set (Set a) -> Set a
unionAll = 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 c slift 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</lang>
- 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:<lang Icon>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 result
end</lang>To test the above procedure:<lang Icon>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</lang>
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:<lang Icon>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</lang>
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>In the typical use, this operation makes sense on collections of unique elements.<lang J> ~.1 2 3 2 1 1 2 3
#ps 1 2 3 2 1
32
#ps ~.1 2 3 2 1
8</lang>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
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 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; }</lang>
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.<lang java5>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;
}</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(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; }</lang>
JavaScript
Uses a JSON stringifier from http://www.json.org/js.html
<lang javascript>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));</lang>
- 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]]
Julia
<lang julia>function powerset (x)
result = {{}} for i in x, j = 1:length(result) push!(result, [result[j],i]) end result
end</lang>
- Output:
julia> show(powerset({1,2,3})) {{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}}
K
<lang K>
ps:{x@&:'+2_vs!_2^#x}
</lang>Usage:
ps "ABC" ("" ,"C" ,"B" "BC" ,"A" "AC" "AB" "ABC")
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>
Logtalk
<lang 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.</lang>
Usage example: <lang logtalk>| ?- 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</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
--non-recurse implementation function 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 t
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, 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>
{{},{a},{a,b},{a,b,c},{a,c},{b},{b,c},{c}}
Maple
<lang Maple>with(combinat): powerset({1,2,3,4});</lang>
- Output:
{{}, {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}}
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:
{{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}
MATLAB
Sets are not an explicit data type in MATLAB, but cell arrays can be used for the same purpose. In fact, cell arrays have the benefit of containing any kind of data structure. So, this powerset function will work on a set of any type of data structure, without the need to overload any operators.<lang MATLAB>function pset = powerset(theSet)
pset = cell(size(theSet)); %Preallocate memory
%Generate all numbers from 0 to 2^(num elements of the set)-1 for i = ( 0:(2^numel(theSet))-1 ) %Convert i into binary, convert each digit in binary to a boolean %and store that array of booleans indicies = logical(bitget( i,(1:numel(theSet)) )); %Use the array of booleans to extract the members of the original %set, and store the set containing these members in the powerset pset(i+1) = {theSet(indicies)}; end
end</lang>
Sample Usage: Powerset of the set of the empty set.<lang MATLAB>powerset({{}})
ans =
{} {1x1 cell} %This is the same as { {},{{}} }</lang>
Powerset of { {1,2},3 }. <lang MATLAB>powerset({{1,2},3})
ans =
{1x0 cell} {1x1 cell} {1x1 cell} {1x2 cell} %This is the same as { {},Template:1,2,{3},{{1,2},3} }</lang>
Maxima
<lang maxima>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}} */</lang>
Nimrod
<lang nimrod>import sets, hashes
proc hash(x): THash =
var h = 0 for i in x: h = h !& hash(i) result = !$h
proc powerset[T](inset: TSet[T]): auto =
result = toSet([initSet[T]()])
for i in inset: var tmp = result for j in result: var k = j k.incl(i) tmp.incl(k) result = tmp
echo powerset(toSet([1,2,3,4]))</lang>
Objective-C
<lang objc>#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; }</lang>
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>
OPL
<lang 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);
}</lang>
- 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:<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 thens Acc = {Powerset2 T} in {Append Acc {Map Acc fun {$ A} H|A end}} end
end</lang>
PARI/GP
<lang parigp>vector(1<<#S,i,vecextract(S,i-1))</lang>
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:
<lang perl>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";</lang>
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):<lang perl>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...
}</lang>(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'sList::Util
core module) seems a little more elegant in this case:<lang perl>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;</lang>- 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:<lang perl>sub powerset {
@_ ? map { $_, [$_[0], @$_] } powerset(@_[1..$#_]) : [];
}</lang>List folding solution:<lang perl>use List::Util qw(reduce);
sub powerset {
@{( reduce { [@$a, map([@$_, $b], @$a)] } [[]], @_ )}
}</lang>- Usage & output:
my @powerset = powerset(@set);
sub set_to_string {
"{" . join(", ", map { ref $_ ? set_to_string(@$_) : $_ } @_) . "}"
}
print set_to_string(@powerset), "\n";</lang>
{{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}
Perl 6
<lang perl6>sub powerset(Set $s) { $s.combinations.map(*.Set).Set } say powerset set <a b c d>;</lang>
- 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:
<lang perl6>.say for <a b c d>.combinations</lang>
- 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
<lang PHP><?php function 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 '
';
}
function print_power_sets($arr) {
echo "POWER SET of [" . join(", ", $arr) . "]
"; 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'));
?></lang>
- Output in browser:
POWER SET of []POWER SET of [singleton] (empty) singleton POWER SET of [dog, c, b, a] (empty) a b a b c a c b c a b c dog a dog b dog a b dog c dog a c dog b c dog
a b c dog
PicoLisp
<lang PicoLisp>(de powerset (Lst)
(ifn Lst (cons) (let L (powerset (cdr Lst)) (conc (mapcar '((X) (cons (car Lst) X)) L) L ) ) ) )</lang>
PL/I
<lang pli>*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;</lang>
- 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).
<lang Prolog>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).</lang>
- 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
<lang Prolog>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).</lang>
- 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.<lang Prolog>:- 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([]).</lang>
- 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.<lang PureBasic>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("}") EndIf
EndIf</lang>
- 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
<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>
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.<lang python>def p(l):
if not l: return [[]] return p(l[1:]) + [[l[0]] + x for x in p(l[1:])]</lang>
Python: Standard documentation
Pythons documentation has a method that produces the groupings, but not as sets:<lang python>>>> 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,)}
>>> </lang>
Qi
<lang qi>(define powerset
[] -> [[]] [A|As] -> (append (map (cons A) (powerset As)) (powerset As)))</lang>
R
Non-recursive version
The conceptual basis for this algorithm is the following:<lang>for each element in the set: for each subset constructed so far: new subset = (subset + element)</lang>This method is much faster than a recursive method, though the speed is still O(2^n).<lang R>powerset = function(set){ ps = list() ps1 = 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. tempsubset = c(pssubset,element) } ps=c(ps,temp) #Add the additional subsets ("temp") to "ps". } return(ps) }
powerset(1:4)</lang>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
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.<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)>>}}
Racket
<lang 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)))))))</lang>
Rascal
<lang rascal>import Set;
public set[set[&T]] PowerSet(set[&T] s) = power(s);</lang>
- 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
<lang 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 1 p=!.d; do u=d to y; !.u=p+1
if !.u==bbase+u then return .combU(u-1) p=!.u end /*u*/
return 0</lang>
- 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
<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| 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 } end
end
- A direct translation of the "power array" version above
require 'set' class Set
def powerset inject(Set[Set[]]) do |ps, item| ps.union ps.map {|e| e.union (Set.new [item])} end end
end
p [1,2,3,4].power_set p %w(one two three).func_power_set
p Set[1,2,3].powerset</lang>
- 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
<lang 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;</lang>You can then call the macro as:
<lang SAS>%SubSets(FieldCount = 5);</lang>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
Testing the cases:
- {1,2,3,4}
- () = { }
- ({}) = { , { } }
<lang scala>import scala.compat.Platform.currentTime
object Powerset extends App {
def powerset[A](s: Set[A]) = s.foldLeft(Set(Set.empty[A])) { case (ss, el) => ss ++ ss.map(_ + el)}
assert(powerset(Set(1, 2, 3, 4)) == Set(Set.empty, Set(1), Set(2), Set(3), Set(4), Set(1, 2), Set(1, 3), Set(1, 4), Set(2, 3), Set(2, 4), Set(3, 4), Set(1, 2, 3), Set(1, 3, 4), Set(1, 2, 4), Set(2, 3, 4), Set(1, 2, 3, 4))) assert(powerset(Set()) == Set(Set())) assert(powerset(Set(Set())) == Set(Set(), Set(Set())))
println(s"Successfully completed without errors. [total ${currentTime - executionStart} ms]")
}</lang>Another option that produces a iterator of the sets:<lang scala>def powerset[A](s: Set[A]) = (0 to s.size).map(s.toSeq.combinations(_)).reduce(_ ++ _).map(_.toSet)</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) ())
Call/cc generation:<lang lisp>(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)))))</lang>output<lang>(1 2)
(1 3) (1) (2 3) (2) (3) ()</lang>Iterative:<lang scheme>(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)))))
</lang>
- 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) ())
Seed7
<lang seed7>$ include "seed7_05.s7i";
const func array bitset: powerSet (in bitset: baseSet) is func
result var array bitset: pwrSet is [] (bitset.value); local var integer: element is 0; var integer: index is 0; var bitset: aSet is bitset.value; begin for element range baseSet do for key index range pwrSet do aSet := pwrSet[index]; if element not in aSet then incl(aSet, element); pwrSet &:= aSet; end if; end for; end for; end func;
const proc: main is func
local var bitset: aSet is bitset.value; begin for aSet range powerSet({1, 2, 3, 4}) do writeln(aSet); end for;
end func;</lang>
- 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}
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>
TXR
The power set function can be written concisely like this:<lang txr>(defun power-set (s)
(reduce-right (op append (mapcar (op cons @@1) @2) @2) s '(())))</lang>A complete program which takes command line arguments and prints the power set in comma-separated brace notation:<lang txr>@(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)</lang>
$ 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.<lang txr>@(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))))</lang>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
<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. <lang Ursala>powerset = ~&NiC+ ~&i&& ~&at^?\~&aNC ~&ahPfatPRXlNrCDrT</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>
zkl
Using a combinations function, build the power set from combinations of 1,2,... items. <lang zkl>fcn pwerSet(list){
(0).pump(list.len(),List, Utils.Helpers.pickNFrom.fp1(list), T(Void.Write,Void.Write) ) .append(list)
}</lang>
- 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
- Programming Tasks
- Discrete math
- Ada
- Ada examples needing attention
- Examples needing attention
- ALGOL 68
- ALGOL 68 examples needing attention
- AutoHotkey
- AutoHotkey examples needing attention
- BBC BASIC
- BBC BASIC examples needing attention
- Bracmat
- Bracmat examples needing attention
- Burlesque
- Burlesque examples needing attention
- C
- C examples needing attention
- C++
- C++ examples needing attention
- C sharp
- C sharp examples needing attention
- Clojure
- CoffeeScript
- CoffeeScript examples needing attention
- ColdFusion
- ColdFusion examples needing attention
- Common Lisp
- Common Lisp examples needing attention
- D
- D examples needing attention
- Déjà Vu
- Déjà Vu examples needing attention
- E
- E examples needing attention
- Erlang
- Erlang examples needing attention
- F Sharp
- F Sharp examples needing attention
- Factor
- Factor examples needing attention
- Forth
- Forth examples needing attention
- Frink
- Frink examples needing attention
- FunL
- GAP
- GAP examples needing attention
- Go
- Go examples needing attention
- Groovy
- Groovy examples needing attention
- Haskell
- Haskell examples needing attention
- Icon
- Unicon
- Icon examples needing attention
- Unicon examples needing attention
- J
- J examples needing attention
- Java
- Java examples needing attention
- Recursion
- JavaScript
- JavaScript examples needing attention
- Julia
- Julia examples needing attention
- K
- K examples needing attention
- Logo
- Logo examples needing attention
- Logtalk
- Logtalk examples needing attention
- Lua
- Lua examples needing attention
- M4
- M4 examples needing attention
- Maple
- Maple examples needing attention
- Mathematica
- Mathematica examples needing attention
- MATLAB
- Maxima
- Maxima examples needing attention
- Nimrod
- Nimrod examples needing attention
- Objective-C
- Objective-C examples needing attention
- OCaml
- OCaml examples needing attention
- OPL
- OPL examples needing attention
- Oz
- Oz examples needing attention
- PARI/GP
- PARI/GP examples needing attention
- Perl
- Perl examples needing attention
- Perl 6
- Perl 6 examples needing attention
- PHP
- PHP examples needing attention
- PicoLisp
- PicoLisp examples needing attention
- PL/I
- PL/I examples needing attention
- Prolog
- Prolog examples needing attention
- Chr
- PureBasic
- PureBasic examples needing attention
- Python
- Python examples needing attention
- Qi
- Qi examples needing attention
- R
- R examples needing attention
- Sets
- Racket
- Racket examples needing attention
- Rascal
- Rascal examples needing attention
- REXX
- REXX examples needing attention
- Ruby
- Ruby examples needing attention
- SAS
- SAS examples needing attention
- Scala
- Scala Implementations
- Scheme
- Scheme examples needing attention
- Seed7
- Seed7 examples needing attention
- Smalltalk
- Smalltalk examples needing attention
- Standard ML
- Standard ML examples needing attention
- Tcl
- Tcl examples needing attention
- TXR
- TXR examples needing attention
- UnixPipes
- UnixPipes examples needing attention
- UNIX Shell
- UNIX Shell examples needing attention
- Ursala
- Ursala examples needing attention
- V
- V examples needing attention
- Zkl
- GUISS/Omit