Power set: Difference between revisions

procedure Power_Setpowerset is

for Iset in Set'Range0..2**Argument_Count-1 loop -- initialize set

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

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

MsgBox % RegExReplace(SubStr(t,1,StrLen(t)-1),",}","}")</langsyntaxhighlight>

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

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

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

[ 3 2 1 ]</pre>

<langsyntaxhighlight Clojurelang="clojure">(use '[clojure.math.combinatorics :only [subsets] ])

(() (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))</langsyntaxhighlight>

<langsyntaxhighlight Clojurelang="clojure">(defn powerset [coll]

(->>into a (map #(conj % x)) a))

(powerset #{1 2 3})</langsyntaxhighlight>

<syntaxhighlight lang="clojure">#{#{} #{1} #{2} #{1 2} #{3} #{1 3} #{2 3} #{1 2 3}}</syntaxhighlight>

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]);</langsyntaxhighlight>{{out}}

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

<langsyntaxhighlight lang="lisp">(defun powerset (l)

prev))))</langsyntaxhighlight>

<langsyntaxhighlight lang="lisp">(defun powerset (xs)

(loop for j below i for x in xs if (logbitp j i) collect x)))</langsyntaxhighlight>

<langsyntaxhighlight lang="lisp">(defun power-set (list)

(push (cons element set) pow-set)))))</langsyntaxhighlight>

{{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.</langsyntaxhighlight>or even more efficient version:<lang erlang>powerset([]) -> [[]];

powerset(X, [H|T], Acc) -> powerset(X, T, [[X|H]|Acc]).</langsyntaxhighlight>

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

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

| 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> ;</langsyntaxhighlight>{{out|Usage}}<pre>( scratchpad ) HS{ 1 2 3 4 } powerset .

}</presyntaxhighlight>

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

acc + map( x -> {s.head()} + x, acc )</langsyntaxhighlight>

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

# [ 2 ], [ 2, 3 ], [ 3 ] ]</langsyntaxhighlight>

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

TheWhile the "add" and "has" methods make a usable set type, the power set method implemented here doescomputes nota needresult directly without using 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.

Eq(elementelem) bool

j, ok := e.(Int)

varif buflen(s) bytes.Buffer== 0 {

for _i, e := range s {

if len(r)i > 10 {

buf.WriteRune(' ,')

uer := append(u, append(er.(set), es))

fmt.Println(" s:", s, "length:", len(s))

fmt.Println(" 𝑷(s):", ps, "length:", len(ps))

def nps = listempty.sizepowerSet()

ps = [[]] :ps.powerSet()

def powerSet =(set) { powerSetRec([], set ->as List) as Set}

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

<langsyntaxhighlight Haskelllang="haskell">powerset [] = [[]]

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

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

powerSet = (Set.fold (slift Set.union) (Set.singleton Set.empty)) . Set.map makeSet</langsyntaxhighlight>

{{out|Usage}}:

end</lang>

end</lang>

<langsyntaxhighlight lang="j"> ps 'ACE'

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

}</langsyntaxhighlight>

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(

}</langsyntaxhighlight>

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

for i in x, jresult = 1:length(result)Vector{T}[[]]

result end

"ABC")</pre>

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

[[1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []]</langsyntaxhighlight>

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

:- end_object.</langsyntaxhighlight>

<langsyntaxhighlight lang="logtalk">| ?- set::powerset([1, 2, 3, 4], PowerSet).

yes</langsyntaxhighlight>

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

powerset(`{a,b,c}')</langsyntaxhighlight>

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

end</langsyntaxhighlight>

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

{} {1x1 cell} %This is the same as { {},{{}} }</langsyntaxhighlight>

<langsyntaxhighlight MATLABlang="matlab">powerset({{1,2},3})

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

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

{1, 4}, {2}, {2, 3}, {2, 3, 4}, {2, 4}, {3}, {3, 4}, {4}} */</langsyntaxhighlight>

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

}</langsyntaxhighlight>

{"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]}}</langsyntaxhighlight>A more convential implementation without finite set constaints:

end</langsyntaxhighlight>

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

<langsyntaxhighlight lang="perl">use Set::Object qw(set);

print $powerset->as_string, "\n";</langsyntaxhighlight>

<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;</langsyntaxhighlight>{{out}}<pre>Set()

print set_to_string(@powerset), "\n";</langsyntaxhighlight>

a b d {

<lang PHP><?php

a b c dog</pre>

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

L ) ) ) )</langsyntaxhighlight>

End;</langsyntaxhighlight>

{{out}}<pre>{}

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

<langsyntaxhighlight Prologlang="prolog">power_set( [], [[]]).

append(PS1, PS2, PS).</langsyntaxhighlight>

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

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))</langsyntaxhighlight>{{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):

return set( frozenset(x) for x in powersequence(list(s)) )</langsyntaxhighlight>

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

>>> </langsyntaxhighlight>

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

temp =<- vector(mode="list",length=length(ps)) #currently in "ps" and create new subsets (in "temp")

ps= <- c(ps,temp) #Add the additional subsets ("temp") to "ps".

return(ps)

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>

2^sv</langsyntaxhighlight>

An example with a list.<lang R>l <- list(a=1, b="qwerty", c=list(d=TRUE, e=1:3))

2^sl</langsyntaxhighlight>

(λ(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<syntaxhighlight shows no proof of the cases with empty sets.}}<lang ="rexx">/*REXX program to displaydisplays a power set,; items may be anything (nobut can't have blanks).*/

parseParse Arg text arg S /*letallow the user specify theoptional set. */

ifIf Stext='' Then then S='one two three four' /*NoneNot specified? UseThen use the default.*/

Do k=0 To n ps=ps combN(N,chunk) /* loops from 0 to /*Nn elements items,of a CHUNKset at a time. */

cc=comb(n,k) end/* returns the combinations of 1 through k /*chunk*/

Parse Var cc elist '/' cc /* get doi k=1from comb's forresult wstring /*show combinations, one/line.*/

psi=psi+1 end /*k index of this set */

exit Do While elist<>'' /* loop through elements /*stick a fork in it, we done.*/

psl=substr(psl,2) /* doget j=1;rid L=of leading comma */

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

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

# See the link if you want a shorter version. This was intended to show the reader how the method works.

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

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

32 1 1 1 1 1 32</pre>

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

<langsyntaxhighlight lang="scheme">(define (power-set set)

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

(loop (x)))))</langsyntaxhighlight>output<lang>(1 2)

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

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

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

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

each asArray printNl ].</langsyntaxhighlight>

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

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

<langsyntaxhighlight lang="tcl">proc powersetb set {

}</langsyntaxhighlight>

{{trans|Common Lisp}}The power set function can be written concisely like this:<lang txr>(defun power-set (s)

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

=={{header|UNIX ShellUrsala}}==

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.

<langsyntaxhighlight Ursalalang="ursala">#cast %sSS

test = powerset {'a','b','c','d'}</langsyntaxhighlight>

{'d'}}</pre>

<langsyntaxhighlight lang="v">[A C E] powerlist

=[[A C E] [A C] [A E] [A] [C E] [C] [E] []]</langsyntaxhighlight>

linrec].</lang>

<langsyntaxhighlight lang="zkl">fcn pwerSet(list){

}</langsyntaxhighlight>

ps:=pwerSetL(L(1).pump,L(n,List1)); ps.println(" Size = ",ps.len());2

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