Power set: Difference between revisions
m
→{{header|Fōrmulæ}}
(→{{header|Quackery}}: Added commentary.) |
|||
(27 intermediate revisions by 15 users not shown) | |||
Line 35:
{{trans|Python}}
<
V result = [[Int]()]
L(x) lst
Line 41:
R result
print(list_powerset([1, 2, 3]))</
{{out}}
Line 52:
This works for ABAP Version 7.40 and above
<syntaxhighlight lang="abap">
report z_powerset.
Line 233:
)->add_element( `4` )->add_element( `4` ).
write: |𝑷( { set3->set~stringify( ) } ) -> { set3->build_powerset( )->set~stringify( ) }|, /.
</syntaxhighlight>
{{out}}
Line 249:
A solution (without recursion) that prints the power set of the n arguments passed by the command line. The idea is that the i'th bit of a natural between 0 and <math>2^n-1</math> indicates whether or not we should put the i'th element of the command line inside the set.
<syntaxhighlight lang="ada">
with Ada.Text_IO, Ada.Command_Line;
use Ada.Text_IO, Ada.Command_Line;
Line 272:
end loop;
end powerset;
</syntaxhighlight>
Line 302:
Requires: ALGOL 68g mk14.1+
<
PROC power set = ([]MEMBER s)[][]MEMBER:(
Line 328:
printf(($"set["d"] = "$,member, repr set, set[member],$l$))
OD
)</
{{out}}
<pre>
Line 344:
{{works with|Dyalog APL}}
<
{{out}}
Line 374:
(functional composition examples)
{{Trans|Haskell}}
<
-- powerset :: [a] -> [[a]]
Line 449:
end script
end if
end mReturn</
{{Out}}
<
{"Empty set", {{}}},
{"Set containing only empty set", {{}, {{}}}}}</
=={{header|Arturo}}==
<
{{out}}
Line 464:
=={{header|ATS}}==
<syntaxhighlight lang="text">
(* ****** ****** *)
//
Line 548:
(* ****** ****** *)
</syntaxhighlight>
=={{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
Line 562:
t .= "}`n{" ; new subsets in new lines
}
MsgBox % RegExReplace(SubStr(t,1,StrLen(t)-1),",}","}")</
=={{header|AWK}}==
<
#!/usr/local/bin/gawk -f
Line 575:
# For each input
{ for (i=0;i<=2^NF-1;i++) if (i == 0) printf("empty\n"); else printf("(%s)\n",tochar(i,NF)) }
</syntaxhighlight>
{{out}}
Line 599:
</pre>
=={{header|
==={{header|BBC BASIC}}===
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
Line 617 ⟶ 618:
s$ += "},"
NEXT i%
= LEFT$(s$) + "}"</
{{out}}
<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|BQN}}==
<syntaxhighlight lang="bqn">P ← (⥊·↕2⥊˜≠)/¨<</syntaxhighlight>
{{out}}
<pre>
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 ⟩ ⟩
</pre>
=={{header|Bracmat}}==
<
= done todo first
. !arg:(?done.?todo)
Line 633 ⟶ 643:
)
& out$(powerset$(.1 2 3 4))
);</
{{out}}
<pre> 1 2 3 4
Line 654 ⟶ 664:
=={{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}}
</syntaxhighlight>
=={{header|C}}==
<
struct node {
Line 690 ⟶ 700:
powerset(argv + 1, argc - 1, 0);
return 0;
}</
{{out}}
<pre>
Line 705 ⟶ 715:
=={{header|C sharp|C#}}==
<
public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
Line 727 ⟶ 737:
}
</syntaxhighlight>
{{out}}
Line 750 ⟶ 760:
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>() }
Line 758 ⟶ 768:
a.Concat(a.Select(x => x.Concat(new List<T>() { b }))));
}
</syntaxhighlight>
Non-recursive version
<
using System;
class Powerset
Line 787 ⟶ 797:
}
}
</syntaxhighlight>
----------------
Line 793 ⟶ 803:
Recursive version
<
using System;
class Powerset
Line 815 ⟶ 825:
}
}
}</
=={{header|C++}}==
Line 821 ⟶ 831:
=== Non-recursive version ===
<
#include <set>
#include <vector>
Line 898 ⟶ 908:
std::cout << " }\n";
}
}</
{{out}}
Line 924 ⟶ 934:
This simplified version has identical output to the previous code.
<
#include <set>
#include <iostream>
Line 959 ⟶ 969:
}
}
</syntaxhighlight>
=== Recursive version ===
<
#include <set>
Line 988 ⟶ 998:
return powerset(s, s.size());
}
</syntaxhighlight>
=={{header|Clojure}}==
<
(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:
<
(reduce (fn [a x]
(into a (map #(conj % x)) a))
#{#{}} coll))
(powerset #{1 2 3})</
<
'''Using bit-test''':
see: https://clojuredocs.org/clojure.core/bit-test#example-5d401face4b0ca44402ef78b
<
(let [cnt (count coll)
bits (Math/pow 2 cnt)]
Line 1,018 ⟶ 1,028:
(nth coll j)))))
(powerset [1 2 3])</
<
=={{header|CoffeeScript}}==
<
print_power_set = (arr) ->
console.log "POWER SET of #{arr}"
Line 1,051 ⟶ 1,061:
print_power_set [4, 2, 1]
print_power_set ['dog', 'c', 'b', 'a']
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="text">
> coffee power_set.coffee
POWER SET of
Line 1,083 ⟶ 1,093:
[ 'dog', 'c', 'b' ]
[ 'dog', 'c', 'b', 'a' ]
</syntaxhighlight>
=={{header|ColdFusion}}==
Line 1,089 ⟶ 1,099:
Port from the [[#JavaScript|JavaScript]] version,
compatible with ColdFusion 8+ or Railo 3+
<
{
var ps = [""];
Line 1,106 ⟶ 1,116:
}
var res = powerset([1,2,3,4]);</
{{out}}
Line 1,112 ⟶ 1,122:
=={{header|Common Lisp}}==
<
(if s (mapcan (lambda (x) (list (cons (car s) x) x))
(powerset (cdr s)))
'(())))</
{{out}}
Line 1,121 ⟶ 1,131:
((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)
<
(reduce #'(lambda (item ps)
(append (mapcar #'(lambda (e) (cons item e))
Line 1,128 ⟶ 1,138:
s
:from-end t
:initial-value '(())))</
{{out}}
>(power-set '(1 2 3))
Line 1,135 ⟶ 1,145:
Alternate, more recursive (same output):
<
(if (null l)
(list nil)
(let ((prev (powerset (cdr l))))
(append (mapcar #'(lambda (elt) (cons (car l) elt)) prev)
prev))))</
Imperative-style using LOOP:
<
(loop for i below (expt 2 (length xs)) collect
(loop for j below i for x in xs if (logbitp j i) collect x)))</
{{out}}
>(powerset '(1 2 3)
Line 1,152 ⟶ 1,162:
Yet another imperative solution, this time with dolist.
<
(let ((pow-set (list nil)))
(dolist (element (reverse list) pow-set)
(dolist (set pow-set)
(push (cons element set) pow-set)))))</
{{out}}
>(power-set '(1 2 3))
Line 1,164 ⟶ 1,174:
This implementation defines a range which *lazily* enumerates the power set.
<
import std.range;
Line 1,190 ⟶ 1,200:
import std.stdio;
args[1..$].powerSet.each!writeln;
}</
An alternative version, which implements the range construct from scratch:
<
struct PowerSet(R)
Line 1,235 ⟶ 1,245:
}
auto powerSet(R)(R r) { return PowerSet!R(r); }</
{{out}}
<pre>$ rdmd powerset a b c
Line 1,261 ⟶ 1,271:
#It doesn't rely on integer bit fiddling, so it should work on arrays larger than size_t.
<syntaxhighlight lang="d">
// Haskell definition:
// foldr f z [] = z
Line 1,278 ⟶ 1,288:
return foldr( (T x, T[][] acc) => acc ~ acc.map!(accx => x ~ accx).array , [[]], set );
}
</syntaxhighlight>
=={{header|Déjà Vu}}==
Line 1,284 ⟶ 1,294:
In Déjà Vu, sets are dictionaries with all values <code>true</code> and the default set to <code>false</code>.
<
local :out [ set{ } ]
for value in keys s:
Line 1,293 ⟶ 1,303:
out
!. powerset set{ 1 2 3 4 }</
{{out}}
Line 1,301 ⟶ 1,311:
{{libheader| System.SysUtils}}
{{Trans|C#}}
<syntaxhighlight lang="delphi">
program Power_set;
Line 1,331 ⟶ 1,341:
rec(0,0);
{$IFNDEF UNIX}readln;{$ENDIF}
end.</
=={{header|Dyalect}}==
{{trans|C#}}
<syntaxhighlight lang="dyalect">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)</syntaxhighlight>
=={{header|E}}==
<
def powerset(s) {
Line 1,343 ⟶ 1,373:
})
}
}</
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|EchoLisp}}==
<
(define (set-cons a A)
(make-set (cons a A)))
Line 1,380 ⟶ 1,410:
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Erlang}}
<
use Bitwise
def powerset1(list) do
Line 1,412 ⟶ 1,442:
IO.inspect RC.powerset3([1,2,3])
IO.inspect RC.powerset1([])
IO.inspect RC.powerset1(["one"])</
{{out}}
Line 1,438 ⟶ 1,468:
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
</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]
|| I <- lists:seq(0,Max-1)].</
{{out}}
Line 1,448 ⟶ 1,478:
Alternate shorter and more efficient version:
<
powerset([H|T]) -> PT = powerset(T),
[ [H|X] || X <- PT ] ++ PT.</
or even more efficient version:
<
powerset([H|T]) -> PT = powerset(T),
powerset(H, PT, PT).
powerset(_, [], Acc) -> Acc;
powerset(X, [H|T], Acc) -> powerset(X, T, [[X|H]|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 [[]]
</syntaxhighlight>
alternatively with list comprehension
<
let rec pow =
function
| [] -> [[]]
| x::xs -> [for i in pow xs do yield! [i;x::i]]
</syntaxhighlight>
=={{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 ;
: powerset ( set -- newset ) members { HS{ } } [ dupd [ add ] curry map append ] reduce <hash-set> ;</
Usage:
<
HS{
HS{ 1 2 3 4 }
Line 1,501 ⟶ 1,531:
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 ;
Line 1,513 ⟶ 1,543:
: powerset 1 argn check-none check-size 1- lshift .powerset ;
powerset</
{{out}}
<pre>
Line 1,538 ⟶ 1,568:
=={{header|FreeBASIC}}==
Los elementos de un conjunto se representan como bits en un número entero (por lo tanto, el tamaño máximo del conjunto es 32).
<
If Ubound(set,1) > 31 Then Print "Set demasiado grande para representarlo como un entero" : Exit Function
If Ubound(set,1) < 0 Then Print "{}": Exit Function ' Set vacío
Line 1,563 ⟶ 1,593:
Dim As String set1(0) = {""}
Print ConjuntoPotencia(set1())
Sleep</
{{out}}
<pre>
Line 1,579 ⟶ 1,609:
=={{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[]
</syntaxhighlight>
=={{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.
<
The powerset function could be implemented in FunL directly as:
<
powerset( {} ) = {{}}
powerset( s ) =
acc = powerset( s.tail() )
acc + map( x -> {s.head()} + x, acc )</
or, alternatively as:
<
def powerset( s ) = foldr( \x, acc -> acc + map( a -> {x} + a, acc), {{}}, s )
println( powerset({1, 2, 3, 4}) )</
{{out}}
Line 1,612 ⟶ 1,642:
=={{header|Fōrmulæ}}==
'''Solution'''
No program needed. Power set is intrinsically supported in Fōrmulæ.
'''Case 1.''' Power set of the set {1, 2, 3, 4}
[[File:Fōrmulæ - Power set 01.png]]
[[File:Fōrmulæ - Power set 02.png]]
'''Case 2.''' The power set of the empty set is the set which contains itself.
[[File:Fōrmulæ - Power set 03.png]]
[[File:Fōrmulæ - Power set 04.png]]
'''Case 3.''' 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
[[File:Fōrmulæ - Power set 05.png]]
[[File:Fōrmulæ - Power set 06.png]]
'''Case 4.''' Even when it is intrinsically supported, a program can be written:
[[File:Fōrmulæ - Power set 07.png]]
[[File:Fōrmulæ - Power set 08.png]]
[[File:Fōrmulæ - Power set 09.png]]
=={{header|GAP}}==
<
Combinations([1, 2, 3]);
# [ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 2, 3 ], [ 3 ] ]
Line 1,626 ⟶ 1,682:
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 ],
# [ 2 ], [ 2, 3 ], [ 3 ] ]</
=={{header|Go}}==
Line 1,635 ⟶ 1,691:
While the "add" and "has" methods make a usable set type, the power set method implemented here computes a result directly without using the add method. 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.
<
import (
Line 1,775 ⟶ 1,831:
}
}
}</
{{out}}
<pre>
Line 1,793 ⟶ 1,849:
=={{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'''.
<
def powerSetRec(head, tail) {
if (!tail) return [head]
Line 1,800 ⟶ 1,856:
def powerSet(set) { powerSetRec([], set as List) as Set}
</syntaxhighlight>
Test program:
<
def vocalists = [ 'C', 'S', 'N', 'Y' ] as Set
println vocalists
println powerSet(vocalists)
</syntaxhighlight>
{{out}}
Line 1,816 ⟶ 1,872:
=={{header|Haskell}}==
<
import Control.Monad
Line 1,823 ⟶ 1,879:
listPowerset :: [a] -> [[a]]
listPowerset = filterM (const [True, False])</
<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'''
<
powerset (head:tail) = acc ++ map (head:) acc where acc = powerset tail</
or
<
powerSet = foldr (\x acc -> acc ++ map (x:) acc) [[]]</
which could also be understood, in point-free terms, as:
<
powerSet = foldr ((mappend <*>) . fmap . (:)) (pure [])</
Examples:
Line 1,852 ⟶ 1,908:
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
Line 1,866 ⟶ 1,922:
powerSet :: (Ord a) => Set a -> Set (Set a)
powerSet = (Set.fold (slift Set.union) (Set.singleton Set.empty)) . Set.map makeSet</
Usage:
<syntaxhighlight 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]]</
=={{header|Icon}} and {{header|Unicon}}==
Line 1,880 ⟶ 1,936:
The following version returns a set containing the powerset:
<syntaxhighlight lang="icon">
procedure power_set (s)
result := set ()
Line 1,895 ⟶ 1,951:
return result
end
</syntaxhighlight>
To test the above procedure:
<syntaxhighlight lang="icon">
procedure main ()
every s := !power_set (set(1,2,3,4)) do { # requires '!' to generate items in the result set
Line 1,907 ⟶ 1,963:
}
end
</syntaxhighlight>
{{out}}
Line 1,933 ⟶ 1,989:
An alternative version, which generates each item in the power set in turn:
<syntaxhighlight lang="icon">
procedure power_set (s)
if *s = 0
Line 1,953 ⟶ 2,009:
}
end
</syntaxhighlight>
=={{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
Line 1,968 ⟶ 2,024:
AE
AC
ACE</
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
8</
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.
Line 1,986 ⟶ 2,042:
[[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)
Line 2,010 ⟶ 2,066:
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>>();
Line 2,038 ⟶ 2,094:
return ps;
}
</syntaxhighlight>
===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.
<
LinkedList<T> A){
LinkedList<LinkedList<T>> ans= new LinkedList<LinkedList<T>>();
Line 2,057 ⟶ 2,113:
}
return ans;
}</
=={{header|JavaScript}}==
Line 2,066 ⟶ 2,122:
{{works with|SpiderMonkey}}
<
var ps = [[]];
for (var i=0; i < ary.length; i++) {
Line 2,079 ⟶ 2,135:
load('json2.js');
print(JSON.stringify(res));</
{{out}}
Line 2,089 ⟶ 2,145:
{{trans|Haskell}}
<
// translating: powerset = foldr (\x acc -> acc ++ map (x:) acc) [[]]
Line 2,109 ⟶ 2,165:
}
})();</
{{Out}}
<syntaxhighlight lang="javascript">{
"[1,2,3] ->":[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]],
"empty set ->":[[]],
"set which contains only the empty set ->":[[], [[]]]
}</
===ES6===
<
'use strict';
Line 2,139 ⟶ 2,195:
])
};
})()</
{{Out}}
<
"empty set ->":[[]],
"set which contains only the empty set ->":[[], [[]]]}</
=={{header|jq}}==
<
reduce .[] as $i ([[]];
reduce .[] as $r (.; . + [$r + [$i]]));</
Example:
[range(0;10)]|powerset|length
Line 2,155 ⟶ 2,211:
Extra credit:
<syntaxhighlight lang="jq">
# The power set of the empty set:
[] | powerset
Line 2,162 ⟶ 2,218:
# The power set of the set which contains only the empty set:
[ [] ] | powerset
# => [[],[[]]]</
====Recursive version====
<
if length == 0 then [[]]
else .[0] as $first
| (.[1:] | powerset)
| map([$first] + . ) + .
end;</
Example:
[1,2,3]|powerset
Line 2,175 ⟶ 2,231:
=={{header|Julia}}==
<
function powerset
result = Vector{T}[[]]
for elem in x, j in eachindex(result)
Line 2,183 ⟶ 2,239:
result
end
</syntaxhighlight>
{{Out}}
<pre>
julia> show(powerset([1,2,3]))
[Int64[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
</pre>
===Non-Mutating Solution===
<syntaxhighlight lang="julia">
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
</syntaxhighlight>
{{Out}}
<pre>
julia> show(powerset([1,2,3]))
[Int64[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
</pre>
=={{header|K}}==
<syntaxhighlight lang="k">
ps:{x@&:'+2_vs!_2^#x}
</syntaxhighlight>
Usage:
<syntaxhighlight lang="k">
ps "ABC"
(""
Line 2,205 ⟶ 2,288:
"AB"
"ABC")
</syntaxhighlight>
=={{header|Kotlin}}==
<
fun <T> Set<T>.subsets(): Sequence<Set<T>> =
when (size) {
Line 2,234 ⟶ 2,317:
}
}
</syntaxhighlight>
{{out}}
Line 2,263 ⟶ 2,346:
[[]]
</pre>
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
{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]]]
</syntaxhighlight>
=={{header|Logo}}==
<
if empty? :set [output [[]]]
localmake "rest powerset butfirst :set
Line 2,272 ⟶ 2,389:
show powerset [1 2 3]
[[1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []]</
=={{header|Logtalk}}==
<
:- public(powerset/2).
Line 2,299 ⟶ 2,416:
reverse(Tail, [Head| List], Reversed).
:- end_object.</
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]]
yes</
=={{header|Lua}}==
<
--returns the powerset of s, out of order.
function powerset(s, start)
Line 2,341 ⟶ 2,458:
return ret
end
</syntaxhighlight>
=={{header|M4}}==
<
`ifelse($#, 0, ``$0'',
eval($2 <= $3), 1,
Line 2,365 ⟶ 2,482:
`{powerpart(0, substr(`$1', 1, eval(len(`$1') - 2)))}')dnl
dnl
powerset(`{a,b,c}')</
{{out}}
Line 2,373 ⟶ 2,490:
=={{header|Maple}}==
<syntaxhighlight lang="maple">
combinat:-powerset({1,2,3,4});
</syntaxhighlight>
{{out}}
<pre>
Line 2,383 ⟶ 2,500:
</pre>
=={{header|Mathematica}}/{{header|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:
<
gives:
<
Subsets[list, {n, Infinity}] gives all the subsets that have n elements or more.
Line 2,403 ⟶ 2,520:
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
Line 2,420 ⟶ 2,537:
end
end</
Sample Usage:
Powerset of the set of the empty set.
<
ans =
{} {1x1 cell} %This is the same as { {},{{}} }</
Powerset of { {1,2},3 }.
<
ans =
{1x0 cell} {1x1 cell} {1x1 cell} {1x2 cell} %This is the same as { {},{{1,2}},{3},{{1,2},3} }</
=={{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}} */</
=={{header|Nim}}==
<
proc hash(x: HashSet[int]): Hash =
Line 2,459 ⟶ 2,576:
result.incl(newSet)
echo powerset([1,2,3,4].toHashSet())</
{{out}}
Line 2,466 ⟶ 2,583:
=={{header|Objective-C}}==
<
+ (NSArray *)powerSetForArray:(NSArray *)array {
Line 2,481 ⟶ 2,598:
}
return subsets;
}</
=={{header|OCaml}}==
Line 2,487 ⟶ 2,604:
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
Line 2,503 ⟶ 2,620:
;;
end;; (* PowerSet *)</
version for lists:
<
=={{header|OPL}}==
<syntaxhighlight lang="opl">
{string} s={"A","B","C","D"};
range r=1.. ftoi(pow(2,card(s)));
Line 2,519 ⟶ 2,636:
writeln(s2);
}
</syntaxhighlight>
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"}]
</syntaxhighlight>
=={{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}
Line 2,547 ⟶ 2,664:
end
in
{Inspect {Powerset [1 2 3 4]}}</
A more convential implementation without finite set constaints:
<
case Set of nil then [nil]
[] H|T thens
Line 2,557 ⟶ 2,674:
{Append Acc {Map Acc fun {$ A} H|A end}}
end
end</
=={{header|PARI/GP}}==
<
{{works with|PARI/GP|2.10.0+}}
The <code>forsubset</code> iterator was added in version 2.10.0 to efficiently iterate over combinations and power sets.
<
forsubset(#S,s,print1(vecextract(S,s)" "))</
{{out}}
<pre>[] ["a"] ["b"] ["c"] ["a", "b"] ["a", "c"] ["b", "c"] ["a", "b", "c"]</pre>
Line 2,576 ⟶ 2,693:
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.
<
my @S = ("a","b","c");
my @PS;
Line 2,583 ⟶ 2,700:
push @PS, "[@$p]"
}
say join(" ",@PS);</
{{out}}
<pre>[a b c] [b c] [a c] [c] [a b] [b] [a] []</pre>
Line 2,590 ⟶ 2,707:
{{libheader|ntheory}}
The simplest solution is to use the one argument version of the combination iterator, which iterates over the power set.
<
my @S = qw/a b c/;
forcomb { print "[@S[@_]] " } scalar(@S);
print "\n";</
{{out}}
<pre>[] [a] [b] [c] [a b] [a c] [b c] [a b c]</pre>
Using the two argument version of the iterator gives a solution similar to the Raku and Python array versions.
<
my @S = qw/a b c/;
for $k (0..@S) {
Line 2,604 ⟶ 2,721:
forcomb { print "[@S[@_]] " } @S,$k;
}
print "\n";</
{{out}}
<pre>[] [a] [b] [c] [a b] [a c] [b c] [a b c] </pre>
Similar to the Pari/GP solution, one can also use <tt>vecextract</tt> 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 <tt>vecreduce</tt> could be done identical to the array reduce solution shown later.
<
my @S = qw/a b c/;
my @PS = map { "[".join(" ",vecextract(\@S,$_))."]" } 0..2**scalar(@S)-1;
say join(" ",@PS);</
{{out}}
<pre>[] [a] [b] [a b] [c] [a c] [b c] [a b c]</pre>
Line 2,620 ⟶ 2,737:
The CPAN module [https://metacpan.org/pod/Set::Object Set::Object] provides a set implementation for sets of arbitrary objects, for which a powerset function could be defined and used like so:
<
sub powerset {
Line 2,633 ⟶ 2,750:
my $powerset = powerset($set);
print $powerset->as_string, "\n";</
{{out}}
Line 2,643 ⟶ 2,760:
using a hash as the underlying representation (like the task description suggests):
<
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 [https://metacpan.org/pod/Set::Tiny Set::Tiny])''
Line 2,656 ⟶ 2,773:
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:
<
sub powerset {
Line 2,666 ⟶ 2,783:
my @subsets = powerset($set);
print $_->as_string, "\n" for @subsets;</
{{out}}
Line 2,685 ⟶ 2,802:
Recursive solution:
<
@_ ? map { $_, [$_[0], @$_] } powerset(@_[1..$#_]) : [];
}</
List folding solution:
<
sub powerset {
@{( reduce { [@$a, map([@$_, $b], @$a)] } [[]], @_ )}
}</
Usage & output:
<
my @powerset = powerset(@set);
Line 2,705 ⟶ 2,822:
}
print set_to_string(@powerset), "\n";</
{{out}}
<pre>
Line 2,718 ⟶ 2,835:
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 <tt>vecextract</tt> operation by hand.
<
use warnings;
sub powerset :prototype(&@) {
my $callback = shift;
my $bitmask = '';
Line 2,739 ⟶ 2,856:
powerset { ++$i } 1..9;
print "The powerset of a nine element set contains $i elements.\n";
</syntaxhighlight>
{{out}}
<pre>powerset of empty set:
Line 2,766 ⟶ 2,883:
=={{header|Phix}}==
<!--<
<span style="color: #004080;">sequence</span> <span style="color: #000000;">powerset</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">step</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
Line 2,796 ⟶ 2,913:
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d0</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">power_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d0</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<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>
===alternative===
Adapted from the one I used on [[Ascending_primes#powerset]].
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">power_set</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">powerset</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{}},</span> <span style="color: #000000;">subset</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{},</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">subset</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">subset</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">sub</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">subset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ni</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sub</span><span style="color: #0000FF;">),</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">next</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">ni</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">powerset</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">powerset</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ni</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">subset</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">powerset</span><span style="color: #0000FF;">)=</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)))</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">powerset</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">power_set</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">power_set</span><span style="color: #0000FF;">({</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">power_set</span><span style="color: #0000FF;">({})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">power_set</span><span style="color: #0000FF;">({{}})</span>
<!--</syntaxhighlight>-->
{{out}}
Guaranteed to be in length order, and index order within each length.
<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}}
{{},{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}}
{{}}
{{},{{}}}
Line 2,805 ⟶ 2,957:
=={{header|PHP}}==
<syntaxhighlight lang="php">
<?php
function get_subset($binary, $arr) {
Line 2,865 ⟶ 3,017:
print_power_sets(array('dog', 'c', 'b', 'a'));
?>
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="text">
POWER SET of []
POWER SET of [singleton]
Line 2,889 ⟶ 3,041:
b c dog
a b c dog
</syntaxhighlight>
=={{header|PicoLisp}}==
<
(ifn Lst
(cons)
Line 2,898 ⟶ 3,050:
(conc
(mapcar '((X) (cons (car Lst) X)) L)
L ) ) ) )</
=={{header|PL/I}}==
{{trans|REXX}}
<
/*--------------------------------------------------------------------
* 06.01.2014 Walter Pachl translated from REXX
Line 2,967 ⟶ 3,119:
End;
End;</
{{out}}
<pre>{}
Line 2,987 ⟶ 3,139:
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function power-set ($array) {
if($array) {
Line 3,022 ⟶ 3,174:
$setC | foreach{"{"+"$_"+"}"}
$OFS = " "
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 3,061 ⟶ 3,213:
The definitions here are elementary, logical (cut-free),
and efficient (within the class of comparably generic implementations).
<
subseq( [], []).
Line 3,067 ⟶ 3,219:
subseq( [X|Xs], [X|Ys] ) :- subseq(Xs, Ys).
subseq( [X|Xs], [_|Ys] ) :- append(_, [X|Zs], Ys), subseq(Xs, Zs).
</syntaxhighlight>
{{out}}
<pre>?- powerset([1,2,3], X).
Line 3,082 ⟶ 3,234:
===Single-Functor Definition===
<
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).</
{{out}}
<pre>?- power_set([1,2,3,4,5,6,7,8], X), length(X,N), writeln(N).
Line 3,095 ⟶ 3,247:
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.
Line 3,113 ⟶ 3,265:
empty_element @ chr_power_set([], _) <=> chr_power_set([]).
</
{{out}}
<pre> ?- chr_power_set([1,2,3,4], []), findall(L, find_chr_constraint(chr_power_set(L)), LL), clean.
Line 3,121 ⟶ 3,273:
=={{header|PureBasic}}==
This code is for console mode.
<
Define argc=CountProgramParameters()
If argc>=(SizeOf(Integer)*8) Or argc<1
Line 3,145 ⟶ 3,297:
PrintN("}")
EndIf
EndIf</
<!-- Output modified with a line break to avoid being too long -->
{{out}}
Line 3,153 ⟶ 3,305:
=={{header|Python}}==
<
# the power set of the empty set has one element, the empty set
result = [[]]
Line 3,172 ⟶ 3,324:
def powerset(s):
return frozenset(map(frozenset, list_powerset(list(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.
Line 3,186 ⟶ 3,338:
==== 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:
Line 3,194 ⟶ 3,346:
s= [0,1,2,3]
print "\npowersetlist(%r) =\n %r" % (s, powersetlist(s))</
{{out}}
Line 3,209 ⟶ 3,361:
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
Line 3,233 ⟶ 3,385:
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:])]
</syntaxhighlight>
===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:
<
>>> from itertools import chain, combinations
>>>
Line 3,272 ⟶ 3,424:
(3, 4),
(4,)}
>>> </
=={{header|Qi}}==
{{trans|Scheme}}
<syntaxhighlight lang="qi">
(define powerset
[] -> [[]]
[A|As] -> (append (map (cons A) (powerset As))
(powerset As)))
</syntaxhighlight>
=={{header|Quackery}}==
Line 3,301 ⟶ 3,453:
advantage that it permits sets of sets, which are required for this task.
<
[ stack ] is (ps).items
[ stack ] is (ps).result
Line 3,338 ⟶ 3,490:
nested
rot swap join swap ]
drop ] is powerset ( [ -->
' [ [ 1 2 3 4 ] [ ] [ [ ] ] ]
Line 3,345 ⟶ 3,497:
dup echo cr
powerset witheach [ echo cr ]
cr ]</
{{out}}
Line 3,378 ⟶ 3,530:
===Non-recursive version===
The conceptual basis for this algorithm is the following:
<syntaxhighlight lang="text">for each element in the set:
for each subset constructed so far:
new subset = (subset + element)
</syntaxhighlight>
This method is much faster than a recursive method, though the speed is still O(2^n).
<
ps <- list()
ps[[1]] <- numeric() #Start with the empty set.
Line 3,399 ⟶ 3,551:
powerset(1:4)
</syntaxhighlight>
The list "temp" is a compromise between the speed costs of doing
Line 3,411 ⟶ 3,563:
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.
<syntaxhighlight lang
An example with a vector.
<
sv <- as.set(v)
2^sv</
{{}, {1}, {4}, {9}, {1, 4}, {1, 9}, {4, 9}, {1, 4, 9}}
An example with a list.
<
sl <- as.set(l)
2^sl</
{{}, {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)
Line 3,432 ⟶ 3,584:
(list->set (set-map outer-set
(λ(inner-set) (set-add inner-set element)))))))
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|rakudo|2014-02-25}}
<syntaxhighlight lang="raku"
say powerset set <a b c d>;</
{{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:
<syntaxhighlight lang="raku"
{{out}}
<pre>
Line 3,462 ⟶ 3,614:
=={{header|Rascal}}==
<
import Set;
public set[set[&T]] PowerSet(set[&T] s) = power(s);
</syntaxhighlight>
{{out}}
<
rascal>PowerSet({1,2,3,4})
set[set[int]]: {
Line 3,488 ⟶ 3,640:
{}
}
</syntaxhighlight>
=={{header|REXX}}==
<
text='one two three four'
n=words(text)
psi=0
Do k=0 To n
Do while
Parse Var cc elist '/' cc /* get i from comb's result string */
psl=''
Do While elist<>'' /* loop through elements */
psl=psl','word(text,e) /* add corresponding test word to set */
End
psl=substr(psl,2) /* get rid of leading comma
Say right(psi,2) '{'psl'}' /* show this element of the power set */
End
End
Exit
comb: Procedure
/***********************************************************************
* Returns the combinations of size digits out of things digits
* e.g. comb(4,2) -> ' 1 2/1 3/1 4/2 3/2 4/3 4/'
1 2/ 1 3/ 1 4/ 2 3/ 2 4/ 3 4 /
***********************************************************************/
Parse Arg things,size
n=2**things-1
list=''
Do u=1 To n
co=combinations(u)
If co>'' Then
list=list '/' combinations(u)
End
Return substr(space(list),2) '/' /* remove leading / */
combinations: Procedure Expose things size
Parse Arg u
nc=0
bu=x2b(d2x(u))
bu1=space(translate(bu,' ',0),0)
If length(bu1)=size Then Do
ub=reverse(bu)
res=''
Do i=1 To things
c=i
If substr(ub,i,1)=1 Then res=res i
End
Return res
End
Else
Return ''</syntaxhighlight>
{{out|output|text= when using the default input:}}
<pre>
Line 3,544 ⟶ 3,717:
=={{header|Ring}}==
<
# Project : Power set
Line 3,565 ⟶ 3,738:
next
return left(s,len(s)-1) + "}"
</syntaxhighlight>
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|RPL}}==
{{works with|Halcyon Calc|4.2.8}}
{| class="wikitable"
! 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'''
{{out}}
<pre>
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: { { } }
</pre>
=={{header|Ruby}}==
<
# See the link if you want a shorter version.
# This was intended to show the reader how the method works.
Line 3,615 ⟶ 3,824:
p %w(one two three).func_power_set
p Set[1,2,3].powerset</
{{out}}
<pre>
Line 3,622 ⟶ 3,831:
#<Set: {#<Set: {}>, #<Set: {1}>, #<Set: {2}>, #<Set: {1, 2}>, #<Set: {3}>, #<Set: {1, 3}>, #<Set: {2, 3}>, #<Set: {1, 2, 3}>}>
</pre>
=={{header|Rust}}==
This implementation consumes the input set, requires that the type <b>T</b> has a full order a.k.a implements the <b>Ord</b> trait and that <b>T</b> is clonable.
<
fn powerset<T: Ord + Clone>(mut set: BTreeSet<T>) -> BTreeSet<BTreeSet<T>> {
Line 3,656 ⟶ 3,864:
println!("{:?}", set);
}
</syntaxhighlight>
{{out}}
Line 3,666 ⟶ 3,874:
=={{header|SAS}}==
<syntaxhighlight lang="sas">
options mprint mlogic symbolgen source source2;
Line 3,720 ⟶ 3,928:
%end;
%Mend SubSets;
</syntaxhighlight>
You can then call the macro as:
<syntaxhighlight lang="sas">
%SubSets(FieldCount = 5);
</syntaxhighlight>
The output will be the dataset SUBSETS
Line 3,769 ⟶ 3,977:
=={{header|Scala}}==
<
object Powerset extends App {
Line 3,777 ⟶ 3,985:
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:
<
A tail-recursive version:
<
def powerset_rec(acc: List[Set[A]], remaining: List[A]): List[Set[A]] = remaining match {
case Nil => acc
Line 3,789 ⟶ 3,997:
}
powerset_rec(List(Set.empty[A]), s.toList)
}</
=={{header|Scheme}}==
{{trans|Common Lisp}}
<
(if (null? set)
'(())
Line 3,805 ⟶ 4,013:
(display (power-set (list "A" "C" "E")))
(newline)</
{{out}}
((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 (iter yield)
(let recur ((a '()) (b lst))
Line 3,832 ⟶ 4,040:
(display a)
(newline)
(loop (x)))))</
{{out}}
<pre>(1 2)
Line 3,842 ⟶ 4,050:
()</pre>
Iterative:<
(define (power_set_iter set)
(let loop ((res '(())) (s set))
Line 3,848 ⟶ 4,056:
res
(loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s)))))
</syntaxhighlight>
{{out}}
Line 3,887 ⟶ 4,095:
=={{header|Seed7}}==
<
const func array bitset: powerSet (in bitset: baseSet) is func
Line 3,915 ⟶ 4,123:
writeln(aSet);
end for;
end func;</
{{out}}
Line 3,938 ⟶ 4,146:
=={{header|SETL}}==
<
Pempty := pow({});
PPempty := pow(Pempty);
Line 3,944 ⟶ 4,152:
print(Pfour);
print(Pempty);
print(PPempty);</
{{out}}
Line 3,952 ⟶ 4,160:
=={{header|Sidef}}==
<
for i in (0 .. arr.len) {
say arr.combinations(i)
}</
{{out}}
Line 3,966 ⟶ 4,174:
=={{header|Simula}}==
<
BEGIN
Line 4,089 ⟶ 4,297:
END;
END.
</syntaxhighlight>
{{out}}
<pre>
Line 4,108 ⟶ 4,316:
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 |
Line 4,114 ⟶ 4,322:
self select: [ :elem | (each bitAt: (i := i + 1)) = 1 ] ]
]
].</
<
each asArray printNl ].
#( 'A' 'C' 'E' ) power do: [ :each |
each asArray printNl ].</
=={{header|Standard ML}}==
version for lists:
<
=={{header|Swift}}==
{{works with|Swift|Revision 4 - tested with Xcode 9.2 playground}}
<
guard elements.count > 0 else {
return [[]]
Line 4,144 ⟶ 4,352:
// Example:
powersetFrom([1, 2, 4])</
{{out}}
<pre>{
Line 4,157 ⟶ 4,365:
}</pre>
<
powersetFrom(["a", "b", "d"])</
{{out}}
<pre>{
Line 4,172 ⟶ 4,380:
=={{header|Tcl}}==
<
set res [list [list]]
foreach e $l {
Line 4,179 ⟶ 4,387:
return $res
}
puts [subsets {a b c d}]</
{{out}}
<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} {
Line 4,194 ⟶ 4,402:
}
return $res
}</
=={{header|TXR}}==
Line 4,200 ⟶ 4,408:
The power set function can be written concisely like this:
<
(mappend* (op comb s) (range 0 (length s))))</
This generates the lists of combinations of all possible lengths, from 0 to the length of <code>s</code> and catenates them. The <code>comb</code> function generates a lazy list, so it is appropriate to use <code>mappend*</code> (the lazy version of <code>mappend</code>) to keep the behavior lazy.
Line 4,207 ⟶ 4,415:
A complete program which takes command line arguments and prints the power set in comma-separated brace notation:
<
(mappend* (op comb s) (range 0 (length s)))))
@(bind pset @(power-set *args*))
Line 4,214 ⟶ 4,422:
{@(rep)@pset, @(last)@pset@(empty)@(end)}
@ (end)
@(end)</
{{out}}
<pre>$ txr rosetta/power-set.txr 1 2 3
Line 4,229 ⟶ 4,437:
generalizes to strings and vectors.
<
(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))))</
{{out}}
<pre>$ txr power-set-generic.txr
Line 4,244 ⟶ 4,452:
=={{header|UNIX Shell}}==
From [http://www.catonmat.net/blog/set-operations-in-unix-shell/ here]
<
Usage
<
A
C
E
^D</
=={{header|UnixPipes}}==
<
| cat A
a
Line 4,276 ⟶ 4,484:
b c
c
</syntaxhighlight>
=={{header|Ursala}}==
Line 4,284 ⟶ 4,492:
The powerset function is a standard library function,
but could be defined as shown below.
<
test program:
<
test = powerset {'a','b','c','d'}</
{{out}}
<pre>{
Line 4,310 ⟶ 4,518:
=={{header|V}}==
V has a built in called powerlist
<
=[[A C E] [A C] [A E] [A] [C E] [C] [E] []]</
its implementation in std.v is (like joy)
<
[null?]
[unitlist]
Line 4,320 ⟶ 4,528:
[dup swapd [cons] map popd swoncat]
linrec].
</syntaxhighlight>
=={{header|VBA}}==
<
Private Function power_set(ByRef st As Collection) As Collection
Dim subset As Collection, pwset As New Collection
Line 4,368 ⟶ 4,576:
Debug.Print print_set(power_set(rcset))
Debug.Print
End Sub</
<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}}
{{}}
Line 4,374 ⟶ 4,582:
=={{header|VBScript}}==
<
q = n
Dec2Bin = ""
Line 4,406 ⟶ 4,614:
End Function
WScript.StdOut.Write PowerSet("1,2,3,4")</
{{out}}
<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|Wren}}==
{{libheader|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.
<syntaxhighlight lang="wren">import "./perm" for Powerset
var sets = [ [1, 2, 3, 4], [], [[]] ]
for (set in sets) {
System.print("The power set of %(set) is:")
System.print(
System.print()
}</
{{out}}
<pre>
The power set of [1, 2, 3, 4] is:
[[], [
The power set of [] is:
Line 4,439 ⟶ 4,642:
The power set of [[]] is:
[[], [[]]]
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">func PowSet(Set, Size);
int Set, Size;
int N, M, Mask, DoComma;
[ChOut(0, ^{);
for N:= 0 to 1<<Size -1 do
[if N>0 then ChOut(0, ^,);
ChOut(0, ^{);
Mask:= 1; DoComma:= false;
for M:= 0 to Size-1 do
[if Mask & N then
[if DoComma then ChOut(0, ^,);
IntOut(0, Set(M));
DoComma:= true;
];
Mask:= Mask << 1;
];
ChOut(0, ^});
];
Text(0, "}^m^j");
];
[PowSet([2, 3, 5, 7], 4);
PowSet([1], 1);
PowSet(0, 0);
]</syntaxhighlight>
{{out}}
<pre>
{{},{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}}
{{}}
</pre>
=={{header|zkl}}==
Using a combinations function, build the power set from combinations of 1,2,... items.
<
(0).pump(list.len(),List, Utils.Helpers.pickNFrom.fp1(list),
T(Void.Write,Void.Write) ) .append(list)
}</
<
ps:=pwerSet((1).pump(n,List)); ps.println(" Size = ",ps.len());
}</
{{out}}
<pre>
|