Power set: Difference between revisions

{{task|Discrete math}}

 

 

 

=={{header|Ada}}==

begin

=={{header|ALGOL 68}}==

{{works with|ALGOL 68|Revision 1 - no extensions to language used}}

 

Requires: ALGOL 68g mk14.1+

 

PROC power set = ([]MEMBER s)[][]MEMBER:(

printf(($"set["d"] = "$,member, repr set, set[member],$l$))

OD

<pre>

set[1] = ();

set[8] = (1, 2, 4);

</pre>

 

=={{header|AutoHotkey}}==

ahk [http://www.autohotkey.com/forum/viewtopic.php?t=44657&postdays=0&postorder=asc&start=147 discussion]

StringSplit a, a, `, ; a0 = #elements, a1,a2,... = elements of the set

 

t .= "}`n{" ; new subsets in new lines

}

 

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

PRINT FNpowerset(list$())

END

s$ += "},"

NEXT i%

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

 

=={{header|C}}==

 

{

 

 

}

 

{

 

=={{header|C++}}==

=== Non-recursive version ===

 

#include <set>

#include <vector>

std::cout << " }\n";

}

 

<pre>

{ }

{ 7 }

</pre>

 

=== Recursive version ===

 

#include <set>

 

return powerset(s, s.size());

}

 

 

 

 

 

 

 

 

=={{header|CoffeeScript}}==

print_power_set = (arr) ->

console.log "POWER SET of #{arr}"

print_power_set [4, 2, 1]

print_power_set ['dog', 'c', 'b', 'a']

> coffee power_set.coffee

POWER SET of

[ 'dog', 'c', 'b' ]

[ 'dog', 'c', 'b', 'a' ]

 

=={{header|ColdFusion}}==

 

{

var ps = [""];

}

 

 

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

s

:from-end t

>(power-set '(1 2 3))

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

 

Alternate, more recursive (same output):

(if (null l)

(list nil)

(let ((prev (powerset (cdr l))))

(append (mapcar #'(lambda (elt) (cons (car l) elt)) prev)

 

 

Imperative-style using LOOP:

(loop for i below (expt 2 (length xs)) collect

>(powerset '(1 2 3)

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

 

=={{header|D}}==

}

 

{{out}}

 

 

 

 

}

 

}

 

 

=={{header|E}}==

 

 

def powerset(s) {

})

}

 

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>

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]

 

<code>[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3], [4], [1,4], [2,4], [1,2,4], [3,4], [1,3,4], [2,3,4], [1,2,3,4]]</code>

 

Alternate shorter and more efficient version:

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

 

or even more efficient version:

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

powerset(H, PT, PT).

 

powerset(_, [], Acc) -> Acc;

 

=={{header|F Sharp|F#}}==

almost exact copy of OCaml version

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

=={{header|Factor}}==

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

IN: powerset

 

: add ( set elt -- newset ) 1array <hash-set> union ;

Usage:

HS{

HS{ 1 2 3 4 }

HS{ 1 3 4 }

HS{ 2 3 4 }

 

=={{header|Forth}}==

{{works with|4tH|3.61.0}}.

{{trans|C}}

: .set begin dup while ?print >r 1+ r> 1 rshift repeat drop drop ;

: .powerset 0 do ." ( " 1 i .set ." )" cr loop ;

: powerset 1 argn check-none check-size 1- lshift .powerset ;

 

<pre>

$ 4th cxq powerset.4th 1 2 3 4

( 1 2 3 4 )

</pre>

 

=={{header|Frink}}==

Frink's set and array classes have built-in subsets[] methods that return all subsets. If called with an array, the results are arrays. If called with a set, the results are sets.

a = new set[1,2,3,4]

a.subsets[]

 

=={{header|GAP}}==

Combinations([1, 2, 3]);

# [ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 2, 3 ], [ 3 ] ]

Combinations([1, 2, 3, 1]);

# [ [ ], [ 1 ], [ 1, 1 ], [ 1, 1, 2 ], [ 1, 1, 2, 3 ], [ 1, 1, 3 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ],

 

=={{header|Go}}==

set add method. Adding elements with the add method ensures the uniqueness property.

 

 

import (

"fmt"

"strconv"

)

 

// element is an interface, allowing different kinds of elements to be

// implemented and stored in sets.

// the mathematical definition of a set. a.eq(b) must give the same

// result as b.eq(a).

// String result is used only for printable output. Given a, b where

// a.eq(b), it is not required that a.String() == b.String().

}

 

// integer type satisfying element interface

 

}

 

return strconv.Itoa(int(i))

}

 

 

// uniqueness of elements can be ensured by using add method

for _, ex := range *s {

}

}

}

 

t, ok := e.(set)

if !ok {

return false

}

for _, se := range s {

return false

}

}

 

func (s set) String() string {

}

}

}

 

var u set

for _, er := range r {

}

r = append(r, u...)

func main() {

var s set

}

ps := s.powerSet()

<pre>

</pre>

 

=={{header|Groovy}}==

Builds on the [[Combinations#Groovy|Combinations]] solution. '''Sets''' are not a "natural" collection type in Groovy. '''Lists''' are much more richly supported. Thus, this solution is liberally sprinkled with coercion from '''Set''' to '''List''' and from '''List''' to '''Set'''.

}

 

 

Test program:

 

 

=={{header|Haskell}}==

import Control.Monad

 

 

listPowerset :: [a] -> [[a]]

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

or

Examples:

 

 

A method using only set operations and set mapping is also possible. Ideally, <code>Set</code> would be defined as a Monad, but that's impossible given the constraint that the type of inputs to Set.map (and a few other functions) be ordered.

type Set=Set.Set

unionAll :: (Ord a) => Set (Set a) -> Set a

 

powerSet :: (Ord a) => Set a -> Set (Set a)

Usage:

Prelude Data.Set> powerSet fromList [1,2,3]

 

=={{header|Icon}} and {{header|Unicon}}==

The following version returns a set containing the powerset:

 

procedure power_set (s)

result := set ()

return result

end

 

To test the above procedure:

 

procedure main ()

every s := !power_set (set(1,2,3,4)) do { # requires '!' to generate items in the result set

}

end

 

<pre>

[ 3 ]

An alternative version, which generates each item in the power set in turn:

 

procedure power_set (s)

if *s = 0

}

end

 

=={{header|J}}==

 

There are a [http://www.jsoftware.com/jwiki/Essays/Power_Set number of ways] to generate a power set in J. Here's one:

For example:

E

AE

AC

 

In the typical use, this operation makes sense on collections of unique elements.

 

1 2 3

#ps 1 2 3 2 1

32

#ps ~.1 2 3 2 1

 

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.

[[Category:Recursion]]

This implementation sorts each subset, but not the whole list of subsets (which would require a custom comparator). It also destroys the original set.

{

if(n<0)

{

if(ps==null)

ps.add(" ");

return ps;

ps.addAll(tmp);

return ps;

 

===Iterative===

The iterative implementation of the above idea. Each subset is in the order that the element appears in the input list. This implementation preserves the input.

public static <T> List<List<T>> powerset(Collection<T> list) {

List<List<T>> ps = new ArrayList<List<T>>();

return ps;

}

 

===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ⁿ - 1. If the k^th bit in the binary string is 1, the k^th element of the original set is in this combination.

LinkedList<T> A){

LinkedList<LinkedList<T>> ans= new LinkedList<LinkedList<T>>();

int ansSize = (int)Math.pow(2, A.size());

LinkedList<T> thisComb = new LinkedList<T>(); //place to put one combination

for(int j= 0;j< A.size();++j){

}

return ans;

 

=={{header|JavaScript}}==

Uses a JSON stringifier from http://www.json.org/js.html

 

{{works with|SpiderMonkey}}

var ps = [[]];

for (var i=0; i < ary.length; i++) {

 

load('json2.js');

 

<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|K}}==

ps:{x@&:'+2_vs!_2^#x}

Usage:

ps "ABC"

(""

"AB"

"ABC")

 

=={{header|Logo}}==

if empty? :set [output [[]]]

localmake "rest powerset butfirst :set

 

show powerset [1 2 3]

 

=={{header|Logtalk}}==

 

:- public(powerset/2).

reverse(Tail, [Head| List], Reversed).

 

Usage example:

 

PowerSet = [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]]

 

=={{header|Lua}}==

--returns the powerset of s, out of order.

function powerset(s, start)

return ret

end

 

=={{header|M4}}==

`ifelse($#, 0, ``$0'',

eval($2 <= $3), 1,

`{powerpart(0, substr(`$1', 1, eval(len(`$1') - 2)))}')dnl

dnl

 

<pre>

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

</pre>

 

gives:

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

 

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

 

 

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

end

 

Sample Usage:

Powerset of the set of the empty set.

 

ans =

 

 

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

 

ans =

 

 

=={{header|Maxima}}==

/* {{}, {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {1, 2, 4}, {1, 3}, {1, 3, 4},

 

=={{header|Objective-C}}==

 

+ (NSArray *)powerSetForArray:(NSArray *)array {

for (int itemIndex = 0; itemIndex < array.count; itemIndex++) {

if((subsetIndex >> itemIndex) & 0x1) {

}

}

[subsets addObject:subset];

}

return subsets;

 

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

 

struct

 

;;

 

 

version for lists:

 

=={{header|Oz}}==

Oz has a library for finite set constraints. Creating a power set is a trivial application of that:

%% Given a set as a list, returns its powerset (again as a list)

fun {Powerset Set}

end

in

 

A more convential implementation without finite set constaints:

case Set of nil then [nil]

[] H|T thens

{Append Acc {Map Acc fun {$ A} H|A end}}

end

 

=={{header|PARI/GP}}==

 

=={{header|Perl}}==

sub powerset {

 

=={{header|PHP}}==

<?php

function get_subset($binary, $arr) {

print_power_sets(array('dog', 'c', 'b', 'a'));

?>

POWER SET of []

POWER SET of [singleton]

b c dog

a b c dog

 

=={{header|PicoLisp}}==

(ifn Lst

(cons)

(conc

(mapcar '((X) (cons (car Lst) X)) L)

 

=={{header|Prolog}}==

 

 

</pre>

 

CHR is a programming language created by '''Professor Thom Frühwirth'''.<br>

Works with SWI-Prolog and module chr written by '''Tom Schrijvers''' and '''Jan Wielemaker'''.

 

:- chr_constraint chr_power_set/2, chr_power_set/1, clean/0.

 

empty_element @ chr_power_set([], _) <=> chr_power_set([]).

<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],[]] .

=={{header|PureBasic}}==

This code is for console mode.

Define argc=CountProgramParameters()

If argc>=(SizeOf(Integer)*8) Or argc<1

PrintN("}")

EndIf

<!-- Output modified with a line break to avoid being too long -->

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

 

=={{header|Python}}==

# the power set of the empty set has one element, the empty set

result = [[]]

 

def powerset(s):

 

<tt>list_powerset</tt> computes the power set of a list of distinct elements. <tt>powerset</tt> simply converts the input and output from lists to sets. We use the <tt>frozenset</tt> type here for immutable sets, because unlike mutable sets, it can be put into other sets.

 

<pre>

>>> list_powerset([1,2,3])

frozenset([frozenset([3]), frozenset([1, 2]), frozenset([]), frozenset([2, 3]), frozenset([1]), frozenset([1, 3]), frozenset([1, 2, 3]), frozenset([2])])

</pre>

==== Further Explanation ====

If you take out the requirement to produce sets and produce list versions of each powerset element, then add a print to trace the execution, you get this simplified version of the program above where it is easier to trace the inner workings

r = [[]]

for e in s:

 

s= [0,1,2,3]

 

<pre>r: [[]] e: 0

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

If you list the members of the set and include them according to if the corresponding bit position of a binary count is true then you generate the powerset.

(Note that only frozensets can be members of a set in the second function)

''' Generate a 'powerset' for sequence types that are indexable by integers.

Uses a binary count to enumerate the members and returns a list

set([frozenset([7]), frozenset([8, 6, 7]), frozenset([6]), frozenset([6, 7]), frozenset([]), frozenset([8]), frozenset([8, 7]), frozenset([8, 6])])

'''

 

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

 

=={{header|Qi}}==

{{trans|Scheme}}

(define powerset

[] -> [[]]

[A|As] -> (append (map (cons A) (powerset As))

(powerset As)))

 

=={{header|R}}==

{{libheader|sets}}

An example with a vector.

sv <- as.set(v)

{{}, {1}, {4}, {9}, {1, 4}, {1, 9}, {4, 9}, {1, 4, 9}}

An example with a list.

sl <- as.set(l)

{{}, {1}, {"qwerty"}, {<<list(2)>>}, {1, <<list(2)>>}, {"qwerty",

1}, {"qwerty", <<list(2)>>}, {"qwerty", 1, <<list(2)>>}}

 

=={{header|Racket}}==

;;; Direct translation of 'functional' ruby method

(define (powerset s)

(list->set (set-map outer-set

(λ(inner-set) (set-add inner-set element)))))))

 

=={{header|Rascal}}==

import Set;

 

public set[set[&T]] PowerSet(set[&T] s) = power(s);

rascal>PowerSet({1,2,3,4})

set[set[int]]: {

{}

}

 

=={{header|REXX}}==

 

1 {}

2 {one}

15 {two,three,four}

16 {one,two,three,four}

</pre>

 

=={{header|Ruby}}==

class Array

# Adds a power_set method to every array, i.e.: [1, 2].power_set

p %w(one two three).func_power_set

 

{{out}}

<pre>

[[], ["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|Scala}}==

 

=={{header|Scheme}}==

{{trans|Common Lisp}}

(if (null? set)

'(())

 

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

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

((A C E) (A C) (A E) (A) (C E) (C) (E) ())

 

(define (iter yield)

(let recur ((a '()) (b lst))

(display a)

(newline)

(1 3)

(1)

(2)

(3)

 

(define (power_set_iter set)

(let loop ((res '(())) (s set))

res

(loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s)))))

 

'((e d c b a)

(e d c b)

(a)

())

 

=={{header|Seed7}}==

const func array bitset: powerSet (in bitset: baseSet) is func

writeln(aSet);

end for;

 

<pre>

{}

{2, 3, 4}

{1, 2, 3, 4}

</pre>

 

Code from [http://smalltalk.gnu.org/blog/bonzinip/fun-generators Bonzini's blog]

 

power [

^(0 to: (1 bitShift: self size) - 1) readStream collect: [ :each || i |

self select: [ :elem | (each bitAt: (i := i + 1)) = 1 ] ]

]

 

each asArray printNl ].

 

#( 'A' 'C' 'E' ) power do: [ :each |

 

=={{header|Standard ML}}==

 

version for lists:

 

=={{header|Tcl}}==

set res [list [list]]

foreach e $l {

return $res

}

<pre>{} a b {a b} c {a c} {b c} {a b c} d {a d} {b d} {a b d} {c d} {a c d} {b c d} {a b c d}</pre>

===Binary Count Method===

set res {}

for {set i 0} {$i < 2**[llength $set]} {incr i} {

}

return $res

 

=={{header|TXR}}==

 

 

@(output)

@ (repeat)

{@(rep)@pset, @(last)@pset@(empty)@(end)}

@ (end)

{1, 2, 3}

{1, 2}

{3}

{}</pre>

 

=={{header|UnixPipes}}==

| cat A

a

b c

c