Anonymous user
Power set: Difference between revisions
Undo revision 188585 by Siskus (talk)
(→{{header|Scala}}: reverse_::: used for speed improvemet) |
|||
Line 2:
A [[set]] is a collection (container) of certain values, without any particular order, and no repeated values. It corresponds with a finite set in mathematics. A set can be implemented as an associative array (partial mapping) in which the value of each key-value pair is ignored.
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}}.
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> } }
=={{header|Ada}}==
This solution prints the power set of words read from the command line.
<lang ada>with Ada.Text_IO, Ada.Command_Line;
procedure Power_Set is
Line 50 ⟶ 56:
end loop;
Print_All_Subsets(Set); -- do the work
end Power_Set;</lang>
{{out}}
<pre>>./power_set cat dog mouse
{ cat, dog, mouse }
{ cat, dog }
Line 64 ⟶ 74:
{ 2 }
{ }</pre>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68|Revision 1 - no extensions to language used}}
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of FORMATted transput}}
Requires: ALGOL 68g mk14.1+
<lang algol68>MODE MEMBER = INT;
PROC power set = ([]MEMBER s)[][]MEMBER:(
Line 93 ⟶ 108:
printf(($"set["d"] = "$,member, repr set, set[member],$l$))
OD
)</lang>
Output:
<pre>
set[1] = ();
set[2] = (1);
set[3] = (2);
Line 100 ⟶ 118:
set[6] = (1, 4);
set[7] = (2, 4);
set[8] = (1, 2, 4);
</pre>
=={{header|AutoHotkey}}==
<lang autohotkey>a = 1,a,-- ; elements separated by commas
StringSplit a, a, `, ; a0 = #elements, a1,a2,... = elements of the set
Line 113 ⟶ 134:
}
MsgBox % RegExReplace(SubStr(t,1,StrLen(t)-1),",}","}")</lang>
=={{header|BBC BASIC}}==
<lang bbcbasic> DIM list$(3) : list$() = "1", "2", "3", "4"
PRINT FNpowerset(list$())
END
Line 130 ⟶ 153:
s$ += "},"
NEXT i%
= LEFT$(s$) + "}"</lang>
'''Output:'''
<pre>
{{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3},{4},{1,4},{2,4},{1,2,4},{3,4},{1,3,4},{2,3,4},{1,2,3,4}}
</pre>
=={{header|Bracmat}}==
= done todo first
. !arg:(?done.?todo)
Line 142 ⟶ 169:
)
& out$(powerset$(.1 2 3 4))
);</lang>
Output:
<pre> 1 2 3 4
, 1 2 3
, 1 2 4
Line 158 ⟶ 187:
, 4
,</pre>
=={{header|Burlesque}}==
<lang burlesque>
blsq ) {1 2 3 4}R@
{{} {1} {2} {1 2} {3} {1 3} {2 3} {1 2 3} {4} {1 4} {2 4} {1 2 4} {3 4} {1 3 4} {2 3 4} {1 2 3 4}}
</lang>
=={{header|C}}==
struct node {
Line 193 ⟶ 226:
powerset(argv + 1, argc - 1, 0);
return 0;
}</lang>
{{out}}
<pre>
% ./a.out 1 2 3
[ ]
[ 3 ]
Line 201 ⟶ 237:
[ 3 1 ]
[ 2 1 ]
[ 3 2 1 ]
</pre>
=={{header|C++}}==
=== Non-recursive version ===
<lang cpp>#include <iostream>
#include <set>
Line 282 ⟶ 321:
std::cout << " }\n";
}
}</lang
Output:
<pre>
{ }
{ 2 }
Line 302 ⟶ 344:
=== Recursive version ===
<lang cpp>#include <iostream>
#include <set>
Line 326 ⟶ 369:
{
return powerset(s, s.size());
}
</lang>
=={{header|C sharp|C#}}==
<lang csharp>
public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
return from m in Enumerable.Range(0, 1 << list.Count)
Line 348 ⟶ 393:
result.Select(subset =>
string.Join(",", subset.Select(clr => clr.ToString()).ToArray())).ToArray()));
}
</lang>
Output:
<lang>
Red
Green
Line 364 ⟶ 415:
Green,Blue,Yellow
Red,Green,Blue,Yellow
</lang>
An alternative implementation for an arbitrary number of elements:
<lang csharp>
public IEnumerable<IEnumerable<T>> GetPowerSet<T>(IEnumerable<T> input) {
var seed = new List<IEnumerable<T>>() { Enumerable.Empty<T>() }
as IEnumerable<IEnumerable<T>>;
Line 371 ⟶ 426:
return input.Aggregate(seed, (a, b) =>
a.Concat(a.Select(x => x.Concat(new List<T>() { b }))));
}
</lang>
=={{header|Clojure}}==
<lang Clojure>(use '[clojure.math.combinatorics :only [subsets] ])
Line 390 ⟶ 447:
(powerset #{1 2 3})</lang>
=={{header|CoffeeScript}}==
<lang coffeescript>
print_power_set = (arr) ->
console.log "POWER SET of #{arr}"
for subset in power_set(arr)
Line 420 ⟶ 478:
print_power_set []
print_power_set [4, 2, 1]
print_power_set ['dog', 'c', 'b', 'a']
</lang>
output
<lang>
> coffee power_set.coffee
POWER SET of
[]
Line 448 ⟶ 510:
[ 'dog', 'c', 'a' ]
[ 'dog', 'c', 'b' ]
[ 'dog', 'c', 'b', 'a' ]
</lang>
=={{header|ColdFusion}}==
Port from the [[#JavaScript|JavaScript]] version, compatible with ColdFusion 8+ or Railo 3+
<lang javascript>public array function powerset(required array data)
{
var ps = [""];
Line 467 ⟶ 533:
}
var res = powerset([1,2,3,4]);</lang>
Outputs:
<pre>["","1","2","1,2","3","1,3","2,3","1,2,3","4","1,4","2,4","1,2,4","3,4","1,3,4","2,3,4","1,2,3,4"]</pre>
=={{header|Common Lisp}}==
(reduce #'(lambda (item ps)
(append (mapcar #'(lambda (e) (cons item e))
Line 477 ⟶ 546:
s
:from-end t
:initial-value '(())))</lang>
Output:
>(power-set '(1 2 3))
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) NIL)
Alternate, more recursive (same output):
<lang lisp>(defun powerset (l)
Line 487 ⟶ 559:
(append (mapcar #'(lambda (elt) (cons (car l) elt)) prev)
prev))))</lang>
Imperative-style using LOOP:
<lang lisp>(defun powerset (xs)
Line 504 ⟶ 578:
>(power-set '(1 2 3))
((1) (1 3) (1 2 3) (1 2) (2) (2 3) (3) NIL)
=={{header|D}}==
<lang d>T[][] powerSet(T)(in T[] s) pure nothrow @safe {
auto r = new typeof(return)(1, 0);
foreach (e; s) {
Line 520 ⟶ 596:
[1, 2, 3].powerSet.writeln;
}</lang>
{{out}}
<pre>[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]</pre>
===Lazy Version===
Compile with -version=power_set2_main to run the main.
Line 560 ⟶ 638:
[1, 2, 3].powerSet.writeln;
}
}</lang>
Same output.
A [[Power_set/D|set implementation]] and its power set function.
=={{header|Déjà Vu}}==
In Déjà Vu, sets are dictionaries with all values <code>true</code> and the default set to <code>false</code>.
<lang dejavu>powerset s:
local :out [ set{ } ]
for value in keys s:
Line 573 ⟶ 656:
out
!. powerset set{ 1 2 3 4 }</lang>
{{out}}
<pre>[ set{ } set{ 4 } set{ 3 4 } set{ 3 } set{ 2 3 } set{ 2 3 4 } set{ 2 4 } set{ 2 } set{ 1 2 } set{ 1 2 4 } set{ 1 2 3 4 } set{ 1 2 3 } set{ 1 3 } set{ 1 3 4 } set{ 1 4 } set{ 1 } ]</pre>
=={{header|E}}==
<lang e>pragma.enable("accumulator")
def powerset(s) {
Line 583 ⟶ 671:
})
}
}</lang>
It would also be possible to define an object which is the powerset of a provided set without actually instantiating all of its members immediately. [[Category:E examples needing attention]]
=={{header|Erlang}}==
<pre>
For [1 2 3]:
[ ] | 0 0 0 | 0
[ 3] | 0 0 1 | 1
Line 596 ⟶ 688:
[1 2 ] | 1 1 0 | 6
[1 2 3] | 1 1 1 | 7
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
</pre>
<lang erlang>powerset(Lst) ->
N = length(Lst),
Max = trunc(math:pow(2,N)),
[[lists:nth(Pos+1,Lst) || Pos <- lists:seq(0,N-1), I band (1 bsl Pos) =/= 0]
|| I <- lists:seq(0,Max-1)].</lang>
Which outputs:
<code>[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3], [4], [1,4], [2,4], [1,2,4], [3,4], [1,3,4], [2,3,4], [1,2,3,4]]</code>
Alternate shorter and more efficient version:
<lang erlang>powerset([]) -> [[]];
powerset([H|T]) -> PT = powerset(T),
[ [H|X] || X <- PT ] ++ PT.</lang>
or even more efficient version:
<lang erlang>powerset([]) -> [[]];
powerset([H|T]) -> PT = powerset(T),
powerset(H, PT, PT).
Line 608 ⟶ 711:
powerset(_, [], Acc) -> Acc;
powerset(X, [H|T], Acc) -> powerset(X, T, [[X|H]|Acc]).</lang>
=={{header|F Sharp|F#}}==
<lang fsharp>
let subsets xs = List.foldBack (fun x rest -> rest @ List.map (fun ys -> x::ys) rest) xs [[]]
</lang>
alternatively with list comprehension
<lang fsharp>
let rec pow =
function
| [] -> [[]]
| x::xs -> [for i in pow xs do yield! [i;x::i]]
</lang>
=={{header|Factor}}==
<lang factor>USING: kernel prettyprint sequences arrays sets hash-sets ;
IN: powerset
: add ( set elt -- newset ) 1array <hash-set> union ;
: powerset ( set -- newset ) members { HS{ } } [ dupd [ add ] curry map append ] reduce <hash-set> ;</lang>
Usage:
<lang factor>( scratchpad ) HS{ 1 2 3 4 } powerset .
HS{
HS{ 1 2 3 4 }
Line 638 ⟶ 753:
HS{ 1 3 4 }
HS{ 2 3 4 }
}</
=={{header|Forth}}==
{{works with|4tH|3.61.0}}.
{{trans|C}}
<lang forth>: ?print dup 1 and if over args type space then ;
: .set begin dup while ?print >r 1+ r> 1 rshift repeat drop drop ;
: .powerset 0 do ." ( " 1 i .set ." )" cr loop ;
Line 647 ⟶ 765:
: powerset 1 argn check-none check-size 1- lshift .powerset ;
powerset</lang>
Output:
<pre>
$ 4th cxq powerset.4th 1 2 3 4
( )
( 1 )
Line 663 ⟶ 784:
( 1 3 4 )
( 2 3 4 )
( 1 2 3 4 )
</pre>
=={{header|Frink}}==
<lang frink>
a = new set[1,2,3,4]
a.subsets[]
</lang>
=={{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.
<lang funl>def powerset( s ) = s.subsets().toSet()</lang>
The powerset function could be implemented in FunL directly as:
<lang funl>def
powerset( {} ) = {{}}
powerset( s ) =
Line 683 ⟶ 813:
def powerset( s ) = foldr( \x, acc -> acc + map( a -> {x} + a, acc), {{}}, s )
println( powerset({1, 2, 3, 4}) )</lang>
{{out}}
<pre>
{{}, {4}, {1, 2}, {1, 3}, {2, 3, 4}, {3}, {1, 2, 3, 4}, {1, 4}, {1, 2, 3}, {2}, {1, 2, 4}, {1}, {3, 4}, {2, 3}, {2, 4}, {1, 3, 4}}
</pre>
=={{header|GAP}}==
Combinations([1, 2, 3]);
# [ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 2, 3 ], [ 3 ] ]
Line 694 ⟶ 830:
# [ [ ], [ 1 ], [ 1, 1 ], [ 1, 1, 2 ], [ 1, 1, 2, 3 ], [ 1, 1, 3 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ],
# [ 2 ], [ 2, 3 ], [ 3 ] ]</lang>
=={{header|Go}}==
Instead, this solution uses a simple (non-associative) slice as a set representation. To ensure uniqueness, the element interface requires an equality method, which is used by the
set add method. Adding elements with the add method ensures the uniqueness property.
The power set method implemented here does not need the add method though. The algorithm
ensures that the result will be a valid set as long as the input is a valid set. This allows the more efficient append function to be used.
<lang go>package main
Line 809 ⟶ 947:
fmt.Println(ps)
fmt.Println("length =", len(ps))
}</lang>
{{out}}
<pre>
{1 2 3 4}
length = 4
{{} {1} {2} {1 2} {3} {1 3} {2 3} {1 2 3} {4} {1 4} {2 4} {1 2 4} {3 4} {1 3 4} {2 3 4} {1 2 3 4}}
length = 16
</pre>
=={{header|Groovy}}==
<lang groovy>def comb
comb = { m, List list ->
def n = list.size()
Line 828 ⟶ 971:
def powerSet = { set ->
(0..(set.size())).inject([]){ list, i -> list + comb(i,set as List)}.collect { it as LinkedHashSet } as LinkedHashSet
}</lang>
Test program:
<lang groovy>def vocalists = [ "C", "S", "N", "Y" ] as LinkedHashSet
println "${vocalists}"
println powerSet(vocalists)</lang>
Line 839 ⟶ 985:
=={{header|Haskell}}==
import Control.Monad
Line 846 ⟶ 992:
listPowerset :: [a] -> [[a]]
listPowerset = filterM (const [True, False])</lang>
<tt>listPowerset</tt> describes the result as all possible (using the list monad) filterings (using <tt>filterM</tt>) of the input list, regardless (using <tt>const</tt>) of each item's value. <tt>powerset</tt> simply converts the input and output from lists to sets.
'''Alternate Solution'''
<lang Haskell>powerset [] = [[]]
powerset (head:tail) = acc ++ map (head:) acc where acc = powerset tail
or
<lang Haskell>powerset = foldr (\x acc -> acc ++ map (x:) acc) [[]]</lang>
Examples:
Line 865 ⟶ 1,014:
'''Alternate solution'''
A method using only set operations and set mapping is also possible. Ideally, <code>Set</code> would be defined as a Monad, but that's impossible given the constraint that the type of inputs to Set.map (and a few other functions) be ordered.
<lang Haskell>import qualified Data.Set as Set
type Set=Set.Set
unionAll :: (Ord a) => Set (Set a) -> Set a
Line 880 ⟶ 1,030:
powerSet :: (Ord a) => Set a -> Set (Set a)
powerSet = (Set.fold (slift Set.union) (Set.singleton Set.empty)) . Set.map makeSet</lang>
<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]]</lang>
=={{header|Icon}} and {{header|Unicon}}==
The two examples below show the similarities and differences between constructing an explicit representation of the solution, i.e. a set containing the powerset, and one using generators. The basic recursive algorithm is the same in each case, but wherever the first stores part of the result away, the second uses 'suspend' to immediately pass the result back to the caller. The caller may then decide to store the results in a set, a list, or dispose of each one as it appears.
===Set building===
The following version returns a set containing the powerset:
<lang Icon>
procedure power_set (s)
result := set ()
if *s = 0
Line 899 ⟶ 1,057:
}
return result
end
</lang>
To test the above procedure:
<lang Icon>
procedure main ()
every s := !power_set (set(1,2,3,4)) do { # requires '!' to generate items in the result set
writes ("[ ")
Line 905 ⟶ 1,069:
write ("]")
}
end
</lang>
Output:
Line 926 ⟶ 1,091:
[ 2 1 ]
</pre>
===Generator===
An alternative version, which generates each item in the power set in turn:
<lang Icon>
procedure power_set (s)
if *s = 0
then suspend set ()
Line 945 ⟶ 1,115:
write ("]")
}
end
</lang>
=={{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:
<lang j>ps =: #~ 2 #:@i.@^ #</lang>
For example:
Line 958 ⟶ 1,131:
AE
AC
ACE</lang>
In the typical use, this operation makes sense on collections of unique elements.
<lang J> ~.1 2 3 2 1
1 2 3
#ps 1 2 3 2 1
32
#ps ~.1 2 3 2 1
8</lang>
In other words, the power set of a 5 element set has 32 sets where the power set of a 3 element set has 8 sets. Thus if elements of the original "set" were not unique then sets of the power "set" will also not be unique sets.
=={{header|Java}}==
===Recursion===
[[Category:Recursion]]
This implementation sorts each subset, but not the whole list of subsets (which would require a custom comparator). It also destroys the original set.
<lang java5>public static ArrayList<String> getpowerset(int a[],int n,ArrayList<String> ps)
{
if(n<0)
Line 993 ⟶ 1,174:
return ps;
}</lang>
===Iterative===
The iterative implementation of the above idea. Each subset is in the order that the element appears in the input list. This implementation preserves the input.
<lang java5>
public static <T> List<List<T>> powerset(Collection<T> list) {
List<List<T>> ps = new ArrayList<List<T>>();
ps.add(new ArrayList<T>()); // add the empty set
Line 1,016 ⟶ 1,200:
}
return ps;
}
</lang>
===Binary String===
This implementation works on idea that each element in the original set can either be in the power set or not in it. With <tt>n</tt> elements in the original set, each combination can be represented by a binary string of length <tt>n</tt>. To get all possible combinations, all you need is a counter from 0 to 2<sup>n</sup> - 1. If the k<sup>th</sup> bit in the binary string is 1, the k<sup>th</sup> element of the original set is in this combination.
<lang java5>public static <T extends Comparable<? super T>> LinkedList<LinkedList<T>> BinPowSet(
LinkedList<T> A){
LinkedList<LinkedList<T>> ans= new LinkedList<LinkedList<T>>();
Line 1,034 ⟶ 1,221:
return ans;
}</lang>
=={{header|JavaScript}}==
{{works with|SpiderMonkey}}
<lang javascript>function powerset(ary) {
var ps = [[]];
for (var i=0; i < ary.length; i++) {
Line 1,048 ⟶ 1,239:
load('json2.js');
print(JSON.stringify(res));</lang>
Outputs:
<pre>[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]]</pre>
=={{header|Julia}}==
result = {{}}
for i in x, j = 1:length(result)
Line 1,057 ⟶ 1,251:
end
result
end</lang>
{{Out}}
<pre>julia> show(powerset({1,2,3}))
{{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}}</pre>
=={{header|K}}==
<lang K>
ps:{x@&:'+2_vs!_2^#x}
</lang
Usage:
<lang K>
ps "ABC"
(""
Line 1,072 ⟶ 1,270:
"AC"
"AB"
"ABC")
</lang>
=={{header|Logo}}==
if empty? :set [output [[]]]
localmake "rest powerset butfirst :set
Line 1,084 ⟶ 1,284:
=={{header|Logtalk}}==
:- public(powerset/2).
Line 1,114 ⟶ 1,314:
PowerSet = [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]]
yes</lang>
=={{header|Lua}}==
<lang lua>
--returns the powerset of s, out of order.
function powerset(s, start)
Line 1,150 ⟶ 1,351:
end
</lang>
=={{header|M4}}==
`ifelse($#, 0, ``$0'',
eval($2 <= $3), 1,
Line 1,173 ⟶ 1,375:
dnl
powerset(`{a,b,c}')</lang>
Output:
<pre>
{{},{a},{a,b},{a,b,c},{a,c},{b},{b,c},{c}}
</pre>
=={{header|Maple}}==
<lang Maple>
with(combinat):
powerset({1,2,3,4});
</lang>
Output:
<pre>
{{}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4},
{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}
</pre>
=={{header|Mathematica}}==
<lang Mathematica>Subsets[{a, b, c}]</lang>
gives:
<lang Mathematica>{{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}</lang>
Subsets[list, {n, Infinity}] gives all the subsets that have n elements or more.
Subsets[list, n] gives all the subsets that have at most n elements.
Subsets[list, {n}] gives all the subsets that have exactly n elements.
Subsets[list, {m,n}] gives all the subsets that have between m and n elements.
=={{header|MATLAB}}==
Sets are not an explicit data type in MATLAB, but cell arrays can be used for the same purpose. In fact, cell arrays have the benefit of containing any kind of data structure. So, this powerset function will work on a set of any type of data structure, without the need to overload any operators.
<lang MATLAB>function pset = powerset(theSet)
pset = cell(size(theSet)); %Preallocate memory
Line 1,206 ⟶ 1,432:
Sample Usage:
Powerset of the set of the empty set.
<lang MATLAB>powerset({{}})
ans =
Line 1,218 ⟶ 1,445:
{1x0 cell} {1x1 cell} {1x1 cell} {1x2 cell} %This is the same as { {},{{1,2}},{3},{{1,2},3} }</lang>
=={{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}} */</lang>
=={{header|Nimrod}}==
proc hash(x): THash =
Line 1,242 ⟶ 1,471:
echo powerset(toSet([1,2,3,4]))</lang>
=={{header|Objective-C}}==
+ (NSArray *)powerSetForArray:(NSArray *)array {
Line 1,259 ⟶ 1,489:
return subsets;
}</lang>
=={{header|OCaml}}==
The standard library already implements a proper ''Set'' datatype. As the base type is unspecified, the powerset must be parameterized as a module. Also, the library is lacking a ''map'' operation, which we have to implement first.
<lang ocaml>module PowerSet(S: Set.S) =
struct
Line 1,276 ⟶ 1,510:
;;
end;; (* PowerSet *)</lang>
version for lists:
<lang ocaml>let subsets xs = List.fold_right (fun x rest -> rest @ List.map (fun ys -> x::ys) rest) xs [[]]</lang>
=={{header|OPL}}==
<lang OPL>
{string} s={"A","B","C","D"};
range r=1.. ftoi(pow(2,card(s)));
{string} s2 [k in r] = {i | i in s: ((k div (ftoi(pow(2,(ord(s,i))))) mod 2) == 1)};
Line 1,285 ⟶ 1,526:
{
writeln(s2);
}
</lang>
which gives
<lang result>
[{} {"A"} {"B"} {"A" "B"} {"C"} {"A" "C"} {"B" "C"} {"A" "B" "C"} {"D"} {"A"
"D"} {"B" "D"} {"A" "B" "D"} {"C" "D"} {"A" "C" "D"} {"B" "C" "D"}
{"A" "B" "C" "D"}]
</lang>
=={{header|Oz}}==
<lang oz>declare
%% Given a set as a list, returns its powerset (again as a list)
fun {Powerset Set}
Line 1,305 ⟶ 1,560:
end
in
{Inspect {Powerset [1 2 3 4]}}</lang>
A more convential implementation without finite set constaints:
<lang oz>fun {Powerset2 Set}
case Set of nil then [nil]
Line 1,316 ⟶ 1,573:
=={{header|PARI/GP}}==
=={{header|Perl}}==
Perl does not have a built-in set data-type. However, you can...
<ul>
<li><p>'''''Use a third-party module'''''</p>
Line 1,341 ⟶ 1,599:
Output:
<pre>Set::Object(Set::Object() Set::Object(1 2 3) Set::Object(1 2) Set::Object(1 3) Set::Object(1) Set::Object(2 3) Set::Object(2) Set::Object(3))</pre
</li>
<li><p>'''''Use a simple custom hash-based set type'''''</p>
It's also easy to define a custom type for sets of strings or numbers, using a hash as the underlying representation (like the task description suggests):
<lang perl>package Set {
sub new { bless { map {$_ => undef} @_[1..$#_] }, shift; }
sub elements { sort keys %{shift()} }
sub as_string { 'Set(' . join(' ', sort keys %{shift()}) . ')' }
# ...more set methods could be defined here...
}</lang>
''(Note: For a ready-to-use module that uses this approach, and comes with all the standard set methods that you would expect, see the CPAN module [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:
<lang perl>use List::Util qw(reduce);
sub powerset {
Line 1,362 ⟶ 1,629:
my @subsets = powerset($set);
print $_->as_string, "\n" for @subsets;</lang>
Output:
<pre>
Set()
Set(1)
Set(2)
Line 1,369 ⟶ 1,640:
Set(1 3)
Set(2 3)
Set(1 2 3)
</pre>
</li>
<li><p>'''''Use arrays'''''</p>
If you don't actually need a proper set data-type that guarantees uniqueness of its elements, the simplest approach is to use arrays to store "sets" of items, in which case the implementation of the powerset function becomes quite short.
Recursive solution:
<lang perl>sub powerset {
@_ ? map { $_, [$_[0], @$_] } powerset(@_[1..$#_]) : [];
}</lang>
List folding solution:
<lang perl>use List::Util qw(reduce);
sub powerset {
@{( reduce { [@$a, map([@$_, $b], @$a)] } [[]], @_ )}
}</lang>
Usage & output:
<lang perl>my @set = (1, 2, 3);
my @powerset = powerset(@set);
Line 1,385 ⟶ 1,671:
print set_to_string(@powerset), "\n";</lang>
<pre>
{{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}
</pre>
</li>
</ul>
=={{header|Perl 6}}==
{{works with|rakudo|2014-02-25}}
<lang perl6>sub powerset(Set $s) { $s.combinations.map(*.Set).Set }
say powerset set <a b c d>;</lang>
{{out}}
<pre>set(set(), set(a), set(b), set(c), set(d), set(a, b), set(a, c), set(a, d), set(b, c), set(b, d), set(c, d), set(a, b, c), set(a, b, d), set(a, c, d), set(b, c, d), set(a, b, c, d))</pre>
If you don't care about the actual <tt>Set</tt> type, the <tt>.combinations</tt> method by itself may be good enough for you:
<lang perl6>.say for <a b c d>.combinations</lang>
{{out}}
<pre>
a
b
Line 1,407 ⟶ 1,704:
b c d
a b c d</pre>
=={{header|PHP}}==
<lang PHP>
function get_subset($binary, $arr) {
// based on true/false values in $binary array, include/exclude
Line 1,467 ⟶ 1,765:
print_power_sets(array('singleton'));
print_power_sets(array('dog', 'c', 'b', 'a'));
?>
</lang>
Output in browser:
<lang>
POWER SET of []
POWER SET of [singleton]
(empty)
Line 1,487 ⟶ 1,789:
a c dog
b c dog
a b c dog
</lang>
=={{header|PicoLisp}}==
(ifn Lst
(cons)
Line 1,496 ⟶ 1,800:
(mapcar '((X) (cons (car Lst) X)) L)
L ) ) ) )</lang>
=={{header|PL/I}}==
/*--------------------------------------------------------------------
* 06.01.2014 Walter Pachl translated from REXX
Line 1,563 ⟶ 1,868:
End;</lang>
'''output'''
<pre>{}
{one}
{two}
Line 1,579 ⟶ 1,885:
{two,three,four}
{one,two,three,four}</pre>
=={{header|Prolog}}==
===Logical (cut-free) Definition===
The predicate powerset(X,Y) defined here can be read as "Y is the
powerset of X", it being understood that lists are used to represent sets.
The predicate subseq(X,Y) is true if and only if the list X is a subsequence of the list Y.
The definitions here are elementary, logical (cut-free), and efficient (within the class of comparably generic implementations).
<lang Prolog>powerset(X,Y) :- bagof( S, subseq(S,X), Y).
Line 1,590 ⟶ 1,900:
subseq( [], [_|_]).
subseq( [X|Xs], [X|Ys] ) :- subseq(Xs, Ys).
subseq( [X|Xs], [_|Ys] ) :- append(_, [X|Zs], Ys), subseq(Xs, Zs
</lang>
Output :
<pre>?- powerset([1,2,3], X).
X = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]].
Line 1,601 ⟶ 1,914:
X = 1,
Y = 2.</pre>
===Single-Functor Definition===
<lang Prolog>power_set( [], [[]]).
Line 1,607 ⟶ 1,921:
maplist( append([X]), PS1, PS2 ), % i.e. prepend X to each PS1
append(PS1, PS2, PS).</lang>
Output :
<pre>?- power_set([1,2,3,4,5,6,7,8], X), length(X,N), writeln(N).
256
</pre>
===Constraint Handling Rules===
Works with SWI-Prolog and module chr written by '''Tom Schrijvers''' and '''Jan Wielemaker'''.
<lang Prolog>:- use_module(library(chr)).
:- chr_constraint chr_power_set/2, chr_power_set/1, clean/0.
Line 1,619 ⟶ 1,937:
only_one @ chr_power_set(A) \ chr_power_set(A) <=> true.
creation @ chr_power_set([H | T], A) <=>
Line 1,626 ⟶ 1,945:
chr_power_set(B).
empty_element @ chr_power_set([], _) <=> chr_power_set([]).
</lang>
Example of output :
<pre> ?- chr_power_set([1,2,3,4], []), findall(L, find_chr_constraint(chr_power_set(L)), LL), clean.
LL = [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,4],[1,3],[1,3,4],[1,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4],[]] .
</pre>
=={{header|PureBasic}}==
<lang PureBasic>If OpenConsole()
Define argc=CountProgramParameters()
If argc>=(SizeOf(Integer)*8) Or argc<1
Line 1,653 ⟶ 1,979:
PrintN("}")
EndIf
EndIf</lang>
<!-- Output modified with a line break to avoid being too long -->
Sample output
<pre>C:\Users\PureBasic_User\Desktop>"Power Set.exe" 1 2 3 4
{{}, {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|Python}}==
<lang python>def list_powerset(lst):
# the power set of the empty set has one element, the empty set
Line 1,678 ⟶ 2,006:
def powerset(s):
return frozenset(map(frozenset, list_powerset(list(s))))</lang>
<tt>list_powerset</tt> computes the power set of a list of distinct elements. <tt>powerset</tt> simply converts the input and output from lists to sets. We use the <tt>frozenset</tt> type here for immutable sets, because unlike mutable sets, it can be put into other sets.
Example:
<pre>
>>> list_powerset([1,2,3])
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Line 1,686 ⟶ 2,018:
</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
<lang python>def powersetlist(s):
r = [[]]
for e in s:
Line 1,694 ⟶ 2,027:
s= [0,1,2,3]
print "\npowersetlist(%r) =\n %r" % (s, powersetlist(s))</lang>
Sample output:
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]]
</pre>
=== Binary Count method ===
If you list the members of the set and include them according to if the corresponding bit position of a binary count is true then you generate the powerset.
(Note that only frozensets can be members of a set in the second function)
<lang python>def powersequence(val):
''' Generate a 'powerset' for sequence types that are indexable by integers.
Uses a binary count to enumerate the members and returns a list
Line 1,730 ⟶ 2,067:
'''
return set( frozenset(x) for x in powersequence(list(s)) )</lang>
=== Recursive Alternative ===
This is an (inefficient) recursive version that almost reflects the recursive definition of a power set as explained in http://en.wikipedia.org/wiki/Power_set#Algorithms. It does not create a sorted output.
<lang python>
def p(l):
if not l: return [[]]
return p(l[1:]) + [[l[0]] + x for x in p(l[1:])]
</lang>
===Python: Standard documentation===
Pythons [http://docs.python.org/3/library/itertools.html?highlight=powerset#itertools-recipes documentation] has a method that produces the groupings, but not as sets:
<lang python>>>> from pprint import pprint as pp
>>> from itertools import chain, combinations
>>>
Line 1,761 ⟶ 2,106:
(4,)}
>>> </lang>
=={{header|Qi}}==
{{trans|Scheme}}
<lang qi>
(define powerset
[] -> [[]]
[A|As] -> (append (map (cons A) (powerset As))
(powerset As)))
</lang>
=={{header|R}}==
===Non-recursive version===
The conceptual basis for this algorithm is the following
<lang>for each element in the set:
for each subset constructed so far:
new subset = (subset + element)
</lang>
This method is much faster than a recursive method, though the speed is still O(2^n).
<lang R>powerset = function(set){
ps = list()
ps[[1]] = numeric() #Start with the empty set.
Line 1,784 ⟶ 2,139:
}
powerset(1:4)
</lang>
The list "temp" is a compromise between the speed costs of doing arithmetic and of creating new lists (since R lists are immutable, appending to a list means actually creating a new list object). Thus, "temp" collects new subsets that are later added to the power set. This improves the speed by 4x compared to extending the list "ps" at every step.
===Recursive version===
{{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.
<lang R>library(sets)</lang>
An example with a vector.
<lang R>v <- (1:3)^2
sv <- as.set(v)
2^sv</lang>
{{}, {1}, {4}, {9}, {1, 4}, {1, 9}, {4, 9}, {1, 4, 9}}
An example with a list.
<lang R>l <- list(a=1, b="qwerty", c=list(d=TRUE, e=1:3))
sl <- as.set(l)
2^sl</lang>
{{}, {1}, {"qwerty"}, {<<list(2)>>}, {1, <<list(2)>>}, {"qwerty",
1}, {"qwerty", <<list(2)>>}, {"qwerty", 1, <<list(2)>>}}
=={{header|Racket}}==
<lang racket>
;;; Direct translation of 'functional' ruby method
(define (powerset s)
(for/fold ([outer-set (set(set))]) ([element s])
(set-union outer-set
(list->set (set-map outer-set
(λ(inner-set) (set-add inner-set element)))))))
</lang>
=={{header|Rascal}}==
<lang rascal>
public set[set[&T]] PowerSet(set[&T] s) = power(s);
</lang>
An example output:
<lang rascal>
rascal>PowerSet({1,2,3,4})
set[set[int]]: {
{4,3},
{4,2,1},
Line 1,827 ⟶ 2,198:
{3,2,1},
{}
</lang>
=={{header|REXX}}==
parse arg S /*let user specify the set. */
if S='' then S='one two three four' /*None specified? Use default*/
Line 1,858 ⟶ 2,231:
end /*u*/
return 0</lang>
<pre style="overflow:scroll">
1 {}
2 {one}
3 {two}
Line 1,874 ⟶ 2,248:
14 {one,three,four}
15 {two,three,four}
16 {one,two,three,four}
</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
Line 1,918 ⟶ 2,294:
p %w(one two three).func_power_set
p Set[1,2,3].powerset</lang
{{out}}
<pre>
[[], [4], [3], [3, 4], [2], [2, 4], [2, 3], [2, 3, 4], [1], [1, 4], [1, 3], [1, 3, 4], [1, 2], [1, 2, 4], [1, 2, 3], [1, 2, 3, 4]]
[[], ["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|SAS}}==
<lang SAS>
options mprint mlogic symbolgen source source2;
%macro SubSets (FieldCount = );
Line 1,976 ⟶ 2,356:
%end;
%Mend SubSets;
</lang>
You can then call the macro as:
<lang SAS>
%SubSets(FieldCount = 5);
</lang>
The output will be the dataset SUBSETS and will have a 5 columns F1, F2, F3, F4, F5 and 32 columns, one with each combination of 1 and missing values.
Output:
<pre>
Obs F1 F2 F3 F4 F5 RowCount
1 . . . . . 1
Line 2,010 ⟶ 2,400:
30 1 1 1 . 1 30
31 1 1 1 1 . 31
32 1 1 1 1 1 32
</pre>
=={{header|Scala}}==
[[Category:Scala Implementations]]<lang scala>import scala.compat.Platform.currentTime
object Powerset extends App {
Line 2,024 ⟶ 2,411:
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]")
}</lang>Another option that produces
<lang scala>def powerset[A](s: Set[A]) = (0 to s.size).map(s.toSeq.combinations(_)).reduce(_ ++ _).map(_.toSet)</lang>
=={{header|Scheme}}==
<lang scheme>(define (power-set set)
(if (null? set)
Line 2,043 ⟶ 2,429:
(display (power-set (list "A" "C" "E")))
(newline)</lang>
Output:
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())
((A C E) (A C) (A E) (A) (C E) (C) (E) ())
Call/cc generation:<lang lisp>(define (power-set lst)
(define (iter yield)
Line 2,074 ⟶ 2,462:
(2)
(3)
()</lang>
Iterative:<lang scheme>
(define (power_set_iter set)
(let loop ((res '(())) (s set))
(if (empty? s)
res
(loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s)))))
</lang>
Output:<lang output>
'((e d c b a)
(e d c b)
(e d c a)
Line 2,111 ⟶ 2,505:
(a)
())
</lang>
=={{header|Seed7}}==
const func array bitset: powerSet (in bitset: baseSet) is func
Line 2,140 ⟶ 2,536:
writeln(aSet);
end for;
end func;</lang>
Output:
<pre>
{}
{1}
{2}
Line 2,155 ⟶ 2,555:
{1, 3, 4}
{2, 3, 4}
{1, 2, 3, 4}
</pre>
=={{header|Smalltalk}}==
{{works with|GNU Smalltalk}}
Code from [http://smalltalk.gnu.org/blog/bonzinip/fun-generators Bonzini's blog]
<lang smalltalk>Collection extend [
power [
^(0 to: (1 bitShift: self size) - 1) readStream collect: [ :each || i |
Line 2,165 ⟶ 2,568:
self select: [ :elem | (each bitAt: (i := i + 1)) = 1 ] ]
]
].</lang>
<lang smalltalk>#(1 2 4) power do: [ :each |
each asArray printNl ].
#( 'A' 'C' 'E' ) power do: [ :each |
each asArray printNl ].</lang>
=={{header|Standard ML}}==
version for lists:
<lang sml>fun subsets xs = foldr (fn (x, rest) => rest @ map (fn ys => x::ys) rest) [[]] xs</lang>
=={{header|Tcl}}==
set res [list [list]]
foreach e $l {
Line 2,180 ⟶ 2,589:
return $res
}
puts [subsets {a b c d}]</lang>
Output:
<pre>{} a b {a b} c {a c} {b c} {a b c} d {a d} {b d} {a b d} {c d} {a c d} {b c d} {a b c d}</pre>
===Binary Count Method===
<lang tcl>proc powersetb set {
Line 2,195 ⟶ 2,605:
return $res
}</lang>
=={{header|TXR}}==
{{trans|Common Lisp}}
The power set function can be written concisely like this:
<lang txr>(defun power-set (s)
(reduce-right
(op append (mapcar (op cons @@1) @2) @2)
s '(())))</lang>
A complete program which takes command line arguments and prints the power set in comma-separated brace notation:
<lang txr>@(do (defun power-set (s)
(reduce-right
(op append (mapcar (op cons @@1) @2) @2)
Line 2,209 ⟶ 2,628:
{@(rep)@pset, @(last)@pset@(empty)@(end)}
@ (end)
@(end)</lang>
<pre>$ txr rosetta/power-set.txr 1 2 3
{1, 2, 3}
{1, 2}
Line 2,217 ⟶ 2,638:
{2}
{3}
{}</pre>
What is not obvious is that the above <code>power-set</code> function generalizes to strings and vectors.
<lang txr>@(do (defun power-set (s)
(reduce-right
(op append (mapcar (op cons @@1) @2) @2)
Line 2,223 ⟶ 2,648:
(prinl (power-set "abc"))
(prinl (power-set ""))
(prinl (power-set #(1 2 3))))</lang>
<pre>txr power-set-generic.txr
((nil) nil)
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) nil)</pre>
=={{header|UnixPipes}}==
<lang ksh>
| cat A
a
b
Line 2,249 ⟶ 2,678:
b
b c
c
</lang>
=={{header|UNIX Shell}}==
From [http://www.catonmat.net/blog/set-operations-in-unix-shell/ here]
<lang bash>p() { [ $# -eq 0 ] && echo || (shift; p "$@") | while read r ; do echo -e "$1 $r\n$r"; done }</lang>
Line 2,263 ⟶ 2,692:
=={{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.
<lang Ursala>powerset = ~&NiC+ ~&i&& ~&at^?\~&aNC ~&ahPfatPRXlNrCDrT</lang>
test program:
Line 2,270 ⟶ 2,702:
test = powerset {'a','b','c','d'}</lang>
output:
<pre>{
{},
{'a'},
Line 2,287 ⟶ 2,719:
{'c'},
{'c','d'},
{'d'}}</pre>
=={{header|V}}==
V has a built in called powerlist
<lang v>[A C E] powerlist
=[[A C E] [A C] [A E] [A] [C E] [C] [E] []]</lang>
its implementation in std.v is (like joy)
<lang v>[powerlist
[null?]
Line 2,299 ⟶ 2,732:
[uncons]
[dup swapd [cons] map popd swoncat]
linrec].
</lang>
=={{header|zkl}}==
Using a combinations function, build the power set from combinations of 1,2,... items.
Line 2,310 ⟶ 2,745:
foreach n in (5){
ps:=pwerSet((1).pump(n,List)); ps.println(" Size = ",ps.len());
}
</pre>
<pre>
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>
{{omit from|GUISS}}
|