# Power set

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

A   set   is a collection (container) of certain values, without any particular order, and no repeated values.

It corresponds with a finite set in mathematics.

A set can be implemented as an associative array (partial mapping) in which the value of each key-value pair is ignored.

Given a set S, the power set (or powerset) of S, written P(S), or 2S, is the set of all subsets of S.

By using a library or built-in set type, or by defining a set type with necessary operations, write a function with a set S as input that yields the power set 2S of S.

For example, the power set of     {1,2,3,4}     is

{{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}.

For a set which contains n elements, the corresponding power set has 2n elements, including the edge cases of empty set.

The power set of the empty set is the set which contains itself (20 = 1):

${\displaystyle \mathcal{P}}$(${\displaystyle \varnothing}$) = { ${\displaystyle \varnothing}$ }

And the power set of the set which contains only the empty set, has two subsets, the empty set and the set which contains the empty set (21 = 2):

${\displaystyle \mathcal{P}}$({${\displaystyle \varnothing}$}) = { ${\displaystyle \varnothing}$, { ${\displaystyle \varnothing}$ } }

Extra credit: Demonstrate that your language supports these last two powersets.

## 11l

Translation of: Python
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]))
Output:
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]


## ABAP

This works for ABAP Version 7.40 and above

report z_powerset.

interface set.
methods:
importing
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).
endloop.
endmethod.

if not line_exists( me->elements[ table_line = element_to_be_added ] ).
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
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 )


## BASIC

### BBC BASIC

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

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

Output:
{{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3},{4},{1,4},{2,4},{1,2,4},{3,4},{1,3,4},{2,3,4},{1,2,3,4}}


## BQN

P ← (⥊·↕2⥊˜≠)/¨<
Output:
   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 ⟩ ⟩


## Bracmat

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

## Burlesque

blsq ) {1 2 3 4}R@
{{} {1} {2} {1 2} {3} {1 3} {2 3} {1 2 3} {4} {1 4} {2 4} {1 2 4} {3 4} {1 3 4} {2 3 4} {1 2 3 4}}

## C

#include <stdio.h>

struct node {
char *s;
struct node* prev;
};

void powerset(char **v, int n, struct node *up)
{
struct node me;

if (!n) {
putchar('[');
while (up) {
printf(" %s", up->s);
up = up->prev;
}
puts(" ]");
} else {
me.s = *v;
me.prev = up;
powerset(v + 1, n - 1, up);
powerset(v + 1, n - 1, &me);
}
}

int main(int argc, char **argv)
{
powerset(argv + 1, argc - 1, 0);
return 0;
}

Output:
% ./a.out 1 2 3
[ ]
[ 3 ]
[ 2 ]
[ 3 2 ]
[ 1 ]
[ 3 1 ]
[ 2 1 ]
[ 3 2 1 ]


## C#

public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
return from m in Enumerable.Range(0, 1 << list.Count)
select
from i in Enumerable.Range(0, list.Count)
where (m & (1 << i)) != 0
select list[i];
}

public void PowerSetofColors()
{
var colors = new List<KnownColor> { KnownColor.Red, KnownColor.Green,
KnownColor.Blue, KnownColor.Yellow };

var result = GetPowerSet(colors);

Console.Write( string.Join( Environment.NewLine,
result.Select(subset =>
string.Join(",", subset.Select(clr => clr.ToString()).ToArray())).ToArray()));
}

Output:
  Red
Green
Red,Green
Blue
Red,Blue
Green,Blue
Red,Green,Blue
Yellow
Red,Yellow
Green,Yellow
Red,Green,Yellow
Blue,Yellow
Red,Blue,Yellow
Green,Blue,Yellow
Red,Green,Blue,Yellow


An alternative implementation for an arbitrary number of elements:

  public IEnumerable<IEnumerable<T>> GetPowerSet<T>(IEnumerable<T> input) {
var seed = new List<IEnumerable<T>>() { Enumerable.Empty<T>() }
as IEnumerable<IEnumerable<T>>;

return input.Aggregate(seed, (a, b) =>
a.Concat(a.Select(x => x.Concat(new List<T>() { b }))));
}


Non-recursive version

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


Recursive version

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


## C++

### Non-recursive version

#include <iostream>
#include <set>
#include <vector>
#include <iterator>
#include <algorithm>
typedef std::set<int> set_type;
typedef std::set<set_type> powerset_type;

powerset_type powerset(set_type const& set)
{
typedef set_type::const_iterator set_iter;
typedef std::vector<set_iter> vec;
typedef vec::iterator vec_iter;

struct local
{
static int dereference(set_iter v) { return *v; }
};

powerset_type result;

vec elements;
do
{
set_type tmp;
std::transform(elements.begin(), elements.end(),
std::inserter(tmp, tmp.end()),
local::dereference);
result.insert(tmp);
if (!elements.empty() && ++elements.back() == set.end())
{
elements.pop_back();
}
else
{
set_iter iter;
if (elements.empty())
{
iter = set.begin();
}
else
{
iter = elements.back();
++iter;
}
for (; iter != set.end(); ++iter)
{
elements.push_back(iter);
}
}
} while (!elements.empty());

return result;
}

int main()
{
int values[4] = { 2, 3, 5, 7 };
set_type test_set(values, values+4);

powerset_type test_powerset = powerset(test_set);

for (powerset_type::iterator iter = test_powerset.begin();
iter != test_powerset.end();
++iter)
{
std::cout << "{ ";
char const* prefix = "";
for (set_type::iterator iter2 = iter->begin();
iter2 != iter->end();
++iter2)
{
std::cout << prefix << *iter2;
prefix = ", ";
}
std::cout << " }\n";
}
}

Output:
{  }
{ 2 }
{ 2, 3 }
{ 2, 3, 5 }
{ 2, 3, 5, 7 }
{ 2, 3, 7 }
{ 2, 5 }
{ 2, 5, 7 }
{ 2, 7 }
{ 3 }
{ 3, 5 }
{ 3, 5, 7 }
{ 3, 7 }
{ 5 }
{ 5, 7 }
{ 7 }


#### C++14 version

This simplified version has identical output to the previous code.

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


### Recursive version

#include <iostream>
#include <set>

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


## Clojure

(use '[clojure.math.combinatorics :only [subsets] ])

(def S #{1 2 3 4})

user> (subsets S)
(() (1) (2) (3) (4) (1 2) (1 3) (1 4) (2 3) (2 4) (3 4) (1 2 3) (1 2 4) (1 3 4) (2 3 4) (1 2 3 4))


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

(defn powerset [coll]
(reduce (fn [a x]
(into a (map #(conj % x)) a))
#{#{}} coll))

(powerset #{1 2 3})

#{#{} #{1} #{2} #{1 2} #{3} #{1 3} #{2 3} #{1 2 3}}


Using bit-test: see: https://clojuredocs.org/clojure.core/bit-test#example-5d401face4b0ca44402ef78b

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

(() (1) (2) (1 2) (3) (1 3) (2 3) (1 2 3))


## CoffeeScript

print_power_set = (arr) ->
console.log "POWER SET of #{arr}"
for subset in power_set(arr)
console.log subset

power_set = (arr) ->
result = []
binary = (false for elem in arr)
n = arr.length
while binary.length <= n
result.push bin_to_arr binary, arr
i = 0
while true
if binary[i]
binary[i] = false
i += 1
else
binary[i] = true
break
binary[i] = true
result

bin_to_arr = (binary, arr) ->
(arr[i] for i of binary when binary[arr.length - i  - 1])

print_power_set []
print_power_set [4, 2, 1]
print_power_set ['dog', 'c', 'b', 'a']

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


## ColdFusion

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

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

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

Output:
["","1","2","1,2","3","1,3","2,3","1,2,3","4","1,4","2,4","1,2,4","3,4","1,3,4","2,3,4","1,2,3,4"]

## Common Lisp

(defun powerset (s)
(if s (mapcan (lambda (x) (list (cons (car s) x) x))
(powerset (cdr s)))
'(())))

Output:
> (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)

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

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


Alternate, more recursive (same output):

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


Imperative-style using LOOP:

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

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


Yet another imperative solution, this time with dolist.

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

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


## D

This implementation defines a range which *lazily* enumerates the power set.

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; }  An alternative version, which implements the range construct from scratch: import std.range; struct PowerSet(R) 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); }  Output: $ rdmd powerset a b c
[]
["a"]
["b"]
["a", "b"]
["c"]
["a", "c"]
["b", "c"]
["a", "b", "c"]

### 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.

1. It isn't lazy (but it could be made so by implementing this as a generator)

Main differences from the version above:

1. It isn't lazy
2. It doesn't rely on integer bit fiddling, so it should work on arrays larger than size_t.
// 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 ); }  ## Déjà Vu In Déjà Vu, sets are dictionaries with all values true and the default set to false. powerset s: local :out [ set{ } ] for value in keys s: for subset in copy out: local :subset+1 copy subset set-to subset+1 value true push-to out subset+1 out !. powerset set{ 1 2 3 4 } Output: [ set{ } set{ 4 } set{ 3 4 } set{ 3 } set{ 2 3 } set{ 2 3 4 } set{ 2 4 } set{ 2 } set{ 1 2 } set{ 1 2 4 } set{ 1 2 3 4 } set{ 1 2 3 } set{ 1 3 } set{ 1 3 4 } set{ 1 4 } set{ 1 } ] ## Delphi Translation of: C# 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.


## Dyalect

Translation of: C#
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)

## E

pragma.enable("accumulator")

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

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

## EchoLisp

(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


## Elixir

Translation of: Erlang
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"])

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


## Erlang

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

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

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

Output:

[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3], [4], [1,4], [2,4], [1,2,4], [3,4], [1,3,4], [2,3,4], [1,2,3,4]]

Alternate shorter and more efficient version:

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


or even more efficient version:

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

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


## F#

almost exact copy of OCaml version

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


alternatively with list comprehension

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


## Factor

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

USING: kernel prettyprint sequences arrays sets hash-sets ;
IN: powerset

: add ( set elt -- newset ) 1array <hash-set> union ;
: powerset ( set -- newset ) members { HS{ } } [ dupd [ add ] curry map append ] reduce <hash-set> ;


Usage:

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


## Forth

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

powerset

Output:
reduce .[] as $r (.; . + [$r + [$i]])); Example: [range(0;10)]|powerset|length # => 1024  Extra credit: # The power set of the empty set: [] | powerset # => [[]] # The power set of the set which contains only the empty set: [ [] ] | powerset # => [[],[[]]] #### Recursive version def powerset: if length == 0 then [[]] else .[0] as$first
| (.[1:] | powerset)
| map([$first] + . ) + . end; Example: [1,2,3]|powerset # => [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]  ## Julia function powerset(x::Vector{T})::Vector{Vector{T}} where T result = Vector{T}[[]] for elem in x, j in eachindex(result) push!(result, [result[j] ; elem]) end result end  Output: julia> show(powerset([1,2,3])) [Int64[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]  ### Non-Mutating Solution 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  Output: julia> show(powerset([1,2,3])) [Int64[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]  ## K  ps:{x@&:'+2_vs!_2^#x} Usage:  ps "ABC" ("" ,"C" ,"B" "BC" ,"A" "AC" "AB" "ABC") ## Kotlin // 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) } } } }  Output: 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: [] [[]]  ## Lambdatalk {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]]]  ## Logo to powerset :set if empty? :set [output [[]]] localmake "rest powerset butfirst :set output sentence map [sentence first :set ?] :rest :rest end show powerset [1 2 3] [[1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []] ## Logtalk :- object(set). :- public(powerset/2). powerset(Set, PowerSet) :- reverse(Set, RSet), powerset_1(RSet, [[]], PowerSet). powerset_1([], PowerSet, PowerSet). powerset_1([X| Xs], Yss0, Yss) :- powerset_2(Yss0, X, Yss1), powerset_1(Xs, Yss1, Yss). powerset_2([], _, []). powerset_2([Zs| Zss], X, [Zs, [X| Zs]| Yss]) :- powerset_2(Zss, X, Yss). reverse(List, Reversed) :- reverse(List, [], Reversed). reverse([], Reversed, Reversed). reverse([Head| Tail], List, Reversed) :- reverse(Tail, [Head| List], Reversed). :- end_object.  Usage example: | ?- set::powerset([1, 2, 3, 4], PowerSet). PowerSet = [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]] yes  ## Lua --returns the powerset of s, out of order. function powerset(s, start) start = start or 1 if(start > #s) then return {{}} end local ret = powerset(s, start + 1) for i = 1, #ret do ret[#ret + 1] = {s[start], unpack(ret[i])} end return ret end --non-recurse implementation function powerset(s) local t = {{}} for i = 1, #s do for j = 1, #t do t[#t+1] = {s[i],unpack(t[j])} end end return t end --alternative, copied from the Python implementation function powerset2(s) local ret = {{}} for i = 1, #s do local k = #ret for j = 1, k do ret[k + j] = {s[i], unpack(ret[j])} end end return ret end  ## M4 define(for', ifelse($#, 0, $0'', eval($2 <= $3), 1, pushdef($1', $2')$4'popdef(
$1')$0($1', incr($2), $3, $4')')')dnl
define(nth',
ifelse($1, 1,$2,
nth(decr($1), shift(shift($@)))')')dnl
define(range',
for(x', eval($1 + 2), eval($2 + 2),
nth(x, $@)'ifelse(x, eval($2+2), ', ,')')')dnl
define(powerpart',
{range(2, incr($1),$@)}'ifelse(incr($1),$#, ',
for(x', eval($1+2),$#,
,powerpart(incr($1), ifelse( eval(2 <= ($1 + 1)), 1,
range(2,incr($1),$@), ')'nth(x, $@)'ifelse( eval((x + 1) <=$#),1,,range(incr(x), $#,$@)'))')')')dnl
define(powerset',
{powerpart(0, substr($1', 1, eval(len($1') - 2)))}')dnl
dnl
powerset({a,b,c}')
Output:
{{},{a},{a,b},{a,b,c},{a,c},{b},{b,c},{c}}


## Maple

combinat:-powerset({1,2,3,4});
Output:
{{}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4},

{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}


## Mathematica/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:

Subsets[{a, b, c}]


gives:

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


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

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

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

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

## MATLAB

Sets are not an explicit data type in MATLAB, but cell arrays can be used for the same purpose. In fact, cell arrays have the benefit of containing any kind of data structure. So, this powerset function will work on a set of any type of data structure, without the need to overload any operators.

function pset = powerset(theSet)

pset = cell(size(theSet)); %Preallocate memory

%Generate all numbers from 0 to 2^(num elements of the set)-1
for i = ( 0:(2^numel(theSet))-1 )

%Convert i into binary, convert each digit in binary to a boolean
%and store that array of booleans
indicies = logical(bitget( i,(1:numel(theSet)) ));

%Use the array of booleans to extract the members of the original
%set, and store the set containing these members in the powerset
pset(i+1) = {theSet(indicies)};

end

end


Sample Usage: Powerset of the set of the empty set.

powerset({{}})

ans =

{}    {1x1 cell} %This is the same as { {},{{}} }


Powerset of { {1,2},3 }.

powerset({{1,2},3})

ans =

{1x0 cell}    {1x1 cell}    {1x1 cell}    {1x2 cell} %This is the same as { {},{{1,2}},{3},{{1,2},3} }


## Maxima

powerset({1, 2, 3, 4});
/* {{}, {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {1, 2, 4}, {1, 3}, {1, 3, 4},
{1, 4}, {2}, {2, 3}, {2, 3, 4}, {2, 4}, {3}, {3, 4}, {4}} */


## 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())  Output: {{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}}  ## Objective-C #import <Foundation/Foundation.h> + (NSArray *)powerSetForArray:(NSArray *)array { UInt32 subsetCount = 1 << array.count; NSMutableArray *subsets = [NSMutableArray arrayWithCapacity:subsetCount]; for(int subsetIndex = 0; subsetIndex < subsetCount; subsetIndex++) { NSMutableArray *subset = [[NSMutableArray alloc] init]; for (int itemIndex = 0; itemIndex < array.count; itemIndex++) { if((subsetIndex >> itemIndex) & 0x1) { [subset addObject:array[itemIndex]]; } } [subsets addObject:subset]; } return subsets; }  ## OCaml The standard library already implements a proper Set datatype. As the base type is unspecified, the powerset must be parameterized as a module. Also, the library is lacking a map operation, which we have to implement first. module PowerSet(S: Set.S) = struct include Set.Make (S) let map f s = let work x r = add (f x) r in fold work s empty ;; let powerset s = let base = singleton (S.empty) in let work x r = union r (map (S.add x) r) in S.fold work s base ;; end;; (* PowerSet *)  version for lists: let subsets xs = List.fold_right (fun x rest -> rest @ List.map (fun ys -> x::ys) rest) xs [[]]  ## OPL {string} s={"A","B","C","D"}; range r=1.. ftoi(pow(2,card(s))); {string} s2 [k in r] = {i | i in s: ((k div (ftoi(pow(2,(ord(s,i))))) mod 2) == 1)}; execute { writeln(s2); } which gives [{} {"A"} {"B"} {"A" "B"} {"C"} {"A" "C"} {"B" "C"} {"A" "B" "C"} {"D"} {"A" "D"} {"B" "D"} {"A" "B" "D"} {"C" "D"} {"A" "C" "D"} {"B" "C" "D"} {"A" "B" "C" "D"}] ## Oz Oz has a library for finite set constraints. Creating a power set is a trivial application of that: declare %% Given a set as a list, returns its powerset (again as a list) fun {Powerset Set} proc {Describe Root} %% Describe sets by lower bound (nil) and upper bound (Set) Root = {FS.var.bounds nil Set} %% enumerate all possible sets {FS.distribute naive [Root]} end AllSets = {SearchAll Describe} in %% convert to list representation {Map AllSets FS.reflect.lowerBoundList} end in {Inspect {Powerset [1 2 3 4]}} A more convential implementation without finite set constaints: fun {Powerset2 Set} case Set of nil then [nil] [] H|T thens Acc = {Powerset2 T} in {Append Acc {Map Acc fun {$ A} H|A end}}
end
end

## PARI/GP

vector(1<<#S,i,vecextract(S,i-1))
Works with: PARI/GP version 2.10.0+

The forsubset iterator was added in version 2.10.0 to efficiently iterate over combinations and power sets.

S=["a","b","c"]
forsubset(#S,s,print1(vecextract(S,s)"  "))
Output:
[]  ["a"]  ["b"]  ["c"]  ["a", "b"]  ["a", "c"]  ["b", "c"]  ["a", "b", "c"]

## Perl

Perl does not have a built-in set data-type. However, you can...

### Module: 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.

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);

Output:
[a b c]  [b c]  [a c]  [c]  [a b]  [b]  [a]  []

### Module: ntheory

Library: ntheory

The simplest solution is to use the one argument version of the combination iterator, which iterates over the power set.

use ntheory "forcomb";
my @S = qw/a b c/;
forcomb { print "[@S[@_]]  " } scalar(@S);
print "\n";

Output:
[]  [a]  [b]  [c]  [a b]  [a c]  [b c]  [a b c]

Using the two argument version of the iterator gives a solution similar to the Raku and Python array versions.

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

Output:
[]  [a]  [b]  [c]  [a b]  [a c]  [b c]  [a b c]  

Similar to the Pari/GP solution, one can also use vecextract 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 vecreduce could be done identical to the array reduce solution shown later.

use ntheory "vecextract";
my @S = qw/a b c/;
my @PS = map { "[".join(" ",vecextract(\@S,$_))."]" } 0..2**scalar(@S)-1; say join(" ",@PS);  Output: [] [a] [b] [a b] [c] [a c] [b c] [a b c] ### Module: Set::Object The CPAN module Set::Object provides a set implementation for sets of arbitrary objects, for which a powerset function could be defined and used like so: use Set::Object qw(set); sub powerset { my$p = Set::Object->new( set() );
foreach my $i (shift->elements) {$p->insert( map { set($_->elements,$i) } $p->elements ); } return$p;
}

my $set = set(1, 2, 3); my$powerset = powerset($set); print$powerset->as_string, "\n";

Output:
Set::Object(Set::Object() Set::Object(1 2 3) Set::Object(1 2) Set::Object(1 3) Set::Object(1) Set::Object(2 3) Set::Object(2) Set::Object(3))

### Simple custom hash-based set type

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

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


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

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

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

use List::Util qw(reduce);

sub powerset {
@{( reduce { [@$a, map { Set->new($_->elements, $b) } @$a ] }
[Set->new()], shift->elements )};
}

my $set = Set->new(1, 2, 3); my @subsets = powerset($set);

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

print set_to_string(@powerset), "\n";

Output:
{{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}


### 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 vecextract operation by hand.

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";  Output: 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.  The technique shown above will work with arbitrarily large sets, and uses a trivial amount of memory. ## Phix sequence powerset integer step = 1 function pst(object key, object /*data*/, object /*user_data*/) integer k = 1 while k<length(powerset) do k += step for j=1 to step do powerset[k] = append(powerset[k],key) k += 1 end for end while step *= 2 return 1 end function function power_set(integer d) powerset = repeat({},power(2,dict_size(d))) step = 1 traverse_dict(routine_id("pst"),0,d) return powerset end function integer d1234 = new_dict({{1,0},{2,0},{3,0},{4,0}}) ?power_set(d1234) integer d0 = new_dict() ?power_set(d0) setd({},0,d0) ?power_set(d0)  Output: {{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3},{4},{1,4},{2,4},{1,2,4},{3,4},{1,3,4},{2,3,4},{1,2,3,4}} {{}} {{},{{}}}  ### alternative Adapted from the one I used on Ascending_primes#powerset. with javascript_semantics function power_set(sequence s) sequence powerset = {{}}, subset = {{{},0}} while length(subset) do sequence next = {} for i=1 to length(subset) do {sequence sub, integer k} = subset[i] for j=k+1 to length(s) do sequence ni = append(deep_copy(sub),s[j]) next = append(next,{ni,j}) powerset = append(powerset,ni) end for end for subset = next end while assert(length(powerset)=power(2,length(s))) return powerset end function ?power_set({1,2,3,4}) ?power_set({4,3,2,1}) ?power_set({}) ?power_set({{}})  Output: Guaranteed to be in length order, and index order within each length. {{},{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}} {{}} {{},{{}}}  ## PHP <?php function get_subset($binary, $arr) { // based on true/false values in$binary array, include/exclude
// values from $arr$subset = array();
foreach (range(0, count($arr)-1) as$i) {
if ($binary[$i]) {
$subset[] =$arr[count($arr) -$i - 1];
}
}
return $subset; } function print_array($arr) {
if (count($arr) > 0) { echo join(" ",$arr);
} else {
echo "(empty)";
}
echo '<br>';
}

function print_power_sets($arr) { echo "POWER SET of [" . join(", ",$arr) . "]<br>";
foreach (power_set($arr) as$subset) {
print_array($subset); } } function power_set($arr) {
$binary = array(); foreach (range(1, count($arr)) as $i) {$binary[] = false;
}
$n = count($arr);
$powerset = array(); while (count($binary) <= count($arr)) {$powerset[] = get_subset($binary,$arr);
$i = 0; while (true) { if ($binary[$i]) {$binary[$i] = false;$i += 1;
} else {
$binary[$i] = true;
break;
}
}
$binary[$i] = true;
}

return $powerset; } print_power_sets(array()); print_power_sets(array('singleton')); print_power_sets(array('dog', 'c', 'b', 'a')); ?>  Output: POWER SET of [] POWER SET of [singleton] (empty) singleton POWER SET of [dog, c, b, a] (empty) a b a b c a c b c a b c dog a dog b dog a b dog c dog a c dog b c dog a b c dog  ## PicoLisp (de powerset (Lst) (ifn Lst (cons) (let L (powerset (cdr Lst)) (conc (mapcar '((X) (cons (car Lst) X)) L) L ) ) ) ) ## PL/I Translation of: REXX *process source attributes xref or(!); /*-------------------------------------------------------------------- * 06.01.2014 Walter Pachl translated from REXX *-------------------------------------------------------------------*/ powerset: Proc Options(main); Dcl (hbound,index,left,substr) Builtin; Dcl sysprint Print; Dcl s(4) Char(5) Var Init('one','two','three','four'); Dcl ps Char(1000) Var; Dcl (n,chunk,p) Bin Fixed(31); n=hbound(s); /* number of items in the list. */ ps='{} '; /* start with a null power set. */ Do chunk=1 To n; /* loop through the ... . */ ps=ps!!combn(chunk); /* a CHUNK at a time. */ End; Do While(ps>''); p=index(ps,' '); Put Edit(left(ps,p-1))(Skip,a); ps=substr(ps,p+1); End; combn: Proc(y) Returns(Char(1000) Var); /*-------------------------------------------------------------------- * returns the list of subsets with y elements of set s *-------------------------------------------------------------------*/ Dcl (y,base,bbase,ym,p,j,d,u) Bin Fixed(31); Dcl (z,l) Char(1000) Var Init(''); Dcl a(20) Bin Fixed(31) Init((20)0); Dcl i Bin Fixed(31); base=hbound(s)+1; bbase=base-y; ym=y-1; Do p=1 To y; a(p)=p; End; Do j=1 By 1; l=''; Do d=1 To y; u=a(d); l=l!!','!!s(u); End; z=z!!'{'!!substr(l,2)!!'} '; a(y)=a(y)+1; If a(y)=base Then If combu(ym) Then Leave; End; /* Put Edit('combn',y,z)(Skip,a,f(2),x(1),a); */ Return(z); combu: Proc(d) Recursive Returns(Bin Fixed(31)); Dcl (d,u) Bin Fixed(31); If d=0 Then Return(1); p=a(d); Do u=d To y; a(u)=p+1; If a(u)=bbase+u Then Return(combu(u-1)); p=a(u); End; Return(0); End; End; End; Output: {} {one} {two} {three} {four} {one,two} {one,three} {one,four} {two,three} {two,four} {three,four} {one,two,three} {one,two,four} {one,three,four} {two,three,four} {one,two,three,four} ## 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 = " "  Output: 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: {} {}  ## Prolog ### Logical (cut-free) Definition The predicate powerset(X,Y) defined here can be read as "Y is the powerset of X", it being understood that lists are used to represent sets. The predicate subseq(X,Y) is true if and only if the list X is a subsequence of the list Y. The definitions here are elementary, logical (cut-free), and efficient (within the class of comparably generic implementations). powerset(X,Y) :- bagof( S, subseq(S,X), Y). subseq( [], []). subseq( [], [_|_]). subseq( [X|Xs], [X|Ys] ) :- subseq(Xs, Ys). subseq( [X|Xs], [_|Ys] ) :- append(_, [X|Zs], Ys), subseq(Xs, Zs).  Output: ?- powerset([1,2,3], X). X = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]. % Symbolic: ?- powerset( [X,Y], S). S = [[], [X], [X, Y], [Y]]. % In reverse: ?- powerset( [X,Y], [[], [1], [1, 2], [2]] ). X = 1, Y = 2. ### Single-Functor Definition power_set( [], [[]]). power_set( [X|Xs], PS) :- power_set(Xs, PS1), maplist( append([X]), PS1, PS2 ), % i.e. prepend X to each PS1 append(PS1, PS2, PS).  Output: ?- power_set([1,2,3,4,5,6,7,8], X), length(X,N), writeln(N). 256  ### Constraint Handling Rules CHR is a programming language created by Professor Thom Frühwirth. Works with SWI-Prolog and module chr written by Tom Schrijvers and Jan Wielemaker. :- use_module(library(chr)). :- chr_constraint chr_power_set/2, chr_power_set/1, clean/0. clean @ clean \ chr_power_set(_) <=> true. clean @ clean <=> true. only_one @ chr_power_set(A) \ chr_power_set(A) <=> true. creation @ chr_power_set([H | T], A) <=> append(A, [H], B), chr_power_set(T, A), chr_power_set(T, B), chr_power_set(B). empty_element @ chr_power_set([], _) <=> chr_power_set([]).  Output:  ?- chr_power_set([1,2,3,4], []), findall(L, find_chr_constraint(chr_power_set(L)), LL), clean. LL = [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,4],[1,3],[1,3,4],[1,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4],[]] .  ## PureBasic This code is for console mode. If OpenConsole() Define argc=CountProgramParameters() If argc>=(SizeOf(Integer)*8) Or argc<1 PrintN("Set out of range.") End 1 Else Define i, j, text$
Define.q bset=1<<argc
Print("{")
For i=0 To bset-1   ; check all binary combinations
If Not i: text$= "{" Else : text$=", {"
EndIf
k=0
For j=0 To argc-1  ; step through each bit
If i&(1<<j)
If k: text$+", ": EndIf ; pad the output text$+ProgramParameter(j): k+1  ; append each matching bit
EndIf
Next j
Print(text$+"}") Next i PrintN("}") EndIf EndIf  Output: C:\Users\PureBasic_User\Desktop>"Power Set.exe" 1 2 3 4 {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}} ## Python def list_powerset(lst): # the power set of the empty set has one element, the empty set result = [[]] for x in lst: # for every additional element in our set # the power set consists of the subsets that don't # contain this element (just take the previous power set) # plus the subsets that do contain the element (use list # comprehension to add [x] onto everything in the # previous power set) result.extend([subset + [x] for subset in result]) return result # the above function in one statement def list_powerset2(lst): return reduce(lambda result, x: result + [subset + [x] for subset in result], lst, [[]]) def powerset(s): return frozenset(map(frozenset, list_powerset(list(s))))  list_powerset computes the power set of a list of distinct elements. powerset simply converts the input and output from lists to sets. We use the frozenset type here for immutable sets, because unlike mutable sets, it can be put into other sets. Example: >>> list_powerset([1,2,3]) [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] >>> powerset(frozenset([1,2,3])) frozenset([frozenset([3]), frozenset([1, 2]), frozenset([]), frozenset([2, 3]), frozenset([1]), frozenset([1, 3]), frozenset([1, 2, 3]), frozenset([2])])  #### Further Explanation If you take out the requirement to produce sets and produce list versions of each powerset element, then add a print to trace the execution, you get this simplified version of the program above where it is easier to trace the inner workings def powersetlist(s): r = [[]] for e in s: print "r: %-55r e: %r" % (r,e) r += [x+[e] for x in r] return r s= [0,1,2,3] print "\npowersetlist(%r) =\n %r" % (s, powersetlist(s))  Output: r: [[]] e: 0 r: [[], [0]] e: 1 r: [[], [0], [1], [0, 1]] e: 2 r: [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]] e: 3 powersetlist([0, 1, 2, 3]) = [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2], [3], [0, 3], [1, 3], [0, 1, 3], [2, 3], [0, 2, 3], [1, 2, 3], [0, 1, 2, 3]]  ### Binary Count method If you list the members of the set and include them according to if the corresponding bit position of a binary count is true then you generate the powerset. (Note that only frozensets can be members of a set in the second function) def powersequence(val): ''' Generate a 'powerset' for sequence types that are indexable by integers. Uses a binary count to enumerate the members and returns a list Examples: >>> powersequence('STR') # String ['', 'S', 'T', 'ST', 'R', 'SR', 'TR', 'STR'] >>> powersequence([0,1,2]) # List [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]] >>> powersequence((3,4,5)) # Tuple [(), (3,), (4,), (3, 4), (5,), (3, 5), (4, 5), (3, 4, 5)] >>> ''' vtype = type(val); vlen = len(val); vrange = range(vlen) return [ reduce( lambda x,y: x+y, (val[i:i+1] for i in vrange if 2**i & n), vtype()) for n in range(2**vlen) ] def powerset(s): ''' Generate the powerset of s Example: >>> powerset(set([6,7,8])) set([frozenset([7]), frozenset([8, 6, 7]), frozenset([6]), frozenset([6, 7]), frozenset([]), frozenset([8]), frozenset([8, 7]), frozenset([8, 6])]) ''' return set( frozenset(x) for x in powersequence(list(s)) )  ### Recursive Alternative This is an (inefficient) recursive version that almost reflects the recursive definition of a power set as explained in http://en.wikipedia.org/wiki/Power_set#Algorithms. It does not create a sorted output. def p(l): if not l: return [[]] return p(l[1:]) + [[l[0]] + x for x in p(l[1:])]  ### Python: Standard documentation Pythons documentation has a method that produces the groupings, but not as sets: >>> from pprint import pprint as pp >>> from itertools import chain, combinations >>> >>> def powerset(iterable): "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) >>> pp(set(powerset({1,2,3,4}))) {(), (1,), (1, 2), (1, 2, 3), (1, 2, 3, 4), (1, 2, 4), (1, 3), (1, 3, 4), (1, 4), (2,), (2, 3), (2, 3, 4), (2, 4), (3,), (3, 4), (4,)} >>>  ## Qi Translation of: Scheme (define powerset [] -> [[]] [A|As] -> (append (map (cons A) (powerset As)) (powerset As))) ## 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.  [ 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 ] Output: 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 [ [ ] ] [ ] [ [ ] ]  ## R ### Non-recursive version The conceptual basis for this algorithm is the following: for each element in the set: for each subset constructed so far: new subset = (subset + element)  This method is much faster than a recursive method, though the speed is still O(2^n). powerset <- function(set){ ps <- list() ps[[1]] <- numeric() #Start with the empty set. for(element in set){ #For each element in the set, take all subsets temp <- vector(mode="list",length=length(ps)) #currently in "ps" and create new subsets (in "temp") for(subset in 1:length(ps)){ #by adding "element" to each of them. temp[[subset]] = c(ps[[subset]],element) } ps <- c(ps,temp) #Add the additional subsets ("temp") to "ps". } ps } powerset(1:4)  The list "temp" is a compromise between the speed costs of doing arithmetic and of creating new lists (since R lists are immutable, appending to a list means actually creating a new list object). Thus, "temp" collects new subsets that are later added to the power set. This improves the speed by 4x compared to extending the list "ps" at every step. ### Recursive version Library: sets The sets package includes a recursive method to calculate the power set. However, this method takes ~100 times longer than the non-recursive method above. library(sets)  An example with a vector. v <- (1:3)^2 sv <- as.set(v) 2^sv  {{}, {1}, {4}, {9}, {1, 4}, {1, 9}, {4, 9}, {1, 4, 9}}  An example with a list. l <- list(a=1, b="qwerty", c=list(d=TRUE, e=1:3)) sl <- as.set(l) 2^sl  {{}, {1}, {"qwerty"}, {<<list(2)>>}, {1, <<list(2)>>}, {"qwerty", 1}, {"qwerty", <<list(2)>>}, {"qwerty", 1, <<list(2)>>}}  ## Racket ;;; Direct translation of 'functional' ruby method (define (powerset s) (for/fold ([outer-set (set(set))]) ([element s]) (set-union outer-set (list->set (set-map outer-set (λ(inner-set) (set-add inner-set element)))))))  ## Raku (formerly Perl 6) Works with: rakudo version 2014-02-25 sub powerset(Set$s) { $s.combinations.map(*.Set).Set } say powerset set <a b c d>;  Output: set(set(), set(a), set(b), set(c), set(d), set(a, b), set(a, c), set(a, d), set(b, c), set(b, d), set(c, d), set(a, b, c), set(a, b, d), set(a, c, d), set(b, c, d), set(a, b, c, d)) If you don't care about the actual Set type, the .combinations method by itself may be good enough for you: .say for <a b c d>.combinations  Output:  a b c d a b a c a d b c b d c d a b c a b d a c d b c d a b c d ## Rascal import Set; public set[set[&T]] PowerSet(set[&T] s) = power(s); Output: rascal>PowerSet({1,2,3,4}) set[set[int]]: { {4,3}, {4,2,1}, {4,3,1}, {4,2}, {4,3,2}, {4,1}, {4,3,2,1}, {4}, {3}, {2,1}, {3,1}, {2}, {3,2}, {1}, {3,2,1}, {} } ## REXX /*REXX program displays a power set; items may be anything (but can't have blanks).*/ parse arg S /*allow the user specify optional set. */ if S='' then S= 'one two three four' /*Not specified? Then use the default.*/ @= '{}' /*start process with a null power set. */ N= words(S); do chunk=1 for N /*traipse through the items in the set.*/ @=@ combN(N, chunk) /*take N items, a CHUNK at a time. */ end /*chunk*/ w= length(2**N) /*the number of items in the power set.*/ do k=1 for words(@) /* [↓] show combinations, 1 per line.*/ say right(k, w) word(@, k) /*display a single combination to term.*/ end /*k*/ exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ combN: procedure expose S; parse arg x,y; base= x + 1; bbase= base - y !.= 0 do p=1 for y; !.p= p end /*p*/$=                                                         /* [↓] build powerset*/
do j=1;                 L=
do d=1  for y;       L= L','word(S, !.d)
end   /*d*/
$=$  '{'strip(L, "L", ',')"}";                  !.y= !.y + 1
if !.y==base  then  if .combU(y - 1)  then leave
end      /*j*/
return strip($) /*return with a partial power set chunk*/ /*──────────────────────────────────────────────────────────────────────────────────────*/ .combU: procedure expose !. y bbase; parse arg d; if d==0 then return 1 p= !.d do u=d to y; !.u= p + 1; if !.u==bbase+u then return .combU(u-1) p= !.u /* ↑ */ end /*u*/ /*recurse──►───┘ */ return 0  output when using the default input:  1 {} 2 {one} 3 {two} 4 {three} 5 {four} 6 {one,two} 7 {one,three} 8 {one,four} 9 {two,three} 10 {two,four} 11 {three,four} 12 {one,two,three} 13 {one,two,four} 14 {one,three,four} 15 {two,three,four} 16 {one,two,three,four}  ## 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) + "}" Output: {{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3},{4},{1,4},{2,4},{1,2,4},{3,4},{1,3,4},{2,3,4},{1,2,3,4}}  ## RPL Works with: Halcyon Calc version 4.2.8 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  Output: 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: { { } }  ## Ruby # Based on http://johncarrino.net/blog/2006/08/11/powerset-in-ruby/ # See the link if you want a shorter version. # This was intended to show the reader how the method works. class Array # Adds a power_set method to every array, i.e.: [1, 2].power_set def power_set # Injects into a blank array of arrays. # acc is what we're injecting into # you is each element of the array inject([[]]) do |acc, you| ret = [] # Set up a new array to add into acc.each do |i| # For each array in the injected array, ret << i # Add itself into the new array ret << i + [you] # Merge the array with a new array of the current element end ret # Return the array we're looking at to inject more. end end # A more functional and even clearer variant. def func_power_set inject([[]]) { |ps,item| # for each item in the Array ps + # take the powerset up to now and add ps.map { |e| e + [item] } # it again, with the item appended to each element } end end #A direct translation of the "power array" version above require 'set' class Set def powerset inject(Set[Set[]]) do |ps, item| ps.union ps.map {|e| e.union (Set.new [item])} end end end p [1,2,3,4].power_set p %w(one two three).func_power_set p Set[1,2,3].powerset  Output: [[], [4], [3], [3, 4], [2], [2, 4], [2, 3], [2, 3, 4], [1], [1, 4], [1, 3], [1, 3, 4], [1, 2], [1, 2, 4], [1, 2, 3], [1, 2, 3, 4]] [[], ["one"], ["two"], ["one", "two"], ["three"], ["one", "three"], ["two", "three"], ["one", "two", "three"]] #<Set: {#<Set: {}>, #<Set: {1}>, #<Set: {2}>, #<Set: {1, 2}>, #<Set: {3}>, #<Set: {1, 3}>, #<Set: {2, 3}>, #<Set: {1, 2, 3}>}>  ## Rust This implementation consumes the input set, requires that the type T has a full order a.k.a implements the Ord trait and that T is clonable. 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); }  Output: {{}, {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"}}  ## SAS options mprint mlogic symbolgen source source2; %macro SubSets (FieldCount = ); data _NULL_; Fields = &FieldCount; SubSets = 2**Fields; call symput ("NumSubSets", SubSets); run; %put &NumSubSets; data inital; %do j = 1 %to &FieldCount; F&j. = 1; %end; run; data SubSets; set inital; RowCount =_n_; call symput("SetCount",RowCount); run; %put SetCount ; %do %while (&SetCount < &NumSubSets); data loop; %do j=1 %to &FieldCount; if rand('GAUSSIAN') > rand('GAUSSIAN') then F&j. = 1; %end; data SubSets_ ; set SubSets loop; run; proc sort data=SubSets_ nodupkey; by F1 - F&FieldCount.; run; data Subsets; set SubSets_; RowCount =_n_; run; proc sql noprint; select max(RowCount) into :SetCount from SubSets; quit; run; %end; %Mend SubSets;  You can then call the macro as: %SubSets(FieldCount = 5);  The output will be the dataset SUBSETS and will have a 5 columns F1, F2, F3, F4, F5 and 32 columns, one with each combination of 1 and missing values. Output: Obs F1 F2 F3 F4 F5 RowCount 1 . . . . . 1 2 . . . . 1 2 3 . . . 1 . 3 4 . . . 1 1 4 5 . . 1 . . 5 6 . . 1 . 1 6 7 . . 1 1 . 7 8 . . 1 1 1 8 9 . 1 . . . 9 10 . 1 . . 1 10 11 . 1 . 1 . 11 12 . 1 . 1 1 12 13 . 1 1 . . 13 14 . 1 1 . 1 14 15 . 1 1 1 . 15 16 . 1 1 1 1 16 17 1 . . . . 17 18 1 . . . 1 18 19 1 . . 1 . 19 20 1 . . 1 1 20 21 1 . 1 . . 21 22 1 . 1 . 1 22 23 1 . 1 1 . 23 24 1 . 1 1 1 24 25 1 1 . . . 25 26 1 1 . . 1 26 27 1 1 . 1 . 27 28 1 1 . 1 1 28 29 1 1 1 . . 29 30 1 1 1 . 1 30 31 1 1 1 1 . 31 32 1 1 1 1 1 32  ## Scala 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]")
}


Another option that produces lazy sequence of the sets:

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


A tail-recursive version:

def powerset[A](s: Set[A]) = {
def powerset_rec(acc: List[Set[A]], remaining: List[A]): List[Set[A]] = remaining match {
case Nil => acc
}
powerset_rec(List(Set.empty[A]), s.toList)
}


## Scheme

Translation of: Common Lisp
(define (power-set set)
(if (null? set)
'(())
(let ((rest (power-set (cdr set))))
(append (map (lambda (element) (cons (car set) element))
rest)
rest))))

(display (power-set (list 1 2 3)))
(newline)

(display (power-set (list "A" "C" "E")))
(newline)

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

Call/cc generation:
(define (power-set lst)
(define (iter yield)
(let recur ((a '()) (b lst))
(if (null? b) (set! yield
(call-with-current-continuation
(lambda (resume)
(set! iter resume)
(yield a))))
(begin (recur (append a (list (car b))) (cdr b))
(recur a (cdr b)))))

;; signal end of generation
(yield 'end-of-seq))

(lambda () (call-with-current-continuation iter)))

(define x (power-set '(1 2 3)))
(let loop ((a (x)))
(if (eq? a 'end-of-seq) #f
(begin
(display a)
(newline)
(loop (x)))))

Output:
(1 2)
(1 3)
(1)
(2 3)
(2)
(3)
()
Iterative:
(define (power_set_iter set)
(let loop ((res '(())) (s set))
(if (empty? s)
res
(loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s)))))

Output:
'((e d c b a)
(e d c b)
(e d c a)
(e d c)
(e d b a)
(e d b)
(e d a)
(e d)
(e c b a)
(e c b)
(e c a)
(e c)
(e b a)
(e b)
(e a)
(e)
(d c b a)
(d c b)
(d c a)
(d c)
(d b a)
(d b)
(d a)
(d)
(c b a)
(c b)
(c a)
(c)
(b a)
(b)
(a)
())


$include "seed7_05.s7i"; const func array bitset: powerSet (in bitset: baseSet) is func result var array bitset: pwrSet is [] (bitset.value); local var integer: element is 0; var integer: index is 0; var bitset: aSet is bitset.value; begin for element range baseSet do for key index range pwrSet do aSet := pwrSet[index]; if element not in aSet then incl(aSet, element); pwrSet &:= aSet; end if; end for; end for; end func; const proc: main is func local var bitset: aSet is bitset.value; begin for aSet range powerSet({1, 2, 3, 4}) do writeln(aSet); end for; end func; Output: {} {1} {2} {1, 2} {3} {1, 3} {2, 3} {1, 2, 3} {4} {1, 4} {2, 4} {1, 2, 4} {3, 4} {1, 3, 4} {2, 3, 4} {1, 2, 3, 4}  ## SETL Pfour := pow({1, 2, 3, 4}); Pempty := pow({}); PPempty := pow(Pempty); print(Pfour); print(Pempty); print(PPempty);  Output: {{} {1} {2} {3} {4} {1 2} {1 3} {1 4} {2 3} {2 4} {3 4} {1 2 3} {1 2 4} {1 3 4} {2 3 4} {1 2 3 4}} {{}} {{} {{}}} ## Sidef var arr = %w(a b c) for i in (0 .. arr.len) { say arr.combinations(i) }  Output: [[]] [["a"], ["b"], ["c"]] [["a", "b"], ["a", "c"], ["b", "c"]] [["a", "b", "c"]]  ## 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. Output: [[]] [[],[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]]  ## Smalltalk Works with: GNU Smalltalk Code from Bonzini's blog Collection extend [ power [ ^(0 to: (1 bitShift: self size) - 1) readStream collect: [ :each || i | i := 0. self select: [ :elem | (each bitAt: (i := i + 1)) = 1 ] ] ] ].  #(1 2 4) power do: [ :each | each asArray printNl ]. #( 'A' 'C' 'E' ) power do: [ :each | each asArray printNl ].  ## Standard ML version for lists: fun subsets xs = foldr (fn (x, rest) => rest @ map (fn ys => x::ys) rest) [[]] xs  ## Swift Works with: Swift version Revision 4 - tested with Xcode 9.2 playground 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])  Output: { {2, 4} {4, 1} {4}, {2, 4, 1} {2, 1} Set([]) {1} {2} } //Example: powersetFrom(["a", "b", "d"])  Output: { {"b", "d"} {"b"} {"d"}, {"a"} {"b", "d", "a"} Set([]) {"d", "a"} {"b", "a"} } ## Tcl proc subsets {l} { set res [list [list]] foreach e$l {
foreach subset $res {lappend res [lappend subset$e]}
}
return $res } puts [subsets {a b c d}]  Output: {} a b {a b} c {a c} {b c} {a b c} d {a d} {b d} {a b d} {c d} {a c d} {b c d} {a b c d} ### Binary Count Method proc powersetb set { set res {} for {set i 0} {$i < 2**[llength $set]} {incr i} { set pos -1 set pset {} foreach el$set {
if {$i & 1<<[incr pos]} {lappend pset$el}
}
lappend res $pset } return$res
}


## TXR

The power set function can be written concisely like this:

(defun power-set (s)
(mappend* (op comb s) (range 0 (length s))))

This generates the lists of combinations of all possible lengths, from 0 to the length of s and catenates them. The comb function generates a lazy list, so it is appropriate to use mappend* (the lazy version of mappend) to keep the behavior lazy.

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

@(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)
Output:
$txr rosetta/power-set.txr 1 2 3 {1, 2, 3} {1, 2} {1, 3} {1} {2, 3} {2} {3} {} The above power-set function generalizes to strings and vectors. @(do (defun power-set (s) (mappend* (op comb s) (range 0 (length s)))) (prinl (power-set "abc")) (prinl (power-set "b")) (prinl (power-set "")) (prinl (power-set #(1 2 3)))) Output: $ 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))

## UNIX Shell

From here

p() { [ $# -eq 0 ] && echo || (shift; p "$@") | while read r ; do echo -e "$1$r\n\$r"; done }


Usage

|p cat | sort | uniq
A
C
E
^D


## UnixPipes

| cat A
a
b
c

| cat A |\
xargs -n 1 ksh -c 'echo \{cat A\}' |\
xargs |\
sed -e 's; ;,;g' \
-e 's;^;echo ;g' \
-e 's;\},;}\\ ;g' |\
ksh |unfold wc -l A |\
xargs -n1 -I{} ksh -c 'echo {} |\
unfold 1 |sort -u |xargs' |sort -u

a
a b
a b c
a c
b
b c
c


## Ursala

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

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

test program:

#cast %sSS

test = powerset {'a','b','c','d'}
Output:
{
{},
{'a'},
{'a','b'},
{'a','b','c'},
{'a','b','c','d'},
{'a','b','d'},
{'a','c'},
{'a','c','d'},
{'a','d'},
{'b'},
{'b','c'},
{'b','c','d'},
{'b','d'},
{'c'},
{'c','d'},
{'d'}}

## V

V has a built in called powerlist

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


its implementation in std.v is (like joy)

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


## VBA

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
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
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
Debug.Print print_set(power_set(rcset))
Debug.Print
End Sub

Output:
{{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}
{{}}
{{}, {{}}}

## VBScript

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")

Output:
{{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3},{4},{1,4},{2,4},{1,2,4},{3,4},{1,3,4},{2,3,4},{1,2,3,4}}

## Wren

Library: 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.

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

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


## XPL0

func PowSet(Set, Size);
int  Set, Size;
[ChOut(0, ^{);
for N:= 0 to 1<<Size -1 do
[if N>0 then ChOut(0, ^,);
ChOut(0, ^{);
for M:= 0 to Size-1 do
[if DoComma then ChOut(0, ^,);
IntOut(0, Set(M));
DoComma:= true;
];
];
ChOut(0, ^});
];
Text(0, "}^m^j");
];

[PowSet([2, 3, 5, 7], 4);
PowSet([1], 1);
PowSet(0, 0);
]
Output:
{{},{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}}
{{}}


## zkl

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

fcn pwerSet(list){
(0).pump(list.len(),List, Utils.Helpers.pickNFrom.fp1(list),
T(Void.Write,Void.Write) ) .append(list)
}
foreach n in (5){
ps:=pwerSet((1).pump(n,List)); ps.println(" Size = ",ps.len());
}
Output:
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
`