Power set: Difference between revisions
m
→{{header|Fōrmulæ}}
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
(17 intermediate revisions by 8 users not shown) | |||
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).
<syntaxhighlight lang="bbcbasic"> DIM list$(3) : list$() = "1", "2", "3", "4"
Line 1,641 ⟶ 1,642:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Power_set}}
'''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}}==
Line 2,205 ⟶ 2,232:
=={{header|Julia}}==
<syntaxhighlight lang="julia">
function powerset
result = Vector{T}[[]]
for elem in x, j in eachindex(result)
Line 2,217 ⟶ 2,244:
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>
Line 2,292 ⟶ 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}}==
Line 2,749 ⟶ 2,837:
<syntaxhighlight lang="perl">use strict;
use warnings;
sub powerset :prototype(&@) {
my $callback = shift;
my $bitmask = '';
Line 3,556 ⟶ 3,644:
=={{header|REXX}}==
<syntaxhighlight lang="rexx">/*REXX program displays a power set; items may be anything (but can't have blanks).*/
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,633 ⟶ 3,742:
<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>
Line 3,686 ⟶ 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}}==
Line 4,479 ⟶ 4,623:
We therefore use lists to represent sets which works fine here.
<syntaxhighlight lang="
var sets = [ [1, 2, 3, 4], [], [[]] ]
|