Power set: Difference between revisions

Given a set S, the [[wp:Power_set|power set]] (or powerset) of S, written P(S), or 2^S, is the set of all subsets of S.<p>'''Taskbr : ''' 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^S of S.</p><p>For example, the power set of {1,2,3,4} is {{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}.</p>

<p>AndFor the power set of thea set which contains onlyn elements, the emptycorresponding power set, has two2ⁿ subsetselements, the empty set andincluding the setedge whichcases contains theof [[wp:Empty_set|empty set (2]].¹br = 2):</p>

end Power_Set;</lang>{{out}}<pre>>./power_set cat dog mouse

Requires: ALGOL 68g mk14.1+<lang algol68>MODE MEMBER = INT;

)</lang>{{out}}<pre>set[1] = ();

set[8] = (1, 2, 4);</pre>

{{incomplete|AutoHotkey|It shows no proof of the cases with empty sets.}}ahk [http://www.autohotkey.com/forum/viewtopic.php?t=44657&postdays=0&postorder=asc&start=147 discussion]<lang autohotkey>a = 1,a,-- ; elements separated by commas

{{incomplete|BBC BASIC|It shows no proof of the cases with empty sets.}}The elements of a set are represented as the bits in an integer (hence the maximum size of set is 32).<lang bbcbasic> DIM list$(3) : list$() = "1", "2", "3", "4"

= LEFT$(s$) + "}"</lang>{{out}}

{{incomplete|Bracmat|It shows no proof of the cases with empty sets.}}<lang bracmat>( ( powerset

);</lang>{{out}}<pre> 1 2 3 4

{{incomplete|C|It shows no proof of the cases with empty sets.}}<lang c>#include <stdio.h>

}</lang>{{out}}<pre>% ./a.out 1 2 3

[ 3 2 1 ]</pre>

}</lang>{{out}}<pre>

}</lang>

<lang Clojure>#{#{} #{1} #{2} #{1 2} #{3} #{1 3} #{2 3} #{1 2 3}}</lang>

print_power_set ['dog', 'c', 'b', 'a']</lang>{{out}}<pre>> coffee power_set.coffee

[ 'dog', 'c', 'b', 'a' ]</pre>

var res = powerset([1,2,3,4]);</lang>{{out}}

{{incomplete|Common Lisp|It shows no proof of the cases with empty sets.}}<lang lisp>(defun power-set (s)

:initial-value '(())))</lang>{{out}}

{{incomplete|D|It shows no proof of the cases with empty sets.}}Version using just arrays (it assumes the input to contain distinct items):<lang d>T[][] powerSet(T)(in T[] s) pure nothrow @safe {

}</lang>{{out}}

}</lang>Same output.

{{out|Generates all subsets of a list with the help of binary}}:

<pre>For [1 2 3]:

¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯</pre><lang erlang>powerset(Lst) ->

[ [H|X] || X <- PT ] ++ PT.</lang>or even more efficient version:<lang erlang>powerset([]) -> [[]];

{{incomplete|F Sharp|It shows no proof of the cases with empty sets.}}almost exact copy of OCaml version

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 =

| x::xs -> [for i in pow xs do yield! [i;x::i]]</lang>

{{incomplete|Factor|It shows no proof of the cases with empty sets.}}We use hash sets, denoted by <code>HS{ }</code> brackets, for our sets. <code>members</code> converts from a set to a sequence, and <code><hash-set></code> converts back.<lang factor>USING: kernel prettyprint sequences arrays sets hash-sets ;

: powerset ( set -- newset ) members { HS{ } } [ dupd [ add ] curry map append ] reduce <hash-set> ;</lang>{{out|Usage}}<pre>( scratchpad ) HS{ 1 2 3 4 } powerset .

}</prelang>

powerset</lang>{{out}}<pre>$ 4th cxq powerset.4th 1 2 3 4

( 1 2 3 4 )</pre>

{{incomplete|Frink|It shows no proof of the cases with empty sets.}}Frink's set and array classes have built-in subsets[] methods that return all subsets. If called with an array, the results are arrays. If called with a set, the results are sets.<lang frink>

a.subsets[]</lang>

{{incomplete|FunL|It shows no proof of the cases with empty sets.}}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>

println( powerset({1, 2, 3, 4}) )</lang>{{out}}

{{incomplete|GAP|It shows no proof of the cases with empty sets.}}<lang gap># Built-in

{{incomplete|Go|It shows no proof of the cases with empty sets.}}No native set type in Go. While the associative array trick mentioned in the task description works well in Go in most situations, it does not work here because we need sets of sets, and converting a general set to a hashable value for a map key is non-trivial.

Instead, this solution uses a simple (non-associative) slice as a set representation. To ensure uniqueness, the element interface requires an equality method, which is used by the set add method. Adding elements with the add method ensures the uniqueness property.

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>{{out}}<pre>{1 2 3 4}

length = 16</pre>

{{incomplete|Groovy|It shows no proof of the cases with empty sets.}}Builds on the [[Combinations#Groovy|Combinations]] solution. '''Sets''' are not a "natural" collection type in Groovy. '''Lists''' are much more richly supported. Thus, this solution is liberally sprinkled with coercion from '''Set''' to '''List''' and from '''List''' to '''Set'''.<lang groovy>def comb

{{incomplete|Haskell|It shows no proof of the cases with empty sets.}}<lang Haskell>import Data.Set

powerset (head:tail) = acc ++ map (head:) acc where acc = powerset tail</lang> or <lang Haskell>powerset = foldr (\x acc -> acc ++ map (x:) acc) [[]]</lang>

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

{{out|Usage}}:

end</lang>

end</lang>

{{incomplete|Java|It shows no proof of the cases with empty sets.}}{{works with|Java|1.5+}}

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)

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

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ⁿ - 1. If the k^th bit in the binary string is 1, the k^th element of the original set is in this combination.<lang java5>public static <T extends Comparable<? super T>> LinkedList<LinkedList<T>> BinPowSet(

{{incomplete|JavaScript|It shows no proof of the cases with empty sets.}}Uses a JSON stringifier from http://www.json.org/js.html{{works with|SpiderMonkey}}<lang javascript>function powerset(ary) {

print(JSON.stringify(res));</lang>{{out}}

{{incomplete|Julia|It shows no proof of the cases with empty sets.}}<lang julia>function powerset (x)

end</lang>{{Out}}

</lang>Usage:<pre>

"ABC")</pre>

{{incomplete|Logo|It shows no proof of the cases with empty sets.}}<lang logo>to powerset :set

{{incomplete|Logtalk|It shows no proof of the cases with empty sets.}}<lang logtalk>:- object(set).

{{incomplete|M4|It shows no proof of the cases with empty sets.}}<lang M4>define(`for',

powerset({1,2,3,4});</lang>{{out}}

{{incomplete|Mathematica|It shows no proof of the cases with empty sets.}}Built-in function that either gives all possible subsets, subsets with at most n elements, subsets with exactly n elements or subsets containing between n and m elements. Example of all subsets:

<lang Mathematica>Subsets[{a, b, c}]</lang>gives:

Powerset of the set of the empty set.<lang MATLAB>powerset({{}})

{{incomplete|Maxima|It shows no proof of the cases with empty sets.}}<lang maxima>powerset({1, 2, 3, 4});

{{incomplete|Nimrod|It shows no proof of the cases with empty sets.}}<lang nimrod>import sets, hashes

{{incomplete|Objective-C|It shows no proof of the cases with empty sets.}}<lang objc>#import <Foundation/Foundation.h>

{"A" "B" "C" "D"}]

{{incomplete|Oz|It shows no proof of the cases with empty sets.}}Oz has a library for finite set constraints. Creating a power set is a trivial application of that:<lang oz>declare

{Inspect {Powerset [1 2 3 4]}}</lang>A more convential implementation without finite set constaints:

{{incomplete|PARI/GP|It shows no proof of the cases with empty sets.}}<lang parigp>vector(1<<#S,i,vecextract(S,i-1))</lang>

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

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

print $_->as_string, "\n" for @subsets;</lang>{{out}}<pre>Set()

<lang perl6>.say for <a b c d>.combinations</lang>{{out}}<pre>&nbsp;

<lang PHP><?php

a b c dog</pre>

{{incomplete|PicoLisp|It shows no proof of the cases with empty sets.}}<lang PicoLisp>(de powerset (Lst)

{{incomplete|PL/I|It shows no proof of the cases with empty sets.}}<lang pli>*process source attributes xref or(!);

subseq( [X|Xs], [_|Ys] ) :- append(_, [X|Zs], Ys), subseq(Xs, Zs).</lang>{{out}}<pre>?- powerset([1,2,3], X).

{{libheader|chr}}CHR is a programming language created by '''Professor Thom Frühwirth'''. Works with SWI-Prolog and module chr written by '''Tom Schrijvers''' and '''Jan Wielemaker'''.<lang Prologbr>:- use_module(library(chr)).

{{incomplete|PureBasic|It shows no proof of the cases with empty sets.}}This code is for console mode.<lang PureBasic>If OpenConsole()

EndIf</lang>{{out|Sample output}}

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

print "\npowersetlist(%r) =\n %r" % (s, powersetlist(s))</lang>{{out|Sample output}}

<pre>r: [[], [0], [1], [0, 1]] e: 20

r: [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]] e: 31

(Note that only frozensets can be members of a set in the second function)<lang python>def powersequence(val):

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

return p(l[1:]) + [[l[0]] + x for x in p(l[1:])]</lang>

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

(powerset As)))</lang>

The conceptual basis for this algorithm is the following:<lang>for each element in the set:

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

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 list.<lang R>l <- list(a=1, b="qwerty", c=list(d=TRUE, e=1:3))

(λ(inner-set) (set-add inner-set element)))))))</lang>

<lang rascal>import Set;

public set[set[&T]] PowerSet(set[&T] s) = power(s);</lang>{{out|An example output}}

}

{{incomplete|REXX|It shows no proof of the cases with empty sets.}}<lang rexx>/*REXX program to display a power set, items may be anything (no blanks)*/

{{out|'''output''' when using the default input}}:

16 {one,two,three,four}</pre>

{{incomplete|Ruby|It shows no proof of the cases with empty sets.}}<lang ruby># Based on http://johncarrino.net/blog/2006/08/11/powerset-in-ruby/

p Set[1,2,3].powerset</lang>{{out}}<pre>

%Mend SubSets;</lang>You can then call the macro as:

32 1 1 1 1 1 32</pre>

[[Category:Scala Implementations]]<lang scala>import scala.compat.Platform.currentTime

{{incomplete|Scheme|It shows no proof of the cases with empty sets.}}{{trans|Common Lisp}}

(newline)</lang>{{out}}

</lang>{{out}} '((e d c b a)

{{incomplete|Seed7|It shows no proof of the cases with empty sets.}}<lang seed7>$ include "seed7_05.s7i";

end func;</lang>{{out}}<pre>{}

{1, 2, 3, 4}</pre>

Code from [http://smalltalk.gnu.org/blog/bonzinip/fun-generators Bonzini's blog]<lang smalltalk>Collection extend [

{{incomplete|Tcl|It shows no proof of the cases with empty sets.}}<lang tcl>proc subsets {l} {

puts [subsets {a b c d}]</lang>{{out}}

@(end)</lang><pre>$ txr rosetta/power-set.txr 1 2 3

(prinl (power-set #(1 2 3))))</lang>txr power-set-generic.txr

((1#\a 2#\b 3#\c) (1#\a 2#\b) (1#\a 3#\c) (1#\a) (2#\b 3#\c) (2#\b) (3#\c) nil)

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.

{'d'}}</pre>

linrec].</lang>

L(L(),L(1),L(2),L(1,2)) Size = 41

L(L(),L(1),L(2),L(3),L(1,2),L(1,3),L(2,3),L(1,2,3)) Size = 82

L(L(),L(1),L(2),L(3),L(4),L(1,2),L(1,3),L(1, Size = 4),L(2,3),L(2,4),