Power set: Difference between revisions
Content deleted Content added
m →Logical (cut-free) Definition: remove redundant comment |
PascalABC.NET |
||
(216 intermediate revisions by 83 users not shown) | |||
Line 1:
{{task|Discrete math}}
{{omit from|GUISS}}
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.
;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 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 2<sup>n</sup> elements, including the edge cases of [[wp:Empty_set|empty set]].<br />
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> } }<br>
'''Extra credit: ''' Demonstrate that your language supports these last two powersets.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F list_powerset(lst)
V result = [[Int]()]
L(x) lst
result.extend(result.map(subset -> subset [+] [@x]))
R result
print(list_powerset([1, 2, 3]))</syntaxhighlight>
{{out}}
<pre>
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
</pre>
=={{header|ABAP}}==
This works for ABAP Version 7.40 and above
<syntaxhighlight lang="abap">
report z_powerset.
interface set.
methods:
add_element
importing
element_to_be_added type any
returning
value(new_set) type ref to set,
remove_element
importing
element_to_be_removed type any
returning
value(new_set) type ref to set,
contains_element
importing
element_to_be_found type any
returning
value(contains) type abap_bool,
get_size
returning
value(size) type int4,
is_equal
importing
set_to_be_compared_with type ref to set
returning
value(equal) type abap_bool,
get_elements
exporting
elements type any table,
stringify
returning
value(stringified_set) type string.
endinterface.
class string_set definition.
public section.
interfaces:
set.
methods:
constructor
importing
elements type stringtab optional,
build_powerset
returning
value(powerset) type ref to string_set.
private section.
data elements type stringtab.
endclass.
class string_set implementation.
method constructor.
loop at elements into data(element).
me->set~add_element( element ).
endloop.
endmethod.
method set~add_element.
if not line_exists( me->elements[ table_line = element_to_be_added ] ).
append element_to_be_added to me->elements.
endif.
new_set = me.
endmethod.
method set~remove_element.
if line_exists( me->elements[ table_line = element_to_be_removed ] ).
delete me->elements where table_line = element_to_be_removed.
endif.
new_set = me.
endmethod.
method set~contains_element.
contains = cond abap_bool(
when line_exists( me->elements[ table_line = element_to_be_found ] )
then abap_true
else abap_false ).
endmethod.
method set~get_size.
size = lines( me->elements ).
endmethod.
method set~is_equal.
if set_to_be_compared_with->get_size( ) ne me->set~get_size( ).
equal = abap_false.
return.
endif.
loop at me->elements into data(element).
if not set_to_be_compared_with->contains_element( element ).
equal = abap_false.
return.
endif.
endloop.
equal = abap_true.
endmethod.
method set~get_elements.
elements = me->elements.
endmethod.
method set~stringify.
stringified_set = cond string(
when me->elements is initial
then `∅`
when me->elements eq value stringtab( ( `∅` ) )
then `{ ∅ }`
else reduce string(
init result = `{ `
for element in me->elements
next result = cond string(
when element eq ``
then |{ result }∅, |
when strlen( element ) eq 1 and element ne `∅`
then |{ result }{ element }, |
else |{ result }\{{ element }\}, | ) ) ).
stringified_set = replace(
val = stringified_set
regex = `, $`
with = ` }`).
endmethod.
method build_powerset.
data(powerset_elements) = value stringtab( ( `` ) ).
loop at me->elements into data(element).
do lines( powerset_elements ) times.
if powerset_elements[ sy-index ] ne `∅`.
append |{ powerset_elements[ sy-index ] }{ element }| to powerset_elements.
else.
append element to powerset_elements.
endif.
enddo.
endloop.
powerset = new string_set( powerset_elements ).
endmethod.
endclass.
start-of-selection.
data(set1) = new string_set( ).
data(set2) = new string_set( ).
data(set3) = new string_set( ).
write: |𝑷( { set1->set~stringify( ) } ) -> { set1->build_powerset( )->set~stringify( ) }|, /.
set2->set~add_element( `∅` ).
write: |𝑷( { set2->set~stringify( ) } ) -> { set2->build_powerset( )->set~stringify( ) }|, /.
set3->set~add_element( `1` )->add_element( `2` )->add_element( `3` )->add_element( `3` )->add_element( `4`
)->add_element( `4` )->add_element( `4` ).
write: |𝑷( { set3->set~stringify( ) } ) -> { set3->build_powerset( )->set~stringify( ) }|, /.
</syntaxhighlight>
{{out}}
<pre>
𝑷( ∅ ) -> { ∅ }
𝑷( { ∅ } ) -> { ∅, {∅} }
𝑷( { 1, 2, 3, 4 } ) -> { ∅, 1, 2, {12}, 3, {13}, {23}, {123}, 4, {14}, {24}, {124}, {34}, {134}, {234}, {1234} }
</pre>
=={{header|Ada}}==
A solution (without recursion) that prints the power set of the n arguments passed by the command line. The idea is that the i'th bit of a natural between 0 and <math>2^n-1</math> indicates whether or not we should put the i'th element of the command line inside the set.
<syntaxhighlight lang="ada">
with Ada.Text_IO, Ada.Command_Line;
use Ada.Text_IO, Ada.Command_Line;
procedure
begin
Put ("{");
declare
k : natural
first : boolean := true;
begin
for i in 1..Argument_Count loop
if k mod 2 = 1 then
Put ((if first then "" else ",") & Argument (i));
first := false;
end if;
k := k / 2; -- we go to the next bit of "set"
end loop;
end;
Put_Line("}");
end loop;
end powerset;
</syntaxhighlight>
{{out}}
<pre>>./powerset a b c d
{}
{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>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68|Revision 1 - no extensions to language used}}
Line 110 ⟶ 302:
Requires: ALGOL 68g mk14.1+
<
PROC power set = ([]MEMBER s)[][]MEMBER:(
Line 136 ⟶ 328:
printf(($"set["d"] = "$,member, repr set, set[member],$l$))
OD
)</
{{out}}
<pre>
set[1] = ();
Line 148 ⟶ 340:
set[8] = (1, 2, 4);
</pre>
=={{header|APL}}==
{{works with|Dyalog APL}}
<syntaxhighlight lang="apl">ps←(↓∘⍉(2/⍨≢)⊤(⍳2*≢))(/¨)⊂</syntaxhighlight>
{{out}}
<!-- note: "line-height: 100%" makes Dyalog's boxed output look better.
Don't know why it wasn't already 100% though. -->
<pre style='line-height: 100%;'> ps 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││
└─┴─┴───┴─┴───┴───┴─────┴─┴───┴───┴─────┴───┴─────┴─────┴───────┴┘</pre>
<pre style='line-height: 100%;'> ps ⍬
┌┐
││
└┘</pre>
<pre style='line-height: 100%;'> ps ,⊂⍬
┌──┬┐
│┌┐││
│││││
│└┘││
└──┴┘</pre>
=={{header|AppleScript}}==
{{Trans|JavaScript}}
(functional composition examples)
{{Trans|Haskell}}
<syntaxhighlight lang="applescript">-- POWER SET -----------------------------------------------------------------
-- powerset :: [a] -> [[a]]
on powerset(xs)
script subSet
on |λ|(acc, x)
script cons
on |λ|(y)
{x} & y
end |λ|
end script
acc & map(cons, acc)
end |λ|
end script
foldr(subSet, {{}}, xs)
end powerset
-- TEST ----------------------------------------------------------------------
on run
script test
on |λ|(x)
set {setName, setMembers} to x
{setName, powerset(setMembers)}
end |λ|
end script
map(test, [¬
["Set [1,2,3]", {1, 2, 3}], ¬
["Empty set", {}], ¬
["Set containing only empty set", {{}}]])
--> {{"Set [1,2,3]", {{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}}},
--> {"Empty set", {{}}},
--> {"Set containing only empty set", {{}, {{}}}}}
end run
-- GENERIC FUNCTIONS ---------------------------------------------------------
-- foldr :: (a -> b -> a) -> a -> [b] -> a
on foldr(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from lng to 1 by -1
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldr
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="applescript">{{"Set [1,2,3]", {{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}}},
{"Empty set", {{}}},
{"Set containing only empty set", {{}, {{}}}}}</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">print powerset [1 2 3 4]</syntaxhighlight>
{{out}}
<pre>[2 3 4] [] [1 2 4] [1 2 3 4] [1 3 4] [1] [2] [1 3] [3 4] [4] [1 4] [3] [1 2] [2 3] [1 2 3] [2 4]</pre>
=={{header|ATS}}==
<syntaxhighlight lang="text">
(* ****** ****** *)
//
#include
"share/atspre_define.hats" // defines some names
#include
"share/atspre_staload.hats" // for targeting C
#include
"share/HATS/atspre_staload_libats_ML.hats" // for ...
//
(* ****** ****** *)
//
extern
fun
Power_set(xs: list0(int)): void
//
(* ****** ****** *)
// Helper: fast power function.
fun power(n: int, p: int): int =
if p = 1 then n
else if p = 0 then 1
else if p % 2 = 0 then power(n*n, p/2)
else n * power(n, p-1)
fun print_list(list: list0(int)): void =
case+ list of
| nil0() => println!(" ")
| cons0(car, crd) =>
let
val () = begin print car; print ','; end
val () = print_list(crd)
in
end
fun get_list_length(list: list0(int), length: int): int =
case+ list of
| nil0() => length
| cons0(car, crd) => get_list_length(crd, length+1)
fun get_list_from_bit_mask(mask: int, list: list0(int), result: list0(int)): list0(int) =
if mask = 0 then result
else
case+ list of
| nil0() => result
| cons0(car, crd) =>
let
val current: int = mask % 2
in
if current = 0 then
get_list_from_bit_mask(mask >> 1, crd, result)
else
get_list_from_bit_mask(mask >> 1, crd, list0_cons(car, result))
end
implement
Power_set(xs) = let
val len: int = get_list_length(xs, 0)
val pow: int = power(2, len)
fun loop(mask: int, list: list0(int)): void =
if mask > 0 && mask >= pow then ()
else
let
val () = print_list(get_list_from_bit_mask(mask, list, list0_nil()))
in
loop(mask+1, list)
end
in
loop(0, xs)
end
(* ****** ****** *)
implement
main0() =
let
val xs: list0(int) = cons0(1, list0_pair(2, 3))
in
Power_set(xs)
end (* end of [main0] *)
(* ****** ****** *)
</syntaxhighlight>
=={{header|AutoHotkey}}==
ahk [http://www.autohotkey.com/forum/viewtopic.php?t=44657&postdays=0&postorder=asc&start=147 discussion]
<
StringSplit a, a, `, ; a0 = #elements, a1,a2,... = elements of the set
Line 161 ⟶ 562:
t .= "}`n{" ; new subsets in new lines
}
MsgBox % RegExReplace(SubStr(t,1,StrLen(t)-1),",}","}")</
=={{header|AWK}}==
<syntaxhighlight lang="awk">cat power_set.awk
#!/usr/local/bin/gawk -f
# User defined function
function tochar(l,n, r) {
while (l) { n--; if (l%2 != 0) r = r sprintf(" %c ",49+n); l = int(l/2) }; return r
}
# For each input
{ for (i=0;i<=2^NF-1;i++) if (i == 0) printf("empty\n"); else printf("(%s)\n",tochar(i,NF)) }
</syntaxhighlight>
{{out}}
<pre>
$ gawk -f power_set.awk
1 2 3 4
empty
( 4 )
( 3 )
( 4 3 )
( 2 )
( 4 2 )
( 3 2 )
( 4 3 2 )
( 1 )
( 4 1 )
( 3 1 )
( 4 3 1 )
( 2 1 )
( 4 2 1 )
( 3 2 1 )
( 4 3 2 1 )
</pre>
=={{header|
==={{header|BBC BASIC}}===
The elements of a set are represented as the bits in an integer (hence the maximum size of set is 32).
<
PRINT FNpowerset(list$())
END
Line 181 ⟶ 618:
s$ += "},"
NEXT i%
= LEFT$(s$) + "}"</
{{out}}
<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|BQN}}==
<syntaxhighlight lang="bqn">P ← (⥊·↕2⥊˜≠)/¨<</syntaxhighlight>
{{out}}
<pre>
P 1‿2‿3‿4‿5
⟨ ⟨⟩ ⟨ 5 ⟩ ⟨ 4 ⟩ ⟨ 4 5 ⟩ ⟨ 3 ⟩ ⟨ 3 5 ⟩ ⟨ 3 4 ⟩ ⟨ 3 4 5 ⟩ ⟨ 2 ⟩ ⟨ 2 5 ⟩ ⟨ 2 4 ⟩ ⟨ 2 4 5 ⟩ ⟨ 2 3 ⟩ ⟨ 2 3 5 ⟩ ⟨ 2 3 4 ⟩ ⟨ 2 3 4 5 ⟩ ⟨ 1 ⟩ ⟨ 1 5 ⟩ ⟨ 1 4 ⟩ ⟨ 1 4 5 ⟩ ⟨ 1 3 ⟩ ⟨ 1 3 5 ⟩ ⟨ 1 3 4 ⟩ ⟨ 1 3 4 5 ⟩ ⟨ 1 2 ⟩ ⟨ 1 2 5 ⟩ ⟨ 1 2 4 ⟩ ⟨ 1 2 4 5 ⟩ ⟨ 1 2 3 ⟩ ⟨ 1 2 3 5 ⟩ ⟨ 1 2 3 4 ⟩ ⟨ 1 2 3 4 5 ⟩ ⟩
</pre>
=={{header|Bracmat}}==
<
= done todo first
. !arg:(?done.?todo)
Line 197 ⟶ 643:
)
& out$(powerset$(.1 2 3 4))
);</
{{out}}
<pre> 1 2 3 4
, 1 2 3
Line 218 ⟶ 664:
=={{header|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}}
</syntaxhighlight>
=={{header|C}}==
<
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;
}</syntaxhighlight>
{{out}}
<pre>
% ./a.out 1 2
[ ]
[ 3 ]
[ 2 ]
[ 3 2 ]
[ 1 ]
[ 3 1 ]
[ 2 1 ]
[ 3 2 1 ]
</pre>
=={{header|C sharp|C#}}==
<syntaxhighlight 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()));
}
</syntaxhighlight>
{
<pre>
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
</pre>
An alternative implementation for an arbitrary number of elements:
<syntaxhighlight 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 }))));
}
</syntaxhighlight>
Non-recursive version
<syntaxhighlight lang="csharp">
using System;
class Powerset
{
static int count = 0, n = 4;
static int [] buf = new int [n];
static void Main()
{
int ind = 0;
int n_1 = n - 1;
for (;;)
{
for (int i = 0; i <= ind; ++i) Console.Write("{0, 2}", buf [i]);
Console.WriteLine();
count++;
if (buf [ind] < n_1) { ind++; buf [ind] = buf [ind - 1] + 1; }
else if (ind > 0) { ind--; buf [ind]++; }
else break;
}
Console.WriteLine("n=" + n + " count=" + count);
}
}
</syntaxhighlight>
----------------
Recursive version
<syntaxhighlight lang="csharp">
using System;
class Powerset
{
static int n = 4;
static int [] buf = new int [n];
static void Main()
{
rec(0, 0);
}
static void rec(int ind, int begin)
{
for (int i = begin; i < n; i++)
{
buf [ind] = i;
for (int j = 0; j <= ind; j++) Console.Write("{0, 2}", buf [j]);
Console.WriteLine();
rec(ind + 1, buf [ind] + 1);
}
}
}</syntaxhighlight>
=={{header|C++}}==
Line 273 ⟶ 831:
=== Non-recursive version ===
<
#include <set>
#include <vector>
Line 350 ⟶ 908:
std::cout << " }\n";
}
}</
{{out}}
<pre>
{ }
Line 371 ⟶ 929:
{ 7 }
</pre>
==== C++14 version ====
This simplified version has identical output to the previous code.
<syntaxhighlight lang="cpp">
#include <set>
#include <iostream>
template <class S>
auto powerset(const S& s)
{
std::set<S> ret;
ret.emplace();
for (auto&& e: s) {
std::set<S> rs;
for (auto x: ret) {
x.insert(e);
rs.insert(x);
}
ret.insert(begin(rs), end(rs));
}
return ret;
}
int main()
{
std::set<int> s = {2, 3, 5, 7};
auto pset = powerset(s);
for (auto&& subset: pset) {
std::cout << "{ ";
char const* prefix = "";
for (auto&& e: subset) {
std::cout << prefix << e;
prefix = ", ";
}
std::cout << " }\n";
}
}
</syntaxhighlight>
=== Recursive version ===
<
#include <set>
Line 399 ⟶ 998:
return powerset(s, s.size());
}
</syntaxhighlight>
=={{header|
<syntaxhighlight 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))</syntaxhighlight>
'''Alternate solution''', with no dependency on third-party library:
<syntaxhighlight lang="clojure">(defn powerset [coll]
(reduce (fn [a x]
(into a (map #(conj % x)) a))
#{#{}} coll))
(powerset #{1 2 3})</syntaxhighlight>
<syntaxhighlight lang="clojure">#{#{} #{1} #{2} #{1 2} #{3} #{1 3} #{2 3} #{1 2 3}}</syntaxhighlight>
'''Using bit-test''':
see: https://clojuredocs.org/clojure.core/bit-test#example-5d401face4b0ca44402ef78b
<syntaxhighlight lang="clojure">(defn powerset [coll]
(let [cnt (count coll)
bits (Math/pow 2 cnt)]
(for [i (range bits)]
(for [j (range i)
:while (< j cnt)
:when (bit-test i j)]
(nth coll j)))))
(powerset [1 2 3])</syntaxhighlight>
<syntaxhighlight lang="clojure">(() (1) (2) (1 2) (3) (1 3) (2 3) (1 2 3))</syntaxhighlight>
=={{header|CoffeeScript}}==
<
print_power_set = (arr) ->
console.log "POWER SET of #{arr}"
Line 496 ⟶ 1,061:
print_power_set [4, 2, 1]
print_power_set ['dog', 'c', 'b', 'a']
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="text">
> coffee power_set.coffee
POWER SET of
Line 528 ⟶ 1,093:
[ 'dog', 'c', 'b' ]
[ 'dog', 'c', 'b', 'a' ]
</syntaxhighlight>
=={{header|ColdFusion}}==
Port from the [[#JavaScript|JavaScript]] version,
compatible with ColdFusion 8+ or Railo 3+
<syntaxhighlight lang="javascript">public array function powerset(required array data)
{
var ps = [""];
Line 550 ⟶ 1,116:
}
var res = powerset([1,2,3,4]);</
{{out}}
<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}}==
<
(if s (mapcan (lambda (x) (list (cons (car s) x) x))
(powerset (cdr s)))
'(())))</syntaxhighlight>
{{out}}
> (powerset '(l i s p))
((L I S P) (I S P) (L S P) (S P) (L I P) (I P) (L P) (P) (L I S) (I S) (L S) (S) (L I) (I) (L) NIL)
<syntaxhighlight lang="lisp">(defun power-set (s)
(reduce #'(lambda (item ps)
(append (mapcar #'(lambda (e) (cons item e))
Line 563 ⟶ 1,138:
s
:from-end t
:initial-value '(())))</
{{out}}
>(power-set '(1 2 3))
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) NIL)
Line 570 ⟶ 1,145:
Alternate, more recursive (same output):
<
(if (null l)
(list nil)
(let ((prev (powerset (cdr l))))
(append (mapcar #'(lambda (elt) (cons (car l) elt)) prev)
prev))))</
Imperative-style using LOOP:
<
(loop for i below (expt 2 (length xs)) collect
(loop for j below i for x in xs if (logbitp j i) collect x)))</
{{out}}
>(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.
<
(let ((pow-set (list nil)))
(dolist (element (reverse list) pow-set)
(dolist (set pow-set)
(push (cons element set) pow-set)))))</
{{out}}
>(power-set '(1 2 3))
((1) (1 3) (1 2 3) (1 2) (2) (2 3) (3) NIL)
=={{header|D}}==
This implementation defines a range which *lazily* enumerates the power set.
<syntaxhighlight lang="d">import std.algorithm;
import std.range;
auto powerSet(R)(R r)
{
return
(1L<<r.length)
.iota
.map!(i =>
r.enumerate
.filter!(t => (1<<t[0]) & i)
.map!(t => t[1])
);
}
unittest
{
int[] emptyArr;
assert(emptyArr.powerSet.equal!equal([emptyArr]));
assert(emptyArr.powerSet.powerSet.equal!(equal!equal)([[], [emptyArr]]));
}
void main(string[] args)
{
import std.stdio;
args[1..$].powerSet.each!writeln;
}</syntaxhighlight>
An alternative version, which implements the range construct from scratch:
<syntaxhighlight lang="d">import std.range;
if (isRandomAccessRange!R)
{
R r;
size_t position;
struct PowerSetItem
{
R r;
size_t position;
private void advance()
{
while (!(position & 1))
{
r.popFront();
position >>= 1;
}
}
@property bool empty() { return position == 0; }
@property auto front()
{
advance();
return r.front;
}
void popFront()
{
advance();
r.popFront();
position >>= 1;
}
}
@property bool empty() { return position == (1 << r.length); }
@property PowerSetItem front() { return PowerSetItem(r.save, position); }
void popFront() { position++; }
}
auto powerSet(R)(R r) { return PowerSet!R(r); }</syntaxhighlight>
{{out}}
<pre>$ rdmd powerset a b c
[]
["a"]
["b"]
["a", "b"]
["c"]
["a", "c"]
["b", "c"]
["a", "b", "c"]</pre>
=== Alternative: using folds ===
An almost verbatim translation of the Haskell code in D.
Since D doesn't foldr, I've also copied Haskell's foldr implementation here.
Main difference from the Haskell:
#It isn't lazy (but it could be made so by implementing this as a generator)
Main differences from the version above:
#It isn't lazy
#It doesn't rely on integer bit fiddling, so it should work on arrays larger than size_t.
<syntaxhighlight lang="d">
// Haskell definition:
// foldr f z [] = z
// foldr f z (x:xs) = x `f` foldr f z xs
S foldr(T, S)(S function(T, S) f, S z, T[] rest) {
return (rest.length == 0) ? z : f(rest[0], foldr(f, z, rest[1..$]));
}
// Haskell definition:
//powerSet = foldr (\x acc -> acc ++ map (x:) acc) [[]]
T[][] powerset(T)(T[] set) {
import std.algorithm;
import std.array;
// Note: The types before x and acc aren't needed, so this could be made even more concise, but I think it helps
// to make the algorithm slightly clearer.
return foldr( (T x, T[][] acc) => acc ~ acc.map!(accx => x ~ accx).array , [[]], set );
}
</syntaxhighlight>
=={{header|Déjà Vu}}==
Line 654 ⟶ 1,294:
In Déjà Vu, sets are dictionaries with all values <code>true</code> and the default set to <code>false</code>.
<
local :out [ set{ } ]
for value in keys s:
Line 663 ⟶ 1,303:
out
!. powerset set{ 1 2 3 4 }</
{{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|Delphi}}==
{{libheader| System.SysUtils}}
{{Trans|C#}}
<syntaxhighlight lang="delphi">
program Power_set;
{$APPTYPE CONSOLE}
uses
System.SysUtils;
const
n = 4;
var
buf: TArray<Integer>;
procedure rec(ind, bg: Integer);
begin
for var i := bg to n - 1 do
begin
buf[ind] := i;
for var j := 0 to ind do
write(buf[j]: 2);
writeln;
rec(ind + 1, buf[ind] + 1);
end;
end;
begin
SetLength(buf, n);
rec(0,0);
{$IFNDEF UNIX}readln;{$ENDIF}
end.</syntaxhighlight>
=={{header|Dyalect}}==
{{trans|C#}}
<syntaxhighlight lang="dyalect">let n = 4
let buf = Array.Empty(n)
func rec(idx, begin) {
for i in begin..<n {
buf[idx] = i
for j in 0..idx {
print("{0, 2}".Format(buf[j]), terminator: "")
}
print("")
rec(idx + 1, buf[idx] + 1)
}
}
rec(0, 0)</syntaxhighlight>
=={{header|E}}==
<
def powerset(s) {
Line 678 ⟶ 1,373:
})
}
}</
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|EchoLisp}}==
<syntaxhighlight lang="scheme">
(define (set-cons a A)
(make-set (cons a A)))
(define (power-set e)
(cond ((null? e)
(make-set (list ∅)))
(else (let [(ps (power-set (cdr e)))]
(make-set
(append ps (map set-cons (circular-list (car e)) ps)))))))
(define B (make-set ' ( 🍎 🍇 🎂 🎄 )))
(power-set B)
→ { ∅ { 🍇 } { 🍇 🍎 } { 🍇 🍎 🎂 } { 🍇 🍎 🎂 🎄 } { 🍇 🍎 🎄 } { 🍇 🎂 } { 🍇 🎂 🎄 }
{ 🍇 🎄 } { 🍎 } { 🍎 🎂 } { 🍎 🎂 🎄 } { 🍎 🎄 } { 🎂 } { 🎂 🎄 } { 🎄 } }
;; The Von Neumann universe
(define V0 (power-set null)) ;; null and ∅ are the same
→ { ∅ }
(define V1 (power-set V0))
→ { ∅ { ∅ } }
(define V2 (power-set V1))
→ { ∅ { ∅ } { ∅ { ∅ } } { { ∅ } } }
(define V3 (power-set V2))
→ { ∅ { ∅ } { ∅ { ∅ } } …🔃 )
(length V3) → 16
(define V4 (power-set V3))
(length V4) → 65536
;; length V5 = 2^65536 : out of bounds
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Erlang}}
<syntaxhighlight lang="elixir">defmodule RC do
use Bitwise
def powerset1(list) do
n = length(list)
max = round(:math.pow(2,n))
for i <- 0..max-1, do: (for pos <- 0..n-1, band(i, bsl(1, pos)) != 0, do: Enum.at(list, pos) )
end
def powerset2([]), do: [[]]
def powerset2([h|t]) do
pt = powerset2(t)
(for x <- pt, do: [h|x]) ++ pt
end
def powerset3([]), do: [[]]
def powerset3([h|t]) do
pt = powerset3(t)
powerset3(h, pt, pt)
end
defp powerset3(_, [], acc), do: acc
defp powerset3(x, [h|t], acc), do: powerset3(x, t, [[x|h] | acc])
end
IO.inspect RC.powerset1([1,2,3])
IO.inspect RC.powerset2([1,2,3])
IO.inspect RC.powerset3([1,2,3])
IO.inspect RC.powerset1([])
IO.inspect RC.powerset1(["one"])</syntaxhighlight>
{{out}}
<pre>
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
[[1], [1, 3], [1, 2, 3], [1, 2], [2], [2, 3], [3], []]
[[]]
[[], ["one"]]
</pre>
=={{header|Erlang}}==
Line 697 ⟶ 1,468:
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
</pre>
<
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)].</
{{out}}
<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:
<
powerset([H|T]) -> PT = powerset(T),
[ [H|X] || X <- PT ] ++ PT.</
or even more efficient version:
<
powerset([H|T]) -> PT = powerset(T),
powerset(H, PT, PT).
powerset(_, [], Acc) -> Acc;
powerset(X, [H|T], Acc) -> powerset(X, T, [[X|H]|Acc]).</
=={{header|F Sharp|F#}}==
almost exact copy of OCaml version
<
let subsets xs = List.foldBack (fun x rest -> rest @ List.map (fun ys -> x::ys) rest) xs [[]]
</syntaxhighlight>
alternatively with list comprehension
<syntaxhighlight lang="fsharp">
let rec pow =
function
| [] -> [[]]
| x::xs -> [for i in pow xs do yield! [i;x::i]]
</syntaxhighlight>
=={{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.
<
IN: powerset
: add ( set elt -- newset ) 1array <hash-set> union ;
: powerset ( set -- newset ) members { HS{ } } [ dupd [ add ] curry map append ] reduce <hash-set> ;</
Usage:
<
HS{
HS{ 1 2 3 4 }
Line 750 ⟶ 1,531:
HS{ 1 3 4 }
HS{ 2 3 4 }
}</
=={{header|Forth}}==
{{works with|4tH|3.61.0}}.
{{trans|C}}
<
: .set begin dup while ?print >r 1+ r> 1 rshift repeat drop drop ;
: .powerset 0 do ." ( " 1 i .set ." )" cr loop ;
Line 762 ⟶ 1,543:
: powerset 1 argn check-none check-size 1- lshift .powerset ;
powerset</
{{out}}
<pre>
$ 4th cxq powerset.4th 1 2 3 4
Line 783 ⟶ 1,564:
( 1 2 3 4 )
</pre>
=={{header|FreeBASIC}}==
Los elementos de un conjunto se representan como bits en un número entero (por lo tanto, el tamaño máximo del conjunto es 32).
<syntaxhighlight lang="freebasic">Function ConjuntoPotencia(set() As String) As String
If Ubound(set,1) > 31 Then Print "Set demasiado grande para representarlo como un entero" : Exit Function
If Ubound(set,1) < 0 Then Print "{}": Exit Function ' Set vacío
Dim As Integer i, j
Dim As String s = "{"
For i = Lbound(set) To (2 Shl Ubound(set,1)) - 1
s += "{"
For j = Lbound(set) To Ubound(set,1)
If i And (1 Shl j) Then s += set(j) + ","
Next j
If Right(s,1) = "," Then s = Left(s,Len(s)-1)
s += "},"
Next i
Return Left(s,Len(s)-1) + "}"
End Function
Print "El power set de [1, 2, 3, 4] comprende:"
Dim As String set(3) = {"1", "2", "3", "4"}
Print ConjuntoPotencia(set())
Print !"\nEl power set de [] comprende:"
Dim As String set0()
Print ConjuntoPotencia(set0())
Print "El power set de [[]] comprende:"
Dim As String set1(0) = {""}
Print ConjuntoPotencia(set1())
Sleep</syntaxhighlight>
{{out}}
<pre>
El power set de [1, 2, 3, 4] comprende:
{{},{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}}
El power set de [] comprende:
{}
El power set de [[]] comprende:
{{},{}}
</pre>
=={{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. If called with a set, the results are sets.
<
a = new set[1,2,3,4]
a.subsets[]
</syntaxhighlight>
=={{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.
<syntaxhighlight lang="funl">def powerset( s ) = s.subsets().toSet()</syntaxhighlight>
The powerset function could be implemented in FunL directly as:
<syntaxhighlight lang="funl">def
powerset( {} ) = {{}}
powerset( s ) =
acc = powerset( s.tail() )
acc + map( x -> {s.head()} + x, acc )</syntaxhighlight>
or, alternatively as:
<syntaxhighlight lang="funl">import lists.foldr
def powerset( s ) = foldr( \x, acc -> acc + map( a -> {x} + a, acc), {{}}, s )
println( powerset({1, 2, 3, 4}) )</syntaxhighlight>
{{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|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Power_set}}
'''Solution'''
No program needed. Power set is intrinsically supported in Fōrmulæ.
'''Case 1.''' Power set of the set {1, 2, 3, 4}
[[File:Fōrmulæ - Power set 01.png]]
[[File:Fōrmulæ - Power set 02.png]]
'''Case 2.''' The power set of the empty set is the set which contains itself.
[[File:Fōrmulæ - Power set 03.png]]
[[File:Fōrmulæ - Power set 04.png]]
'''Case 3.''' 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
[[File:Fōrmulæ - Power set 05.png]]
[[File:Fōrmulæ - Power set 06.png]]
'''Case 4.''' Even when it is intrinsically supported, a program can be written:
[[File:Fōrmulæ - Power set 07.png]]
[[File:Fōrmulæ - Power set 08.png]]
[[File:Fōrmulæ - Power set 09.png]]
=={{header|GAP}}==
<
Combinations([1, 2, 3]);
# [ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 2, 3 ], [ 3 ] ]
Line 799 ⟶ 1,682:
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 ] ]</
=={{header|Go}}==
Line 807 ⟶ 1,690:
set add method. Adding elements with the add method ensures the uniqueness property.
<syntaxhighlight lang="go">package main
import (
"fmt"
"strconv"
"strings"
)
Line 820 ⟶ 1,703:
// element is an interface, allowing different kinds of elements to be
// implemented and stored in sets.
type
// 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).
// String result is used only for printable output. Given a, b where
// a.eq(b), it is not required that a.String() == b.String().
}
// integer type satisfying element interface
type
func (i
return ok
}
func (i
return strconv.Itoa(int(i))
}
// a set
//
type set []
// uniqueness of elements can be ensured by using add method
func (s *set)
if !s.
*s = append(*s, e)
}
}
func (s *set)
for _, ex := range *s {
if e.
return true
}
Line 864 ⟶ 1,745:
}
func (s set) ok() bool {
for i, e0 := range s {
for _, e1 := range s[i+1:] {
if e0.Eq(e1) {
return false
}
}
}
return true
}
// elem.Eq
func (s set) Eq(e elem) bool {
t, ok := e.(set)
if !ok {
Line 874 ⟶ 1,766:
}
for _, se := range s {
if !t.
return false
}
Line 881 ⟶ 1,773:
}
// elem.String
func (s set) String() string {
}
var buf
buf.WriteRune('{')
for i, e := range s {
if i > 0 {
buf.WriteRune(',')
}
}
return buf.String()
}
Line 899 ⟶ 1,796:
var u set
for _, er := range r {
u = append(u, append(er[:len(er):len(er)], es))
}
r = append(r, u...)
Line 908 ⟶ 1,806:
func main() {
var s set
for _, i := range []
s.
}
fmt.Println(" s:", s, "length:", len(s))
ps := s.powerSet()
fmt.Println(" 𝑷(s):", ps, "length:", len(ps))
fmt.Println("\n(extra credit)")
var empty set
fmt.Println(" empty:", empty, "len:", len(empty))
ps = empty.powerSet()
fmt.Println(" 𝑷(∅):", ps, "len:", len(ps))
ps = ps.powerSet()
fmt.Println("𝑷(𝑷(∅)):", ps, "len:", len(ps))
fmt.Println("\n(regression test for earlier bug)")
s = set{Int(1), Int(2), Int(3), Int(4), Int(5)}
fmt.Println(" s:", s, "length:", len(s), "ok:", s.ok())
ps = s.powerSet()
fmt.Println(" 𝑷(s):", "length:", len(ps), "ok:", ps.ok())
for _, e := range ps {
if !e.(set).ok() {
panic("invalid set in ps")
}
}
}</syntaxhighlight>
{{out}}
<pre>
s: {1
𝑷(s): {∅,{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
(extra credit)
empty: ∅ len: 0
𝑷(∅): {∅} len: 1
𝑷(𝑷(∅)): {∅,{∅}} len: 2
(regression test for earlier bug)
s: {1,2,3,4,5} length: 5 ok: true
𝑷(s): length: 32 ok: true
</pre>
=={{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'''.
<syntaxhighlight lang
def powerSetRec(head, tail) {
if (!tail) return [head]
powerSetRec(head, tail.tail()) + powerSetRec(head + [tail.head()], tail.tail())
}
def powerSet
</syntaxhighlight>
Test program:
<syntaxhighlight lang="groovy">
def vocalists = [ 'C', 'S', 'N', 'Y' ] as Set
println
println powerSet(vocalists)
</syntaxhighlight>
{{out}}
<pre>
[C, S, N, Y]
[[], [Y], [N], [N, Y], [S], [S, Y], [S, N], [S, N, Y], [C], [C, Y], [C, N], [C, N, Y], [C, S], [C, S, Y], [C, S, N], [C, S, N, Y]]
</pre>
=={{header|Haskell}}==
<
import Control.Monad
Line 961 ⟶ 1,879:
listPowerset :: [a] -> [[a]]
listPowerset = filterM (const [True, False])</
<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'''
<
powerset (head:tail) = acc ++ map (head:) acc where acc = powerset tail</
or
<syntaxhighlight lang="haskell">powerSet :: [a] -> [[a]]
powerSet = foldr (\x acc -> acc ++ map (x:) acc) [[]]</syntaxhighlight>
which could also be understood, in point-free terms, as:
<syntaxhighlight lang="haskell">powerSet :: [a] -> [[a]]
powerSet = foldr ((mappend <*>) . fmap . (:)) (pure [])</syntaxhighlight>
Examples:
Line 984 ⟶ 1,908:
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.
<
type Set=Set.Set
unionAll :: (Ord a) => Set (Set a) -> Set a
Line 998 ⟶ 1,922:
powerSet :: (Ord a) => Set a -> Set (Set a)
powerSet = (Set.fold (slift Set.union) (Set.singleton Set.empty)) . Set.map makeSet</
Usage:
<syntaxhighlight lang="haskell">
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]]</
=={{header|Icon}} and {{header|Unicon}}==
Line 1,012 ⟶ 1,936:
The following version returns a set containing the powerset:
<syntaxhighlight lang="icon">
procedure power_set (s)
result := set ()
Line 1,027 ⟶ 1,951:
return result
end
</syntaxhighlight>
To test the above procedure:
<syntaxhighlight lang="icon">
procedure main ()
every s := !power_set (set(1,2,3,4)) do { # requires '!' to generate items in the result set
Line 1,039 ⟶ 1,963:
}
end
</syntaxhighlight>
{{out}}
<pre>
[ 3 ]
Line 1,065 ⟶ 1,989:
An alternative version, which generates each item in the power set in turn:
<syntaxhighlight lang="icon">
procedure power_set (s)
if *s = 0
Line 1,085 ⟶ 2,009:
}
end
</syntaxhighlight>
=={{header|J}}==
There are a [http://www.jsoftware.com/jwiki/Essays/Power_Set number of ways] to generate a power set in J. Here's one:
<
For example:
<
E
Line 1,100 ⟶ 2,024:
AE
AC
ACE</
In the typical use, this operation makes sense on collections of unique elements.
<
1 2 3
#ps 1 2 3 2 1
32
#ps ~.1 2 3 2 1
8</
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.
Line 1,118 ⟶ 2,042:
[[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.
<
{
if(n<0)
Line 1,142 ⟶ 2,066:
ps.addAll(tmp);
return ps;
}</
===Iterative===
The iterative implementation of the above idea. Each subset is in the order that the element appears in the input list. This implementation preserves the input.
<
public static <T> List<List<T>> powerset(Collection<T> list) {
List<List<T>> ps = new ArrayList<List<T>>();
Line 1,170 ⟶ 2,094:
return ps;
}
</syntaxhighlight>
===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.
<
LinkedList<T> A){
LinkedList<LinkedList<T>> ans= new LinkedList<LinkedList<T>>();
int ansSize = (int)Math.pow(2, A.size());
for(
String bin= Integer.
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){
Line 1,189 ⟶ 2,113:
}
return ans;
}</
=={{header|JavaScript}}==
===ES5===
====Iteration====
Uses a JSON stringifier from http://www.json.org/js.html
{{works with|SpiderMonkey}}
<
var ps = [[]];
for (var i=0; i < ary.length; i++) {
Line 1,208 ⟶ 2,135:
load('json2.js');
print(JSON.stringify(res));</
{{out}}
<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>
====Functional composition====
{{trans|Haskell}}
<syntaxhighlight lang="javascript">(function () {
// translating: powerset = foldr (\x acc -> acc ++ map (x:) acc) [[]]
function powerset(xs) {
return xs.reduceRight(function (a, x) {
return a.concat(a.map(function (y) {
return [x].concat(y);
}));
}, [[]]);
}
// TEST
return {
'[1,2,3] ->': powerset([1, 2, 3]),
'empty set ->': powerset([]),
'set which contains only the empty set ->': powerset([[]])
}
})();</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="javascript">{
"[1,2,3] ->":[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]],
"empty set ->":[[]],
"set which contains only the empty set ->":[[], [[]]]
}</syntaxhighlight>
===ES6===
<syntaxhighlight lang="javascript">(() => {
'use strict';
// powerset :: [a] -> [[a]]
const powerset = xs =>
xs.reduceRight((a, x) => [...a, ...a.map(y => [x, ...y])], [
[]
]);
// TEST
return {
'[1,2,3] ->': powerset([1, 2, 3]),
'empty set ->': powerset([]),
'set which contains only the empty set ->': powerset([
[]
])
};
})()</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="javascript">{"[1,2,3] ->":[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]],
"empty set ->":[[]],
"set which contains only the empty set ->":[[], [[]]]}</syntaxhighlight>
=={{header|jq}}==
<syntaxhighlight lang="jq">def powerset:
reduce .[] as $i ([[]];
reduce .[] as $r (.; . + [$r + [$i]]));</syntaxhighlight>
Example:
[range(0;10)]|powerset|length
# => 1024
Extra credit:
<syntaxhighlight lang="jq">
# The power set of the empty set:
[] | powerset
# => [[]]
# The power set of the set which contains only the empty set:
[ [] ] | powerset
# => [[],[[]]]</syntaxhighlight>
====Recursive version====
<syntaxhighlight lang="jq">def powerset:
if length == 0 then [[]]
else .[0] as $first
| (.[1:] | powerset)
| map([$first] + . ) + .
end;</syntaxhighlight>
Example:
[1,2,3]|powerset
# => [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
=={{header|Julia}}==
<syntaxhighlight lang
function powerset(x::Vector{T})::Vector{Vector{T}} where T
for elem in x, j in eachindex(result)
push!(result, [result[j] ; elem])
result
end
</syntaxhighlight>
{{Out}}
<pre>
julia> show(powerset([1,2,3]))
[Int64[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
</pre>
===Non-Mutating Solution===
<syntaxhighlight lang="julia">
using Base.Iterators
function bitmask(u, max_size)
res = BitArray(undef, max_size)
res.chunks[1] = u%UInt64
res
end
function powerset(input_collection::Vector{T})::Vector{Vector{T}} where T
num_elements = length(input_collection)
bitmask_map(x) = Iterators.map(y -> bitmask(y, num_elements), x)
getindex_map(x) = Iterators.map(y -> input_collection[y], x)
UnitRange(0, (2^num_elements)-1) |>
bitmask_map |>
getindex_map |>
collect
end
</syntaxhighlight>
{{Out}}
<pre>
julia> show(powerset([1,2,3]))
[Int64[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
</pre>
=={{header|K}}==
<syntaxhighlight lang="k">
ps:{x@&:'+2_vs!_2^#x}
</syntaxhighlight>
Usage:
<syntaxhighlight lang="k">
ps "ABC"
(""
Line 1,240 ⟶ 2,288:
"AB"
"ABC")
</syntaxhighlight>
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">// purely functional & lazy version, leveraging recursion and Sequences (a.k.a. streams)
fun <T> Set<T>.subsets(): Sequence<Set<T>> =
when (size) {
0 -> sequenceOf(emptySet())
else -> {
val head = first()
val tail = this - head
tail.subsets() + tail.subsets().map { setOf(head) + it }
}
}
// if recursion is an issue, you may change it this way:
fun <T> Set<T>.subsets(): Sequence<Set<T>> = sequence {
when (size) {
0 -> yield(emptySet<T>())
else -> {
val head = first()
val tail = this@subsets - head
yieldAll(tail.subsets())
for (subset in tail.subsets()) {
yield(setOf(head) + subset)
}
}
}
}
</syntaxhighlight>
{{out}}
<pre>
Power set of setOf(1, 2, 3, 4) comprises:
[]
[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]
Power set of emptySet<Any>() comprises:
[]
Power set of setOf(emptySet<Any>()) comprises:
[]
[[]]
</pre>
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
{def powerset
{def powerset.r
{lambda {:ary :ps :i}
{if {= :i {A.length :ary}}
then :ps
else {powerset.r :ary
{powerset.rr :ary :ps {A.length :ps} :i 0}
{+ :i 1}} }}}
{def powerset.rr
{lambda {:ary :ps :len :i :j}
{if {= :j :len}
then :ps
else {powerset.rr :ary
{A.addlast! {A.concat {A.get :j :ps}
{A.new {A.get :i :ary}}}
:ps}
:len
:i
{+ :j 1}} }}}
{lambda {:ary}
{A.new {powerset.r :ary {A.new {A.new}} 0}}}}
-> powerset
{powerset {A.new 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]]]
</syntaxhighlight>
=={{header|Logo}}==
<
if empty? :set [output [[]]]
localmake "rest powerset butfirst :set
Line 1,250 ⟶ 2,389:
show powerset [1 2 3]
[[1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []]</
=={{header|Logtalk}}==
<
:- public(powerset/2).
Line 1,277 ⟶ 2,416:
reverse(Tail, [Head| List], Reversed).
:- end_object.</
Usage example:
<
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</
=={{header|Lua}}==
<
--returns the powerset of s, out of order.
function powerset(s, start)
Line 1,319 ⟶ 2,458:
return ret
end
</syntaxhighlight>
=={{header|M4}}==
<
`ifelse($#, 0, ``$0'',
eval($2 <= $3), 1,
Line 1,343 ⟶ 2,482:
`{powerpart(0, substr(`$1', 1, eval(len(`$1') - 2)))}')dnl
dnl
powerset(`{a,b,c}')</
{{out}}
<pre>
{{},{a},{a,b},{a,b,c},{a,c},{b},{b,c},{c}}
</pre>
=={{header|
<syntaxhighlight lang="maple">
combinat:-powerset({1,2,3,4});
</syntaxhighlight>
{{out}}
<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}}
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
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:
<syntaxhighlight lang="mathematica">Subsets[{a, b, c}]</syntaxhighlight>
gives:
<
Subsets[list, {n, Infinity}] gives all the subsets that have n elements or more.
Line 1,367 ⟶ 2,520:
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.
<
pset = cell(size(theSet)); %Preallocate memory
Line 1,384 ⟶ 2,537:
end
end</
Sample Usage:
Powerset of the set of the empty set.
<
ans =
{} {1x1 cell} %This is the same as { {},{{}} }</
Powerset of { {1,2},3 }.
<
ans =
{1x0 cell} {1x1 cell} {1x1 cell} {1x2 cell} %This is the same as { {},{{1,2}},{3},{{1,2},3} }</
=={{header|Maxima}}==
<
/* {{}, {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}} */</
=={{header|Nim}}==
<syntaxhighlight lang="nim">import sets, hashes
proc hash(x: HashSet[int]): Hash =
var h = 0
for i in x: h = h !& hash(i)
result = !$h
proc powerset[T](inset: HashSet[T]): HashSet[HashSet[T]] =
result.incl(initHashSet[T]()) # Initialized with empty set.
for val in inset:
let previous = result
for aSet in previous:
var newSet = aSet
newSet.incl(val)
result.incl(newSet)
echo powerset([1,2,3,4].toHashSet())</syntaxhighlight>
{{out}}
<pre>{{4, 3, 1}, {3, 2, 1}, {3}, {3, 1}, {2}, {4, 3, 2, 1}, {}, {4, 2}, {4, 2, 1}, {4, 3, 2}, {1}, {3, 2}, {4, 3}, {4}, {4, 1}, {2, 1}}
</pre>
=={{header|Objective-C}}==
<
+ (NSArray *)powerSetForArray:(NSArray *)array {
Line 1,416 ⟶ 2,592:
for (int itemIndex = 0; itemIndex < array.count; itemIndex++) {
if((subsetIndex >> itemIndex) & 0x1) {
[subset addObject:
}
}
[subsets addObject:subset];
}
return subsets;
}</
=={{header|OCaml}}==
Line 1,429 ⟶ 2,604:
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.
<
struct
Line 1,445 ⟶ 2,620:
;;
end;; (* PowerSet *)</
version for lists:
<
=={{header|OPL}}==
<syntaxhighlight lang="opl">
{string} s={"A","B","C","D"};
range r=1.. ftoi(pow(2,card(s)));
Line 1,462 ⟶ 2,636:
writeln(s2);
}
</syntaxhighlight>
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"}]
</syntaxhighlight>
=={{header|Oz}}==
Oz has a library for finite set constraints. Creating a power set is a trivial application of that:
<
%% Given a set as a list, returns its powerset (again as a list)
fun {Powerset Set}
Line 1,495 ⟶ 2,664:
end
in
{Inspect {Powerset [1 2 3 4]}}</
A more convential implementation without finite set constaints:
<
case Set of nil then [nil]
[] H|T thens
Line 1,505 ⟶ 2,674:
{Append Acc {Map Acc fun {$ A} H|A end}}
end
end</
=={{header|PARI/GP}}==
<
{{works with|PARI/GP|2.10.0+}}
The <code>forsubset</code> iterator was added in version 2.10.0 to efficiently iterate over combinations and power sets.
<syntaxhighlight lang="parigp">S=["a","b","c"]
forsubset(#S,s,print1(vecextract(S,s)" "))</syntaxhighlight>
{{out}}
<pre>[] ["a"] ["b"] ["c"] ["a", "b"] ["a", "c"] ["b", "c"] ["a", "b", "c"]</pre>
=={{header|PascalABC.NET}}==
<syntaxhighlight lang="delphi">
function AllSubSets<T>(a: array of T; i: integer; lst: List<T>): sequence of List<T>;
begin
if i = a.Length then
begin
yield lst;
exit;
end;
lst.Add(a[i]);
yield sequence AllSubSets(a, i + 1, lst);
lst.RemoveAt(lst.Count-1);
yield sequence AllSubSets(a, i + 1, lst);
end;
begin
AllSubSets(Arr(1..4),0,new List<integer>).Print;
end.
</syntaxhighlight>
{{out}}
<pre>
[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] []
</pre>
=={{header|Perl}}==
Perl does not have a built-in set data-type. However, you can...
=== Module: [https://metacpan.org/pod/Algorithm::Combinatorics Algorithm::Combinatorics] ===
This module has an iterator over the power set. Note that it does not enforce that the input array is a set (no duplication). If each subset is processed immediately, this has an advantage of very low memory use.
<syntaxhighlight lang="perl">use Algorithm::Combinatorics "subsets";
my @S = ("a","b","c");
my @PS;
my $iter = subsets(\@S);
while (my $p = $iter->next) {
push @PS, "[@$p]"
}
say join(" ",@PS);</syntaxhighlight>
{{out}}
<pre>[a b c] [b c] [a c] [c] [a b] [b] [a] []</pre>
=== Module: [https://metacpan.org/pod/ntheory ntheory] ===
{{libheader|ntheory}}
The simplest solution is to use the one argument version of the combination iterator, which iterates over the power set.
<syntaxhighlight lang="perl">use ntheory "forcomb";
my @S = qw/a b c/;
forcomb { print "[@S[@_]] " } scalar(@S);
print "\n";</syntaxhighlight>
{{out}}
<pre>[] [a] [b] [c] [a b] [a c] [b c] [a b c]</pre>
Using the two argument version of the iterator gives a solution similar to the Raku and Python array versions.
<syntaxhighlight lang="perl">use ntheory "forcomb";
my @S = qw/a b c/;
for $k (0..@S) {
# Iterate over each $#S+1,$k combination.
forcomb { print "[@S[@_]] " } @S,$k;
}
print "\n";</syntaxhighlight>
{{out}}
<pre>[] [a] [b] [c] [a b] [a c] [b c] [a b c] </pre>
Similar to the Pari/GP solution, one can also use <tt>vecextract</tt> with an integer mask to select elements. Note that it does not enforce that the input array is a set (no duplication). This also has low memory if each subset is processed immediately and the range is applied with a loop rather than a map. A solution using <tt>vecreduce</tt> could be done identical to the array reduce solution shown later.
<syntaxhighlight lang="perl">use ntheory "vecextract";
my @S = qw/a b c/;
my @PS = map { "[".join(" ",vecextract(\@S,$_))."]" } 0..2**scalar(@S)-1;
say join(" ",@PS);</syntaxhighlight>
{{out}}
<pre>[] [a] [b] [a b] [c] [a c] [b c] [a b c]</pre>
=== Module: [https://metacpan.org/pod/Set::Object Set::Object] ===
The CPAN module [https://metacpan.org/pod/Set::Object Set::Object] provides a set implementation for sets of arbitrary objects, for which a powerset function could be defined and used like so:
<syntaxhighlight 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";</syntaxhighlight>
{{out}}
<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>
=== 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):
<syntaxhighlight 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...
}</syntaxhighlight>
''(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.
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:
<syntaxhighlight 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;</syntaxhighlight>
{{out}}
<pre>
Set()
Set(1)
Set(2)
Set(1 2)
Set(3)
Set(1 3)
Set(2 3)
Set(1 2 3)
</pre>
=== 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:
<syntaxhighlight lang="perl">sub powerset {
@_ ? map { $_, [$_[0], @$_] } powerset(@_[1..$#_]) : [];
}</syntaxhighlight>
List folding solution:
<syntaxhighlight lang="perl">use List::Util qw(reduce);
sub powerset {
@{( reduce { [@$a, map([@$_, $b], @$a)] } [[]], @_ )}
}</syntaxhighlight>
Usage & output:
<syntaxhighlight lang="perl">my @set = (1, 2, 3);
my @powerset = powerset(@set);
sub set_to_string {
"{" . join(", ", map { ref $_ ? set_to_string(@$_) : $_ } @_) . "}"
}
print set_to_string(@powerset), "\n";</syntaxhighlight>
{{out}}
<pre>
{{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}
</pre>
=== Lazy evaluation ===
If the initial set is quite large, constructing it's powerset all at once can consume lots of memory.
If you want to iterate through all of the elements of the powerset of a set, and don't mind each element being generated immediately before you process it, and being thrown away immediately after you're done with it, you can use vastly less memory. This is similar to the earlier solutions using the Algorithm::Combinatorics and ntheory modules.
The following algorithm uses one bit of memory for every element of the original set (technically it uses several bytes per element with current versions of Perl). This is essentially doing a <tt>vecextract</tt> operation by hand.
<syntaxhighlight lang="perl">use strict;
use warnings;
sub powerset :prototype(&@) {
my $callback = shift;
my $bitmask = '';
my $bytes = @_/8;
{
my @indices = grep vec($bitmask, $_, 1), 0..$#_;
$callback->( @_[@indices] );
++vec($bitmask, $_, 8) and last for 0 .. $bytes;
redo if @indices != @_;
}
}
print "powerset of empty set:\n";
powerset { print "[@_]\n" };
print "powerset of set {1,2,3,4}:\n";
powerset { print "[@_]\n" } 1..4;
my $i = 0;
powerset { ++$i } 1..9;
print "The powerset of a nine element set contains $i elements.\n";
</syntaxhighlight>
{{out}}
<pre>powerset of empty set:
[]
powerset of set {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]
The powerset of a nine element set contains 512 elements.
</pre>
The technique shown above will work with arbitrarily large sets, and uses a trivial amount of memory.
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #004080;">sequence</span> <span style="color: #000000;">powerset</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">step</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">pst</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">key</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000080;font-style:italic;">/*data*/</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000080;font-style:italic;">/*user_data*/</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">powerset</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">step</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">step</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">powerset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">powerset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span><span style="color: #000000;">key</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">step</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">power_set</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">powerset</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({},</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)))</span>
<span style="color: #000000;">step</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #7060A8;">traverse_dict</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">routine_id</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"pst"</span><span style="color: #0000FF;">),</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">powerset</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">d1234</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">power_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d1234</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">d0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">power_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d0</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d0</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">power_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d0</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<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>
===alternative===
Adapted from the one I used on [[Ascending_primes#powerset]].
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">power_set</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">powerset</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{}},</span> <span style="color: #000000;">subset</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{},</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">subset</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">subset</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">sub</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">subset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ni</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sub</span><span style="color: #0000FF;">),</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">next</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">ni</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">powerset</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">powerset</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ni</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">subset</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">powerset</span><span style="color: #0000FF;">)=</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)))</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">powerset</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">power_set</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">power_set</span><span style="color: #0000FF;">({</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">power_set</span><span style="color: #0000FF;">({})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">power_set</span><span style="color: #0000FF;">({{}})</span>
<!--</syntaxhighlight>-->
{{out}}
Guaranteed to be in length order, and index order within each length.
<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}}
{{},{4},{3},{2},{1},{4,3},{4,2},{4,1},{3,2},{3,1},{2,1},{4,3,2},{4,3,1},{4,2,1},{3,2,1},{4,3,2,1}}
{{}}
{{},{{}}}
</pre>
=={{header|PHP}}==
<syntaxhighlight lang="php">
<?php
function get_subset($binary, $arr) {
Line 1,584 ⟶ 3,041:
print_power_sets(array('dog', 'c', 'b', 'a'));
?>
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="text">
POWER SET of []
POWER SET of [singleton]
Line 1,608 ⟶ 3,065:
b c dog
a b c dog
</syntaxhighlight>
=={{header|PicoLisp}}==
<
(ifn Lst
(cons)
Line 1,617 ⟶ 3,074:
(conc
(mapcar '((X) (cons (car Lst) X)) L)
L ) ) ) )</
=={{header|PL/I}}==
{{trans|REXX}}
<syntaxhighlight lang="pli">*process source attributes xref or(!);
/*--------------------------------------------------------------------
* 06.01.2014 Walter Pachl translated from REXX
Line 1,685 ⟶ 3,143:
End;
End;</
{{out}}
<pre>{}
{one}
Line 1,703 ⟶ 3,161:
{two,three,four}
{one,two,three,four}</pre>
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function power-set ($array) {
if($array) {
$n = $array.Count
function state($set, $i){
if($i -gt -1) {
state $set ($i-1)
state ($set+@($array[$i])) ($i-1)
} else {
"$($set | sort)"
}
}
$set = state @() ($n-1)
$power = 0..($set.Count-1) | foreach{@(0)}
$i = 0
$set | sort | foreach{$power[$i++] = $_.Split()}
$power | sort {$_.Count}
} else {@()}
}
$OFS = " "
$setA = power-set @(1,2,3,4)
"number of sets in setA: $($setA.Count)"
"sets in setA:"
$OFS = ", "
$setA | foreach{"{"+"$_"+"}"}
$setB = @()
"number of sets in setB: $($setB.Count)"
"sets in setB:"
$setB | foreach{"{"+"$_"+"}"}
$setC = @(@(), @(@()))
"number of sets in setC: $($setC.Count)"
"sets in setC:"
$setC | foreach{"{"+"$_"+"}"}
$OFS = " "
</syntaxhighlight>
<b>Output:</b>
<pre>
number of sets in setA: 16
sets in setA:
{}
{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}
number of sets in setB: 0
sets in setB:
number of sets in setC: 2
sets in setC:
{}
{}
</pre>
=={{header|Prolog}}==
Line 1,712 ⟶ 3,235:
The predicate subseq(X,Y) is true if and only if the list X is a subsequence of the list Y.
The
and efficient (within the class of comparably generic implementations).
<syntaxhighlight lang="prolog">powerset(X,Y) :- bagof( S, subseq(S,X), Y).
subseq( [], []).
Line 1,720 ⟶ 3,243:
subseq( [X|Xs], [X|Ys] ) :- subseq(Xs, Ys).
subseq( [X|Xs], [_|Ys] ) :- append(_, [X|Zs], Ys), subseq(Xs, Zs).
</syntaxhighlight>
{{out}}
<pre>?- powerset([1,2,3], X).
X = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]].
% Symbolic:
?- powerset( [X,Y], S).
% In reverse:
?- powerset( [X,Y], [[], [1], [1, 2], [2]] ).
X = 1,
Y = 2.</pre>
===Single-Functor Definition===
<syntaxhighlight lang="prolog">power_set( [], [[]]).
power_set( [X|Xs], PS) :-
maplist( append([X]), PS1, PS2 ), % i.e. prepend X to each PS1
append(PS1, PS2, PS).</syntaxhighlight>
{{out}}
<pre>?- power_set([1,2,3,4,5,6,7,8], X), length(X,N), writeln(N).
256
</pre>
Line 1,746 ⟶ 3,271:
CHR is a programming language created by '''Professor Thom Frühwirth'''.<br>
Works with SWI-Prolog and module chr written by '''Tom Schrijvers''' and '''Jan Wielemaker'''.
<
:- chr_constraint chr_power_set/2, chr_power_set/1, clean/0.
Line 1,764 ⟶ 3,289:
empty_element @ chr_power_set([], _) <=> chr_power_set([]).
</
{{out}}
<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],[]] .
Line 1,772 ⟶ 3,297:
=={{header|PureBasic}}==
This code is for console mode.
<
Define argc=CountProgramParameters()
If argc>=(SizeOf(Integer)*8) Or argc<1
Line 1,796 ⟶ 3,321:
PrintN("}")
EndIf
EndIf</
<!-- Output modified with a line break to avoid being too long -->
{{out}}
<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},
Line 1,804 ⟶ 3,329:
=={{header|Python}}==
<
# the power set of the empty set has one element, the empty set
result = [[]]
Line 1,823 ⟶ 3,348:
def powerset(s):
return frozenset(map(frozenset, list_powerset(list(s))))</
<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.
{{out|Example
<pre>
>>> list_powerset([1,2,3])
Line 1,834 ⟶ 3,359:
frozenset([frozenset([3]), frozenset([1, 2]), frozenset([]), frozenset([2, 3]), frozenset([1]), frozenset([1, 3]), frozenset([1, 2, 3]), frozenset([2])])
</pre>
==== 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
<
r = [[]]
for e in s:
Line 1,844 ⟶ 3,370:
s= [0,1,2,3]
print "\npowersetlist(%r) =\n %r" % (s, powersetlist(s))</
{{out}}
<pre>r: [[]] e: 0
r: [[], [0]] e: 1
Line 1,859 ⟶ 3,385:
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)
<
''' Generate a 'powerset' for sequence types that are indexable by integers.
Uses a binary count to enumerate the members and returns a list
Line 1,883 ⟶ 3,409:
set([frozenset([7]), frozenset([8, 6, 7]), frozenset([6]), frozenset([6, 7]), frozenset([]), frozenset([8]), frozenset([8, 7]), frozenset([8, 6])])
'''
return set( frozenset(x) for x in powersequence(list(s)) )</
=== Recursive Alternative ===
This is an (inefficient) recursive version that almost reflects the recursive definition of a power set as explained in http://en.wikipedia.org/wiki/Power_set#Algorithms. It does not create a sorted output.
<
def p(l):
if not l: return [[]]
return p(l[1:]) + [[l[0]] + x for x in p(l[1:])]
</syntaxhighlight>
===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:
<
>>> from itertools import chain, combinations
>>>
Line 1,922 ⟶ 3,448:
(3, 4),
(4,)}
>>> </
=={{header|Qi}}==
{{trans|Scheme}}
<syntaxhighlight lang="qi">
(define powerset
[] -> [[]]
[A|As] -> (append (map (cons A) (powerset As))
(powerset As)))
</syntaxhighlight>
=={{header|Quackery}}==
Quackery is, when seen from a certain perspective, an assembly language that recognises
only three types, "operators", which correspond to op-codes, "numbers" i.e. bignums, and
"nests" which are ordered sequences of zero of more operator, bignums and nests. Everything
else is a matter of interpretation.
Integers can be used as a set of natural numbers, with (in binary) 0 corresponding to the
empty set, 1 corresponding to the set of the natural number 1, 10 corresponding to the set
of the natural number 2, 11 corresponding to the set of the natural numbers 1 and 2, and so
on. With this sort of set, enumerating the powerset of the numbers 0 to 4, for example
simply consists of enumerating the numbers 0 to 15 inclusive. Operations on this sort of
set, such as union and intersection, correspond to bitwise logic operators.
The other way of implementing sets is with nests, with each item in a nest corresponding
to an item in the set. This is computationally slower and more complex to code, but has the
advantage that it permits sets of sets, which are required for this task.
<syntaxhighlight lang="quackery"> [ stack ] is (ps).stack
[ stack ] is (ps).items
[ stack ] is (ps).result
[ 1 - (ps).items put
0 (ps).stack put
[] (ps).result put
[ (ps).result take
(ps).stack behead
drop nested join
(ps).result put
(ps).stack take
dup (ps).items share
= iff
[ drop
(ps).stack size 1 > iff
[ 1 (ps).stack tally ] ]
else
[ dup (ps).stack put
1+ (ps).stack put ]
(ps).stack size 1 = until ]
(ps).items release
(ps).result take ] is (ps) ( n --> )
[ dup size dip
[ witheach
[ over swap peek swap ] ]
nip pack ] is arrange ( [ [ --> [ )
[ dup [] = iff
nested done
dup size (ps)
' [ [ ] ] swap join
[] unrot witheach
[ dip dup arrange
nested
rot swap join swap ]
drop ] is powerset ( [ --> [ )
' [ [ 1 2 3 4 ] [ ] [ [ ] ] ]
witheach
[ say "The powerset of "
dup echo cr
powerset witheach [ echo cr ]
cr ]</syntaxhighlight>
{{out}}
<pre>The powerset of [ 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 ]
The powerset of [ ]
[ ]
The powerset of [ [ ] ]
[ ]
[ [ ] ]
</pre>
=={{header|R}}==
===Non-recursive version===
The conceptual basis for this algorithm is the following:
<syntaxhighlight lang="text">for each element in the set:
for each subset constructed so far:
new subset = (subset + element)
</syntaxhighlight>
This method is much faster than a recursive method, though the speed is still O(2^n).
<
ps
ps[[1]]
for(element in set){ #For each element in the set, take all subsets
temp
for(subset in 1:length(ps)){ #by adding "element" to each of them.
temp[[subset]] = c(ps[[subset]],element)
}
ps
}
}
powerset(1:4)
</syntaxhighlight>
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===
{{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.
<syntaxhighlight lang="r">library(sets)</syntaxhighlight>
An example with a vector.
<
sv <- as.set(v)
2^sv</
{{}, {1}, {4}, {9}, {1, 4}, {1, 9}, {4, 9}, {1, 4, 9}}
An example with a list.
<
sl <- as.set(l)
2^sl</
{{}, {1}, {"qwerty"}, {<<list(2)>>}, {1, <<list(2)>>}, {"qwerty",
1}, {"qwerty", <<list(2)>>}, {"qwerty", 1, <<list(2)>>}}
=={{header|Racket}}==
<
;;; Direct translation of 'functional' ruby method
(define (powerset s)
Line 1,985 ⟶ 3,608:
(list->set (set-map outer-set
(λ(inner-set) (set-add inner-set element)))))))
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|rakudo|2014-02-25}}
<syntaxhighlight lang="raku" line>sub powerset(Set $s) { $s.combinations.map(*.Set).Set }
say powerset set <a b c d>;</syntaxhighlight>
{{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>
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:
<syntaxhighlight lang="raku" line>.say for <a b c d>.combinations</syntaxhighlight>
{{out}}
<pre>
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</pre>
=={{header|Rascal}}==
<
import Set;
public set[set[&T]] PowerSet(set[&T] s) = power(s);
</syntaxhighlight>
{{out}}
<
rascal>PowerSet({1,2,3,4})
set[set[int]]: {
Line 2,014 ⟶ 3,664:
{}
}
</syntaxhighlight>
=={{header|REXX}}==
<
text='one two three four'
n=words(text)
psi=0
Do k=0 To n
cc=comb(n,k)
Do while pos('/',cc)>0 /* as long as there is a combination */
Parse Var cc elist '/' cc /* get
psl='' /* initialize the list of words */
psi=psi+1
parse var elist e elist /* get an element (a digit) */
psl=psl','word(text,e) /* add corresponding test word to set */
End
psl=substr(psl,2) /*
Say right(psi,2) '{'psl'}' /* show this element of the power set */
End
End
Exit
comb: Procedure
/***********************************************************************
* Returns the combinations of size digits out of things digits
* e.g. comb(4,2) -> ' 1 2/1 3/1 4/2 3/2 4/3 4/'
1 2/ 1 3/ 1 4/ 2 3/ 2 4/ 3 4 /
***********************************************************************/
Parse Arg things,size
n=2**things-1
list=''
Do u=1 To n
co=combinations(u)
If co>'' Then
list=list '/' combinations(u)
End
Return substr(space(list),2) '/' /* remove leading / */
combinations: Procedure Expose things size
Parse Arg u
nc=0
bu=x2b(d2x(u))
bu1=space(translate(bu,' ',0),0)
If length(bu1)=size Then Do
ub=reverse(bu)
res=''
Do i=1 To things
c=i
If substr(ub,i,1)=1 Then res=res i
End
Return res
End
Else
Return ''</syntaxhighlight>
{{out|output|text= when using the default input:}}
<pre>
1 {}
2 {one}
Line 2,064 ⟶ 3,738:
15 {two,three,four}
16 {one,two,three,four}
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
# Project : Power set
list = ["1", "2", "3", "4"]
see powerset(list)
func powerset(list)
s = "{"
for i = 1 to (2 << len(list)) - 1 step 2
s = s + "{"
for j = 1 to len(list)
if i & (1 << j)
s = s + list[j] + ","
ok
next
if right(s,1) = ","
s = left(s,len(s)-1)
ok
s = s + "},"
next
return left(s,len(s)-1) + "}"
</syntaxhighlight>
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|RPL}}==
{{works with|Halcyon Calc|4.2.8}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
'''IF''' DUP SIZE
'''THEN''' LAST OVER SWAP GET → last
≪ LIST→ 1 - SWAP DROP →LIST '''POWST'''
1 OVER SIZE '''FOR''' j
DUP j GET last + 1 →LIST + '''NEXT'''
≫
'''ELSE''' 1 →LIST '''END'''
≫ ''''POWST'''' STO
|
'''POWST''' ''( { set } -- { power set } )''
if set is not empty
then store last item
get power set of ''{ set } - last item''
for all sets of ''{ set } - last item'' power set
add last item to set, then set to power set
else return { { } }
|}
{ 1 2 3 4 } '''POWST'''
{ } '''POWST'''
{{out}}
<pre>
2: { { } { 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: { { } }
</pre>
=={{header|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
Line 2,109 ⟶ 3,848:
p %w(one two three).func_power_set
p Set[1,2,3].powerset</
{{out}}
<pre>
Line 2,115 ⟶ 3,854:
[[], ["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}>}>
</pre>
=={{header|Rust}}==
This implementation consumes the input set, requires that the type <b>T</b> has a full order a.k.a implements the <b>Ord</b> trait and that <b>T</b> is clonable.
<syntaxhighlight lang="rust">use std::collections::BTreeSet;
fn powerset<T: Ord + Clone>(mut set: BTreeSet<T>) -> BTreeSet<BTreeSet<T>> {
if set.is_empty() {
let mut powerset = BTreeSet::new();
powerset.insert(set);
return powerset;
}
// Access the first value. This could be replaced with `set.pop_first().unwrap()`
// But this is an unstable feature
let entry = set.iter().nth(0).unwrap().clone();
set.remove(&entry);
let mut powerset = powerset(set);
for mut set in powerset.clone().into_iter() {
set.insert(entry.clone());
powerset.insert(set);
}
powerset
}
fn main() {
let set = (1..5).collect();
let set = powerset(set);
println!("{:?}", set);
let set = ["a", "b", "c", "d"].iter().collect();
let set = powerset(set);
println!("{:?}", set);
}
</syntaxhighlight>
{{out}}
<pre>
{{}, {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}}
{{}, {"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"}}
</pre>
=={{header|SAS}}==
<syntaxhighlight 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;
</syntaxhighlight>
You can then call the macro as:
<syntaxhighlight lang="sas">
%SubSets(FieldCount = 5);
</syntaxhighlight>
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>
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
</pre>
=={{header|Scala}}==
<syntaxhighlight 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)))
println(s"Successfully completed without errors. [total ${currentTime - executionStart} ms]")
}</syntaxhighlight>
Another option that produces lazy sequence of the sets:
<syntaxhighlight lang="scala">def powerset[A](s: Set[A]) = (0 to s.size).map(s.toSeq.combinations(_)).reduce(_ ++ _).map(_.toSet)</syntaxhighlight>
A tail-recursive version:
<syntaxhighlight lang="scala">def powerset[A](s: Set[A]) = {
def powerset_rec(acc: List[Set[A]], remaining: List[A]): List[Set[A]] = remaining match {
case Nil => acc
case head :: tail => powerset_rec(acc ++ acc.map(_ + head), tail)
}
powerset_rec(List(Set.empty[A]), s.toList)
}</syntaxhighlight>
=={{header|Scheme}}==
{{trans|Common Lisp}}
<
(if (null? set)
'(())
Line 2,134 ⟶ 4,037:
(display (power-set (list "A" "C" "E")))
(newline)</
{{out}}
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())
((A C E) (A C) (A E) (A) (C E) (C) (E) ())
Call/cc generation:<
(define (iter yield)
(let recur ((a '()) (b lst))
Line 2,161 ⟶ 4,064:
(display a)
(newline)
(loop (x)))))</
{{out}}
<pre>(1 2)
(1 3)
(1)
Line 2,167 ⟶ 4,072:
(2)
(3)
()</
Iterative:<
(define (power_set_iter set)
(let loop ((res '(())) (s set))
Line 2,175 ⟶ 4,080:
res
(loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s)))))
</syntaxhighlight>
{{out}}
<pre>
'((e d c b a)
(e d c b)
Line 2,210 ⟶ 4,116:
(a)
())
</
=={{header|Seed7}}==
<
const func array bitset: powerSet (in bitset: baseSet) is func
Line 2,241 ⟶ 4,147:
writeln(aSet);
end for;
end func;</
{{out}}
<pre>
{}
Line 2,261 ⟶ 4,167:
{2, 3, 4}
{1, 2, 3, 4}
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="haskell">Pfour := pow({1, 2, 3, 4});
Pempty := pow({});
PPempty := pow(Pempty);
print(Pfour);
print(Pempty);
print(PPempty);</syntaxhighlight>
{{out}}
<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}}
{{}}
{{} {{}}}</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">var arr = %w(a b c)
for i in (0 .. arr.len) {
say arr.combinations(i)
}</syntaxhighlight>
{{out}}
<pre>
[[]]
[["a"], ["b"], ["c"]]
[["a", "b"], ["a", "c"], ["b", "c"]]
[["a", "b", "c"]]
</pre>
=={{header|Simula}}==
<syntaxhighlight lang="simula">SIMSET
BEGIN
LINK CLASS LOF_INT(N); INTEGER N;;
LINK CLASS LOF_LOF_INT(H); REF(HEAD) H;;
REF(HEAD) PROCEDURE MAP(P_LI, P_LLI);
REF(HEAD) P_LI;
REF(HEAD) P_LLI;
BEGIN
REF(HEAD) V_RESULT;
V_RESULT :- NEW HEAD;
IF NOT P_LLI.EMPTY THEN BEGIN
REF(LOF_LOF_INT) V_LLI;
V_LLI :- P_LLI.FIRST QUA LOF_LOF_INT;
WHILE V_LLI =/= NONE DO BEGIN
REF(HEAD) V_NEWLIST;
V_NEWLIST :- NEW HEAD;
! ADD THE SAME 1ST ELEMENT TO EVERY NEWLIST ;
NEW LOF_INT(P_LI.FIRST QUA LOF_INT.N).INTO(V_NEWLIST);
IF NOT V_LLI.H.EMPTY THEN BEGIN
REF(LOF_INT) V_LI;
V_LI :- V_LLI.H.FIRST QUA LOF_INT;
WHILE V_LI =/= NONE DO BEGIN
NEW LOF_INT(V_LI.N).INTO(V_NEWLIST);
V_LI :- V_LI.SUC;
END;
END;
NEW LOF_LOF_INT(V_NEWLIST).INTO(V_RESULT);
V_LLI :- V_LLI.SUC;
END;
END;
MAP :- V_RESULT;
END MAP;
REF(HEAD) PROCEDURE SUBSETS(P_LI);
REF(HEAD) P_LI;
BEGIN
REF(HEAD) V_RESULT;
IF P_LI.EMPTY THEN BEGIN
V_RESULT :- NEW HEAD;
NEW LOF_LOF_INT(NEW HEAD).INTO(V_RESULT);
END ELSE BEGIN
REF(HEAD) V_SUBSET, V_MAP;
REF(LOF_INT) V_LI;
V_SUBSET :- NEW HEAD;
V_LI :- P_LI.FIRST QUA LOF_INT;
! SKIP OVER 1ST ELEMENT ;
IF V_LI =/= NONE THEN V_LI :- V_LI.SUC;
WHILE V_LI =/= NONE DO BEGIN
NEW LOF_INT(V_LI.N).INTO(V_SUBSET);
V_LI :- V_LI.SUC;
END;
V_RESULT :- SUBSETS(V_SUBSET);
V_MAP :- MAP(P_LI, V_RESULT);
IF NOT V_MAP.EMPTY THEN BEGIN
REF(LOF_LOF_INT) V_LLI;
V_LLI :- V_MAP.FIRST QUA LOF_LOF_INT;
WHILE V_LLI =/= NONE DO BEGIN
NEW LOF_LOF_INT(V_LLI.H).INTO(V_RESULT);
V_LLI :- V_LLI.SUC;
END;
END;
END;
SUBSETS :- V_RESULT;
END SUBSETS;
PROCEDURE PRINT_LIST(P_LI); REF(HEAD) P_LI;
BEGIN
OUTTEXT("[");
IF NOT P_LI.EMPTY THEN BEGIN
INTEGER I;
REF(LOF_INT) V_LI;
I := 0;
V_LI :- P_LI.FIRST QUA LOF_INT;
WHILE V_LI =/= NONE DO BEGIN
IF I > 0 THEN OUTTEXT(",");
OUTINT(V_LI.N, 0);
V_LI :- V_LI.SUC;
I := I+1;
END;
END;
OUTTEXT("]");
END PRINT_LIST;
PROCEDURE PRINT_LIST_LIST(P_LLI); REF(HEAD) P_LLI;
BEGIN
OUTTEXT("[");
IF NOT P_LLI.EMPTY THEN BEGIN
INTEGER I;
REF(LOF_LOF_INT) V_LLI;
I := 0;
V_LLI :- P_LLI.FIRST QUA LOF_LOF_INT;
WHILE V_LLI =/= NONE DO BEGIN
IF I > 0 THEN BEGIN
OUTTEXT(",");
! OUTIMAGE;
END;
PRINT_LIST(V_LLI.H);
V_LLI :- V_LLI.SUC;
I := I+1;
END;
END;
OUTTEXT("]");
OUTIMAGE;
END PRINT_LIST_LIST;
INTEGER N;
REF(HEAD) V_RANGE;
REF(HEAD) V_LISTS;
V_RANGE :- NEW HEAD;
V_LISTS :- SUBSETS(V_RANGE);
PRINT_LIST_LIST(V_LISTS);
OUTIMAGE;
FOR N := 1 STEP 1 UNTIL 4 DO BEGIN
NEW LOF_INT(N).INTO(V_RANGE);
V_LISTS :- SUBSETS(V_RANGE);
PRINT_LIST_LIST(V_LISTS);
OUTIMAGE;
END;
END.
</syntaxhighlight>
{{out}}
<pre>
[[]]
[[],[1]]
[[],[2],[1],[1,2]]
[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
[[],[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]]
</pre>
Line 2,267 ⟶ 4,340:
Code from [http://smalltalk.gnu.org/blog/bonzinip/fun-generators Bonzini's blog]
<
power [
^(0 to: (1 bitShift: self size) - 1) readStream collect: [ :each || i |
Line 2,273 ⟶ 4,346:
self select: [ :elem | (each bitAt: (i := i + 1)) = 1 ] ]
]
].</
<
each asArray printNl ].
#( 'A' 'C' 'E' ) power do: [ :each |
each asArray printNl ].</
=={{header|Standard ML}}==
version for lists:
<
=={{header|Swift}}==
{{works with|Swift|Revision 4 - tested with Xcode 9.2 playground}}
<syntaxhighlight lang="swift">func powersetFrom<T>(_ elements: Set<T>) -> Set<Set<T>> {
guard elements.count > 0 else {
return [[]]
}
var powerset: Set<Set<T>> = [[]]
for element in elements {
for subset in powerset {
powerset.insert(subset.union([element]))
}
}
return powerset
}
// Example:
powersetFrom([1, 2, 4])</syntaxhighlight>
{{out}}
<pre>{
{2, 4}
{4, 1}
{4},
{2, 4, 1}
{2, 1}
Set([])
{1}
{2}
}</pre>
<syntaxhighlight lang="swift">//Example:
powersetFrom(["a", "b", "d"])</syntaxhighlight>
{{out}}
<pre>{
{"b", "d"}
{"b"}
{"d"},
{"a"}
{"b", "d", "a"}
Set([])
{"d", "a"}
{"b", "a"}
}</pre>
=={{header|Tcl}}==
<
set res [list [list]]
foreach e $l {
Line 2,294 ⟶ 4,411:
return $res
}
puts [subsets {a b c d}]</
{{out}}
<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===
<
set res {}
for {set i 0} {$i < 2**[llength $set]} {incr i} {
Line 2,309 ⟶ 4,426:
}
return $res
}</
=={{header|TXR}}==
The power set function can be written concisely like this:
<
(mappend* (op comb s) (range 0 (length s))))</syntaxhighlight>
This generates the lists of combinations of all possible lengths, from 0 to the length of <code>s</code> and catenates them. The <code>comb</code> function generates a lazy list, so it is appropriate to use <code>mappend*</code> (the lazy version of <code>mappend</code>) to keep the behavior lazy.
A complete program which takes command line arguments and prints the power set in comma-separated brace notation:
<syntaxhighlight lang="txr">@(do (defun power-set (s)
(mappend* (op comb s) (range 0 (length s)))))
@(bind pset @(power-set *args*))
@(output)
@ (repeat)
{@(rep)@pset, @(last)@pset@(empty)@(end)}
@ (end)
@(end)</
{{out}}
<pre>$
{1, 2, 3}
{1, 2}
Line 2,349 ⟶ 4,458:
{}</pre>
generalizes to strings and vectors.
<
(mappend* (op comb s) (range 0 (length s))))
(prinl (power-set
(
(
{{out}}
<pre>$ txr power-set-generic.txr
("" "a" "b" "c" "ab" "ac" "bc" "abc")
("" "b")
("")
(#() #(1) #(2) #(3) #(1 2) #(1 3) #(2 3) #(1 2 3))</pre>
=={{header|UNIX Shell}}==
From [http://www.catonmat.net/blog/set-operations-in-unix-shell/ here]
<syntaxhighlight lang="bash">p() { [ $# -eq 0 ] && echo || (shift; p "$@") | while read r ; do echo -e "$1 $r\n$r"; done }</syntaxhighlight>
Usage
<syntaxhighlight lang="bash">|p `cat` | sort | uniq
A
C
E
^D</syntaxhighlight>
=={{header|UnixPipes}}==
<
| cat A
a
Line 2,388 ⟶ 4,508:
b c
c
</syntaxhighlight>
=={{header|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.
<
test program:
<
test = powerset {'a','b','c','d'}</
{{out}}
<pre>{
{},
Line 2,432 ⟶ 4,542:
=={{header|V}}==
V has a built in called powerlist
<
=[[A C E] [A C] [A E] [A] [C E] [C] [E] []]</
its implementation in std.v is (like joy)
<
[null?]
[unitlist]
Line 2,442 ⟶ 4,552:
[dup swapd [cons] map popd swoncat]
linrec].
</syntaxhighlight>
=={{
<syntaxhighlight lang="vb">Option Base 1
Private Function power_set(ByRef st As Collection) As Collection
Dim subset As Collection, pwset As New Collection
For i = 0 To 2 ^ st.Count - 1
Set subset = New Collection
For j = 1 To st.Count
If i And 2 ^ (j - 1) Then subset.Add st(j)
Next j
pwset.Add subset
Next i
Set power_set = pwset
End Function
Private Function print_set(ByRef st As Collection) As String
'assume st is a collection of collections, holding integer variables
Dim s() As String, t() As String
ReDim s(st.Count)
'Debug.Print "{";
For i = 1 To st.Count
If st(i).Count > 0 Then
ReDim t(st(i).Count)
For j = 1 To st(i).Count
Select Case TypeName(st(i)(j))
Case "Integer": t(j) = CStr(st(i)(j))
Case "Collection": t(j) = "{}" 'assumes empty
End Select
Next j
s(i) = "{" & Join(t, ", ") & "}"
Else
s(i) = "{}"
End If
Next i
print_set = "{" & Join(s, ", ") & "}"
End Function
Public Sub rc()
Dim rcset As New Collection, result As Collection
For i = 1 To 4
rcset.Add i
Next i
Debug.Print print_set(power_set(rcset))
Set rcset = New Collection
Debug.Print print_set(power_set(rcset))
Dim emptyset As New Collection
rcset.Add emptyset
Debug.Print print_set(power_set(rcset))
Debug.Print
End Sub</syntaxhighlight>{{out}}
<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|VBScript}}==
<syntaxhighlight lang="vb">Function Dec2Bin(n)
q = n
Dec2Bin = ""
Do Until q = 0
Dec2Bin = CStr(q Mod 2) & Dec2Bin
q = Int(q / 2)
Loop
Dec2Bin = Right("00000" & Dec2Bin,6)
End Function
Function PowerSet(s)
arrS = Split(s,",")
PowerSet = "{"
For i = 0 To 2^(UBound(arrS)+1)-1
If i = 0 Then
PowerSet = PowerSet & "{},"
Else
binS = Dec2Bin(i)
PowerSet = PowerSet & "{"
c = 0
For j = Len(binS) To 1 Step -1
If CInt(Mid(binS,j,1)) = 1 Then
PowerSet = PowerSet & arrS(c) & ","
End If
c = c + 1
Next
PowerSet = Mid(PowerSet,1,Len(PowerSet)-1) & "},"
End If
Next
PowerSet = Mid(PowerSet,1,Len(PowerSet)-1) & "}"
End Function
WScript.StdOut.Write PowerSet("1,2,3,4")</syntaxhighlight>
{{out}}
<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|Wren}}==
{{libheader|Wren-perm}}
Although we have a module for sets, they are based on maps whose keys must be value types. This means that sets of sets are technically impossible because sets themselves are not value types.
We therefore use lists to represent sets which works fine here.
<syntaxhighlight lang="wren">import "./perm" for Powerset
var sets = [ [1, 2, 3, 4], [], [[]] ]
for (set in sets) {
System.print("The power set of %(set) is:")
System.print(Powerset.list(set))
System.print()
}</syntaxhighlight>
{{out}}
<pre>
The power set of [1, 2, 3, 4] is:
[[], [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]]
The power set of [] is:
[[]]
The power set of [[]] is:
[[], [[]]]
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">func PowSet(Set, Size);
int Set, Size;
int N, M, Mask, DoComma;
[ChOut(0, ^{);
for N:= 0 to 1<<Size -1 do
[if N>0 then ChOut(0, ^,);
ChOut(0, ^{);
Mask:= 1; DoComma:= false;
for M:= 0 to Size-1 do
[if Mask & N then
[if DoComma then ChOut(0, ^,);
IntOut(0, Set(M));
DoComma:= true;
];
Mask:= Mask << 1;
];
ChOut(0, ^});
];
Text(0, "}^m^j");
];
[PowSet([2, 3, 5, 7], 4);
PowSet([1], 1);
PowSet(0, 0);
]</syntaxhighlight>
{{out}}
<pre>
{{},{2},{3},{2,3},{5},{2,5},{3,5},{2,3,5},{7},{2,7},{3,7},{2,3,7},{5,7},{2,5,7},{3,5,7},{2,3,5,7}}
{{},{1}}
{{}}
</pre>
=={{header|zkl}}==
Using a combinations function, build the power set from combinations of 1,2,... items.
<syntaxhighlight lang="zkl">fcn pwerSet(list){
(0).pump(list.len(),List, Utils.Helpers.pickNFrom.fp1(list),
T(Void.Write,Void.Write) ) .append(list)
}</syntaxhighlight>
<syntaxhighlight lang="zkl">foreach n in (5){
ps:=pwerSet((1).pump(n,List)); ps.println(" Size = ",ps.len());
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
|