Rosetta Code

Power set: Difference between revisions

Page Discussion

Power set (view source)

Revision as of 22:33, 12 November 2014

78 bytes removed ,  9 years ago
m
{{out}} / -Category:Scala Implementations
(→‎{{header|Go}}: Fix June 2 change that made it not even compile! Tweak set output and demonstrate it works as expected with empty sets. gofmt.)
Line 1:
{{task|Discrete math}}
{{omit from|GUISS}}
A [[set]] is a collection (container) of certain values, without any particular order, and no repeated values. It corresponds with a finite set in mathematics. A set can be implemented as an associative array (partial mapping) in which the value of each key-value pair is ignored.
A [[set]] is a collection (container) of certain values,
without any particular order, and no repeated values.
It corresponds with a finite set in mathematics.
A set can be implemented as an associative array (partial mapping)
in which the value of each key-value pair is ignored.
 
Given a set S, the [[wp:Power_set|power set]] (or powerset) of S, written P(S), or 2<sup>S</sup>, is the set of all subsets of S.<br />
Line 113 ⟶ 118:
OD
)</lang>
{{out}}
Output:
<pre>
set[1] = ();
Line 158 ⟶ 163:
NEXT i%
= LEFT$(s$) + "}"</lang>
{{out}}
'''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}}
Line 174 ⟶ 179:
& out$(powerset$(.1 2 3 4))
);</lang>
{{out}}
Output:
<pre> 1 2 3 4
, 1 2 3
Line 327 ⟶ 332:
}</lang>
 
{{out}}
Output:
<pre>
{ }
Line 401 ⟶ 406:
</lang>
 
{{out}}
Output:
<pre>
 
<lang>
Red
Green
Line 419 ⟶ 423:
Green,Blue,Yellow
Red,Green,Blue,Yellow
</langpre>
 
An alternative implementation for an arbitrary number of elements:
Line 484 ⟶ 488:
print_power_set ['dog', 'c', 'b', 'a']
</lang>
{{out}}
output
<lang>
> coffee power_set.coffee
Line 519 ⟶ 523:
=={{header|ColdFusion}}==
 
Port from the [[#JavaScript|JavaScript]] version, compatible with ColdFusion 8+ or Railo 3+
compatible with ColdFusion 8+ or Railo 3+
<lang javascript>public array function powerset(required array data)
{
Line 539 ⟶ 544:
var res = powerset([1,2,3,4]);</lang>
 
{{out}}
Outputs:
<pre>["","1","2","1,2","3","1,3","2,3","1,2,3","4","1,4","2,4","1,2,4","3,4","1,3,4","2,3,4","1,2,3,4"]</pre>
 
Line 551 ⟶ 556:
:from-end t
:initial-value '(())))</lang>
{{out}}
Output:
>(power-set '(1 2 3))
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) NIL)
Line 569 ⟶ 574:
(loop for i below (expt 2 (length xs)) collect
(loop for j below i for x in xs if (logbitp j i) collect x)))</lang>
{{out}}
Output:
>(powerset '(1 2 3)
(NIL (1) (2) (1 2) (3) (1 3) (2 3) (1 2 3))
Line 579 ⟶ 584:
(dolist (set pow-set)
(push (cons element set) pow-set)))))</lang>
{{out}}
Output:
>(power-set '(1 2 3))
((1) (1 3) (1 2 3) (1 2) (2) (2 3) (3) NIL)
Line 700 ⟶ 705:
|| I <- lists:seq(0,Max-1)].</lang>
 
{{out}}
Which outputs:
<code>[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3], [4], [1,4], [2,4], [1,2,4], [3,4], [1,3,4], [2,3,4], [1,2,3,4]]</code>
 
Line 770 ⟶ 775:
 
powerset</lang>
{{out}}
Output:
<pre>
$ 4th cxq powerset.4th 1 2 3 4
Line 991 ⟶ 996:
println powerSet(vocalists)</lang>
 
{{out}}
Output:
<pre>[C, S, N, Y]
[[], [C], [S], [N], [Y], [C, S], [C, N], [C, Y], [S, N], [S, Y], [N, Y], [C, S, N], [C, S, Y], [C, N, Y], [S, N, Y], [C, S, N, Y]]</pre>
Line 1,085 ⟶ 1,090:
</lang>
 
{{out}}
Output:
<pre>
[ 3 ]
Line 1,254 ⟶ 1,259:
print(JSON.stringify(res));</lang>
 
{{out}}
Outputs:
<pre>[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]]</pre>
 
Line 1,417 ⟶ 1,422:
powerset(`{a,b,c}')</lang>
 
{{out}}
Output:
<pre>
{{},{a},{a,b},{a,b,c},{a,c},{b},{b,c},{c}}
Line 1,429 ⟶ 1,434:
powerset({1,2,3,4});
</lang>
{{out}}
Output:
<pre>
{{}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4},
Line 1,437 ⟶ 1,442:
 
=={{header|Mathematica}}==
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:
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:
Line 1,639 ⟶ 1,647:
print $powerset->as_string, "\n";</lang>
 
{{out}}
Output:
<pre>Set::Object(Set::Object() Set::Object(1 2 3) Set::Object(1 2) Set::Object(1 3) Set::Object(1) Set::Object(2 3) Set::Object(2) Set::Object(3))</pre>
 
Line 1,645 ⟶ 1,653:
<li><p>'''''Use a simple custom hash-based set type'''''</p>
 
It's also easy to define a custom type for sets of strings or numbers, using a hash as the underlying representation (like the task description suggests):
using a hash as the underlying representation (like the task description suggests):
 
<lang perl>package Set {
Line 1,672 ⟶ 1,681:
print $_->as_string, "\n" for @subsets;</lang>
 
{{out}}
Output:
<pre>
Set()
Line 1,703 ⟶ 1,712:
 
Usage & output:
 
<lang perl>my @set = (1, 2, 3);
my @powerset = powerset(@set);
Line 1,862 ⟶ 1,870:
?>
</lang>
{{out}}
Output in browser:
<lang>
POWER SET of []
Line 1,963 ⟶ 1,971:
 
End;</lang>
{{out}}
'''output'''
<pre>{}
{one}
Line 1,989 ⟶ 1,997:
The predicate subseq(X,Y) is true if and only if the list X is a subsequence of the list Y.
 
The definitions here are elementary, logical (cut-free), and efficient (within the class of comparably generic implementations).
and efficient (within the class of comparably generic implementations).
<lang Prolog>powerset(X,Y) :- bagof( S, subseq(S,X), Y).
 
Line 1,997 ⟶ 2,006:
subseq( [X|Xs], [_|Ys] ) :- append(_, [X|Zs], Ys), subseq(Xs, Zs).
</lang>
{{out}}
Output :
<pre>?- powerset([1,2,3], X).
X = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]].
Line 2,016 ⟶ 2,025:
maplist( append([X]), PS1, PS2 ), % i.e. prepend X to each PS1
append(PS1, PS2, PS).</lang>
{{out}}
Output :
<pre>?- power_set([1,2,3,4,5,6,7,8], X), length(X,N), writeln(N).
256
Line 2,043 ⟶ 2,052:
empty_element @ chr_power_set([], _) <=> chr_power_set([]).
</lang>
{{out}}
Example of output :
<pre> ?- chr_power_set([1,2,3,4], []), findall(L, find_chr_constraint(chr_power_set(L)), LL), clean.
LL = [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,4],[1,3],[1,3,4],[1,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4],[]] .
Line 2,076 ⟶ 2,085:
EndIf</lang>
<!-- Output modified with a line break to avoid being too long -->
{{out}}
Sample output
<pre>C:\Users\PureBasic_User\Desktop>"Power Set.exe" 1 2 3 4
{{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4},
Line 2,105 ⟶ 2,114:
<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.
 
{{out|Example:}}
<pre>
>>> list_powerset([1,2,3])
Line 2,112 ⟶ 2,121:
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
Line 2,124 ⟶ 2,134:
print "\npowersetlist(%r) =\n %r" % (s, powersetlist(s))</lang>
 
{{out}}
Sample output:
<pre>r: [[]] e: 0
r: [[], [0]] e: 1
Line 2,237 ⟶ 2,247:
</lang>
 
The list "temp" is a compromise between the speed costs of doing
The list "temp" is a compromise between the speed costs of doing arithmetic and of creating new lists (since R lists are immutable, appending to a list means actually creating a new list object). Thus, "temp" collects new subsets that are later added to the power set. This improves the speed by 4x compared to extending the list "ps" at every step.
arithmetic and of creating new lists (since R lists are immutable,
appending to a list means actually creating a new list object).
Thus, "temp" collects new subsets that are later added to the power set.
This improves the speed by 4x compared to extending the list "ps" at every step.
 
===Recursive version===
{{libheader|sets}}
The sets package includes a recursive method to calculate the power set. However, this method takes ~100 times longer than the non-recursive method above.
However, this method takes ~100 times longer than the non-recursive method above.
<lang R>library(sets)</lang>
An example with a vector.
Line 2,264 ⟶ 2,279:
(λ(inner-set) (set-add inner-set element)))))))
</lang>
 
 
 
=={{header|Rascal}}==
Line 2,273 ⟶ 2,286:
public set[set[&T]] PowerSet(set[&T] s) = power(s);
</lang>
{{out}}
An example output:
<lang rascal>
rascal>PowerSet({1,2,3,4})
Line 2,326 ⟶ 2,339:
end /*u*/
return 0</lang>
'''output'''{{out}} when using the default input:
<pre style="overflow:scroll">
1 {}
Line 2,348 ⟶ 2,361:
=={{header|Ruby}}==
<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.
This was intended to show the reader how the method works.
class Array
# Adds a power_set method to every array, i.e.: [1, 2].power_set
Line 2,459 ⟶ 2,473:
</lang>
 
The output will be the dataset SUBSETS and will have a 5 columns F1, F2, F3, F4, F5 and 32 columns, one with each combination of 1 and missing values.
and will have a 5 columns F1, F2, F3, F4, F5 and 32 columns,
one with each combination of 1 and missing values.
 
{{out}}
Output:
<pre>
Obs F1 F2 F3 F4 F5 RowCount
Line 2,499 ⟶ 2,515:
 
=={{header|Scala}}==
[[Category:Scala Implementations]]<lang scala>import scala.compat.Platform.currentTime
 
object Powerset extends App {
Line 2,525 ⟶ 2,541:
(display (power-set (list "A" "C" "E")))
(newline)</lang>
{{out}}
Output:
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())
((A C E) (A C) (A E) (A) (C E) (C) (E) ())
Line 2,551 ⟶ 2,567:
(display a)
(newline)
(loop (x)))))</lang>output<lang>(1 2)
{{out}}
<pre>(1 2)
(1 3)
(1)
Line 2,557 ⟶ 2,575:
(2)
(3)
()</langpre>
 
Iterative:<lang scheme>
Line 2,567 ⟶ 2,585:
</lang>
 
{{out}}
Output:<lang output>
<pre>
'((e d c b a)
(e d c b)
Line 2,600 ⟶ 2,619:
(a)
())
</langpre>
 
=={{header|Seed7}}==
Line 2,633 ⟶ 2,652:
end func;</lang>
 
{{out}}
Output:
<pre>
{}
Line 2,685 ⟶ 2,704:
}
puts [subsets {a b c d}]</lang>
{{out}}
Output:
<pre>{} a b {a b} c {a c} {b c} {a b c} d {a d} {b d} {a b d} {c d} {a c d} {b c d} {a b c d}</pre>
===Binary Count Method===
Line 2,724 ⟶ 2,743:
@ (end)
@(end)</lang>
{{out}}
 
<pre>$ txr rosetta/power-set.txr 1 2 3
{1, 2, 3}
Line 2,735 ⟶ 2,754:
{}</pre>
 
What is not obvious is that the above <code>power-set</code> function generalizes to strings and vectors.
generalizes to strings and vectors.
 
<lang txr>@(do (defun power-set (s)
Line 2,789 ⟶ 2,809:
 
Sets are a built in type constructor in Ursala, represented as
lexically sorted lists with duplicates removed. The powerset function
The powerset function is a standard library function, but could be defined as shown
but could be defined as shown below.
below.
<lang Ursala>powerset = ~&NiC+ ~&i&& ~&at^?\~&aNC ~&ahPfatPRXlNrCDrT</lang>
test program:
Line 2,797 ⟶ 2,817:
 
test = powerset {'a','b','c','d'}</lang>
{{out}}
output:
<pre>{
{},
Line 2,842 ⟶ 2,862:
}
</pre>
{{out}}
<pre>
L(L()) Size = 1
Line 2,850 ⟶ 2,871:
L(3,4),L(1,2,3),L(1,2,4),L(1,3,4),L(2,3,4),L(1,2,3,4)) Size = 16
</pre>
 
 
{{omit from|GUISS}}
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/74379"