Rosetta Code

Combinations: Difference between revisions

Page Discussion

Combinations (view source)

Revision as of 08:19, 3 January 2024

7,793 bytes added ,  4 months ago
m
no edit summary
imported>Lacika7
mNo edit summary
 
(16 intermediate revisions by 12 users not shown)
Line 128:
2 4 5
3 4 5
</pre>
 
=={{header|Acornsoft Lisp}}==
{{trans|Emacs Lisp}}
 
<syntaxhighlight lang="lisp">
(defun comb (m n (i . 0))
(cond ((zerop m) '(()))
((eq i n) '())
(t (append
(mapc '(lambda (rest) (cons i rest))
(comb (sub1 m) n (add1 i)))
(comb m n (add1 i))))))
 
(defun append (a b)
(cond ((null a) b)
(t (cons (car a) (append (cdr a) b)))))
 
(map print (comb 3 5))
</syntaxhighlight>
 
{{Out}}
 
<pre>
(0 1 2)
(0 1 3)
(0 1 4)
(0 2 3)
(0 2 4)
(0 3 4)
(1 2 3)
(1 2 4)
(1 3 4)
(2 3 4)
</pre>
 
Line 523 ⟶ 557:
1 3 4
2 3 4</pre>
 
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">print.lines combine.by:3 @0..4</syntaxhighlight>
 
{{out}}
 
<pre>[0 1 2]
[0 1 3]
[0 1 4]
[0 2 3]
[0 2 4]
[0 3 4]
[1 2 3]
[1 2 4]
[1 3 4]
[2 3 4]</pre>
 
=={{header|AutoHotkey}}==
Line 610 ⟶ 660:
3 4 5
</pre>
 
=={{header|BASIC}}==
==={{header|BASIC256}}===
<syntaxhighlight lang="vb">input "Enter n comb m. ", n
input m
 
outstr$ = ""
call iterate (outstr$, 0, m-1, n-1)
end
 
subroutine iterate (curr$, start, stp, depth)
for i = start to stp
if depth = 0 then print curr$ + " " + string(i)
call iterate (curr$ + " " + string(i), i+1, stp, depth-1)
next i
end subroutine</syntaxhighlight>
{{out}}
<pre>Enter n comb m. 3
5
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4</pre>
 
==={{header|IS-BASIC}}===
<syntaxhighlight lang="is-basic">100 PROGRAM "Combinat.bas"
110 LET MMAX=3:LET NMAX=5
120 NUMERIC COMB(0 TO MMAX)
130 CALL GENERATE(1)
140 DEF GENERATE(M)
150 NUMERIC N,I
160 IF M>MMAX THEN
170 FOR I=1 TO MMAX
180 PRINT COMB(I);
190 NEXT
200 PRINT
220 ELSE
230 FOR N=0 TO NMAX-1
240 IF M=1 OR N>COMB(M-1) THEN
250 LET COMB(M)=N
260 CALL GENERATE(M+1)
270 END IF
280 NEXT
290 END IF
300 END DEF</syntaxhighlight>
 
==={{header|QBasic}}===
{{works with|QBasic|1.1}}
{{works with|QuickBasic|4.5}}
<syntaxhighlight lang="qbasic">SUB iterate (curr$, start, stp, depth)
FOR i = start TO stp
IF depth = 0 THEN PRINT curr$ + " " + STR$(i)
CALL iterate(curr$ + " " + STR$(i), i + 1, stp, depth - 1)
NEXT i
END SUB
 
INPUT "Enter n comb m. ", n, m
 
outstr$ = ""
CALL iterate(outstr$, 0, m - 1, n - 1)
END</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
 
==={{header|Run BASIC}}===
<syntaxhighlight lang="vb">sub iterate curr$, start, stp, depth
for i = start to stp
if depth = 0 then print curr$ + " " + str$(i)
call iterate curr$ + " " + str$(i), i+1, stp, depth-1
next i
end sub
 
input "Enter n comb m. "; n, m
outstr$ = ""
call iterate outstr$, 0, m-1, n-1
end</syntaxhighlight>
 
==={{header|XBasic}}===
{{works with|Windows XBasic}}
<syntaxhighlight lang="qbasic">PROGRAM "Combinations"
VERSION "0.0000"
 
DECLARE FUNCTION Entry ()
DECLARE FUNCTION iterate (curr$, start, stp, depth)
 
FUNCTION Entry ()
n = 3
m = 5
outstr$ = ""
iterate(outstr$, 0, m - 1, n - 1)
 
END FUNCTION
 
FUNCTION iterate (curr$, start, stp, depth)
FOR i = start TO stp
IF depth = 0 THEN PRINT curr$ + " " + STR$(i)
iterate(curr$ + " " + STR$(i), i + 1, stp, depth - 1)
NEXT i
RETURN
END FUNCTION
END PROGRAM</syntaxhighlight>
 
=={{header|BBC BASIC}}==
Line 1,462 ⟶ 1,619:
len result[] m
#
funcproc combinations pos val . .
if pos <= m
for i = val to n - m
result[pos] = pos + i
call combinations pos + 1 i
.
else
print result[]
.
.
call combinations 1 0
</syntaxhighlight>
{{out}}
Line 1,682 ⟶ 1,839:
 
=={{header|Elena}}==
ELENA 46.x :
<syntaxhighlight lang="elena">import system'routines;
import extensions;
Line 1,692 ⟶ 1,849:
Numbers(n)
{
^ Array.allocate(n).populate::(int n => n)
}
 
Line 1,698 ⟶ 1,855:
{
var numbers := Numbers(N);
Combinator.new(M, numbers).forEach::(row)
{
console.printLine(row.toString())
Line 2,383 ⟶ 2,540:
[ 1 3 4 ]
[ 2 3 4 ]</pre>
 
=={{header|IS-BASIC}}==
<syntaxhighlight lang="is-basic">100 PROGRAM "Combinat.bas"
110 LET MMAX=3:LET NMAX=5
120 NUMERIC COMB(0 TO MMAX)
130 CALL GENERATE(1)
140 DEF GENERATE(M)
150 NUMERIC N,I
160 IF M>MMAX THEN
170 FOR I=1 TO MMAX
180 PRINT COMB(I);
190 NEXT
200 PRINT
220 ELSE
230 FOR N=0 TO NMAX-1
240 IF M=1 OR N>COMB(M-1) THEN
250 LET COMB(M)=N
260 CALL GENERATE(M+1)
270 END IF
280 NEXT
290 END IF
300 END DEF</syntaxhighlight>
 
=={{header|J}}==
Line 2,931 ⟶ 3,066:
<syntaxhighlight lang="julia">
using Base.Iterators
function combinations(x::Vector{T}, size::Int)::Vector{Vector{T}} where T
# Iterators.filter(flt, itr) takes a function flt, and an iterator itr, and returns
# a new (lazy) iterator which passes elements for which flt returns true.
size_filter(x) = Iterators.filter(y -> count_ones(y) == size, x)
 
function bitmask(u, max_size)
# Iterators.map(f, x) takes a function f and an iterable x, and returns
res = BitArray(undef, max_size)
# a new (lazy) iterator which applies the function f to the elements of x.
res.chunks[1] = u%UInt64
bitstring_map(x) = Iterators.map(bitstring, x)
res
reverse_map(x) = Iterators.map(reverse, x)
end
 
function combinations(input_collection::Vector{T}, choice_size::Int)::Vector{Vector{T}} where T
num_elements = length(input_collection)
size_filter(x) = Iterators.filter(y -> count_ones(y) == choice_size, x)
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) |>
# |> is a function pipe. The return value of the function before the pipe
size_filter |>
# becomes the input value of the function after the pipe.
bitmask_map |>
bit_strings = range(stop=2^length(x)-1) |>
size_filtergetindex_map |>
bitstring_map |>collect
reverse_map
# At this point, bit_strings is still a lazy iterator. It isn't until we
# collect the results into this array comprehension that the calculations
# are performed.
[[a for (a, b) in zip(x, bits) if b == '1'] for bits in bit_strings]
end
</syntaxhighlight>
Line 3,775 ⟶ 3,908:
{2,4,5}
{3,4,5}
</pre>
As of 1.0.2 there is a builtin combinations() function. Using a string here for simplicity and neater output, but it works with any sequence:
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">combinations</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"12345"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">),</span><span style="color: #008000;">','</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
"123,124,125,134,135,145,234,235,245,345"
</pre>
 
Line 4,502 ⟶ 4,643:
 
=={{header|REXX}}==
===Version 1===
This REXX program supports up to &nbsp; 100 &nbsp; symbols &nbsp; (one symbol for each "thing").
 
Line 4,507 ⟶ 4,649:
 
The symbol list could be extended by added any unique viewable symbol &nbsp; (character).
<syntaxhighlight lang="rexx">/*REXX program displays combination sets for X things taken Y at a time. */
parseParse argArg xthings ysize $chars . /* get optional arguments from the C.L.command line */
If things='?' Then Do
if x=='' | x=="," then x= 5 /*No X specified? Then use default.*/
Say 'rexx combi things size characters'
if y=='' | y=="," then y= 3; oy= y; y= abs(y) /* " Y " " " " */
Say ' defaults: 5 3 123456789...'
if $=='' | $=="," then $='123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ',
Say 'example rexx combi , , xyzuvw'
"~!@#$%^&*()_+`{}|[]\:;<>?,./█┌┐└┘±≥≤≈∙" /*some extended chars*/
Say 'size<0 shows only the number of possible combinations'
/* [↑] No $ specified? Use default.*/
Exit
if y>x then do; say y " can't be greater than " x; exit 1; end
End
say "────────────" x ' things taken ' y " at a time:"
If things==''|things=="," Then things=5 /* No things specified? Then use default*/
say "────────────" combN(x,y) ' combinations.'
If size=='' |size=="," Then size=3 /* No size specified? Then use default*/
exit /*stick a fork in it, we're all done. */
If chars==''|chars=="," Then /* No chars specified? Then Use default*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
chars='123456789abcdefghijklmnopqrstuvwxyz'||,
combN: procedure expose $ oy; parse arg x,y; xp= x+1; xm= xp-y; !.= 0
'ABCDEFGHIJKLMNOPQRSTUVWXYZ'||,
if x=0 | y=0 then return 'no'
"~!@#chars%^&*()_+`{}|[]\:;<>?,./¦++++±==˜·" /*some extended chars */
do i=1 for y; !.i= i
 
end /*i*/
show_details=sign(size) do/* j=-1;: Don't L=show details */
size=abs(size)
do d=1 for y; L= L substr($, !.d, 1)
If things<size Then
end /*d*/
Call exit 'Not enough things ('things') for size ('size').'
if oy>0 then say L; !.y= !.y + 1 /*don't show if OY<0 */
Say '------------' things 'things taken' size 'times at a time:'
if !.y==xp then if .combN(y-1) then leave
Say '------------' combn(things,size) 'combinations.'
end /*j*/
Exit /* stick a fork in it, we're all */
return j
/*-------------------------------------------------------------------------------*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
combn: Procedure Expose chars show_details
.combN: procedure expose !. y xm; parse arg d; if d==0 then return 1; p= !.d
Parse Arg things,size
do u=d to y; !.u= p+1; if !.u==xm+u then return .combN(u-1); p= !.u
thingsp=things+1
end /*u*/ /* ↑ */
thingsm=thingsp-size
return 0 /*recursive call──►──────┘ */</syntaxhighlight>
index.=0
If things=0|size=0 Then
Return 'no'
Do i=1 For size
index.i=i
End
done=0
Do combi=1 By 1 Until done
combination=''
Do d=1 To size
combination=combination substr(chars,index.d,1)
End
If show_details=1 Then
Say combination
index.size=index.size+1
If index.size==thingsp Then
done=.combn(size-1)
End
Return combi
/*---------------------------------------------------------------------------------*/
.combn: Procedure Expose index. size thingsm
Parse Arg d
--Say '.combn' d thingsm show()
If d==0 Then
Return 1
p=index.d
Do u=d To size
index.u=p+1
If index.u==thingsm+u Then
Return .combn(u-1)
p=index.u
End
Return 0
 
show:
list=''
Do k=1 To size
list=list index.k
End
Return list
 
exit:
Say '*****error*****' arg(1)
Exit 13
</syntaxhighlight>
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 5 &nbsp; 3 &nbsp; 01234 </tt>}}
<pre>
────────────------------ 5 things taken 3 at a time:
0 1 2
0 1 3
Line 4,548 ⟶ 4,735:
1 3 4
2 3 4
────────────------------ 10 combinations.
</pre>
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 5 &nbsp; 3 &nbsp; abcde </tt>}}
<pre>
────────────------------ 5 things taken 3 at a time:
a b c
a b d
Line 4,563 ⟶ 4,750:
b d e
c d e
────────────------------ 10 combinations.
</pre>
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 44 &nbsp; 0 </tt>}}
<pre>
────────────------------ 44 things taken 0 at a time:
────────────------------ no combinations.
</pre>
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 52 &nbsp; -5 </tt>}}
<pre>
────────────------------ 52 things taken 5 at a time:
────────────------------ 2598960 combinations.
</pre>
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 5 &nbsp; -8 </tt>}}
<pre>
*****error***** Not enough things (5) for size (8).
</pre>
===Version 2===
{{trans|Java}}
<syntaxhighlight lang="rexx">/*REXX program displays combination sets for X things taken Y at a time. */
Parse Arg things size characters
If things='?' Then Do
Say 'rexx combi2 things size characters'
Say ' defaults: 5 3 123456789...'
Say 'example rexx combi2 , , xyzuvw'
Say 'size<0 shows only the number of possible combinations'
Exit
End
If things==''|things=="," Then things=5 /* No things specified? Then use default*/
If size=='' |size=="," Then size=3 /* No size specified? Then use default*/
Numeric Digits 20
show=sign(size)
size=abs(size)
If things<size Then
Call exit 'Not enough things ('things') for size ('size').' Say '----------' things 'things taken' size 'at a time:'
n=2**things-1
nc=0
Do u=1 to n
nc=nc+combinations(u)
End
Say '------------' nc 'combinations.'
Exit
combinations: Procedure Expose things size characters show
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
If characters<>'' then
c=substr(characters,i,1)
Else
c=i
If substr(ub,i,1)=1 Then res=res c
End
If show=1 then
Say res
Return 1
End
Else
Return 0
exit:
Say '*****error*****' arg(1)
Exit 13 </syntaxhighlight>
 
=={{header|Ring}}==
Line 4,663 ⟶ 4,903:
[2 4 5]
[3 4 5]
</pre>
 
=={{header|RPL}}==
{{trans|BASIC}}
{{works with|HP|48SX}}
≪ → currcomb start stop depth
≪ '''WHILE''' start stop ≤ '''REPEAT'''
currcomb start +
1 'start' STO+
'''IF''' depth '''THEN'''
start stop depth 1 - <span style="color:blue">GENCOMB</span> '''END'''
'''END'''
≫ ≫ '<span style="color:blue">GENCOMB</span>' STO
≪
{ } 0 4 ROLL 1 - 4 ROLL 1 - <span style="color:blue">GENCOMB</span>
≫ '<span style="color:blue">COMBS</span>' STO
 
5 3 <span style="color:blue">COMBS</span>
{{out}}
<pre>
10: { 0 1 2 }
9: { 0 1 3 }
8: { 0 1 4 }
7: { 0 2 3 }
6: { 0 2 4 }
5: { 0 3 4 }
4: { 1 2 3 }
3: { 1 2 4 }
2: { 1 3 4 }
1: { 2 3 4 }
</pre>
 
Line 5,037 ⟶ 5,308:
[http://fricas.github.io/api/SymmetricGroupCombinatoricFunctions.html?highlight=choose SGCF]
==> SymmetricGroupCombinatoricFunctions
 
=={{header|SparForte}}==
As a structured script.
<syntaxhighlight lang="ada">#!/usr/local/bin/spar
pragma annotate( summary, "combinations" )
@( description, "Given non-negative integers m and n, generate all size m" )
@( description, "combinations of the integers from 0 to n-1 in sorted" )
@( description, "order (each combination is sorted and the entire table" )
@( description, "is sorted" )
@( see_also, "http://rosettacode.org/wiki/Combinations" )
@( author, "Ken O. Burtch" );
 
pragma restriction( no_external_commands );
 
procedure combinations is
number_of_items : constant natural := 3;
max_item_value : constant natural := 5;
 
-- get_first_combination
-- return the first combination (e.g. 0,1,2 for 3 items)
 
function get_first_combination return string is
c : string;
begin
for i in 1..number_of_items loop
c := @ & strings.image( natural( i-1 ) );
end loop;
return c;
end get_first_combination;
 
-- get_last_combination
-- return the highest value (e.g. 4,4,4 for 3 items
-- with a maximum value of 5).
 
function get_last_combination return string is
c : string;
begin
for i in 1..number_of_items loop
c := @ & strings.image( max_item_value-1 );
end loop;
return c;
end get_last_combination;
 
combination : string := get_first_combination;
last_combination : constant string := get_last_combination;
 
item : natural; -- a number from the combination
bad : boolean; -- true if we know a value is too big
s : string; -- a temp string for deleting leading space
 
begin
put_line( combination );
while combination /= last_combination loop
 
-- the combination is 3 numbers with leading spaces
-- so the field positions start at 2 (1 is a null string)
 
for i in reverse 1..number_of_items loop
item := numerics.value( strings.field( combination, i+1, ' ') );
if item < max_item_value-1 then
item := @+1;
s := strings.image( item );
s := strings.delete( s, 1, 1 );
strings.replace( combination, i+1, s, ' ' );
bad := false;
for j in i+1..number_of_items loop
item := numerics.value( strings.field( combination, j, ' ') );
if item < max_item_value-1 then
item := @+1;
s := strings.image( item );
s := strings.delete( s, 1, 1 );
strings.replace( combination, j+1, s, ' ' );
else
bad;
end if;
end loop;
exit;
end if;
end loop;
if not bad then
put_line( combination );
end if;
end loop;
end combinations;</syntaxhighlight>
 
=={{header|Standard ML}}==
Line 5,178 ⟶ 5,533:
<pre>$ txr combinations.tl
3 comb 5 = ((0 1 2) (0 1 3) (0 1 4) (0 2 3) (0 2 4) (0 3 4) (1 2 4) (1 3 4) (2 3 4))</pre>
 
=={{header|uBasic/4tH}}==
{{Trans|C}}
<syntaxhighlight lang="qbasic">o = 1
Proc _Comb(5, 3, 0, 0)
End
 
_Comb
Param (4)
If a@ < b@ + d@ Then Return
 
If b@ = 0 Then
For d@ = 0 To a@-1
If AND(c@, SHL(o, d@)) Then Print d@;" "; : Fi
Next
Print : Return
EndIf
 
Proc _Comb(a@, b@ - 1, OR(c@, SHL(o, d@)), d@ + 1)
Proc _Comb(a@, b@, c@, d@ + 1)
Return</syntaxhighlight>
{{Out}}
<pre>0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
 
0 OK, 0:33</pre>
 
=={{header|Ursala}}==
Line 5,417 ⟶ 5,807:
=={{header|Wren}}==
{{libheader|Wren-perm}}
<syntaxhighlight lang="ecmascriptwren">import "./perm" for Comb
 
var fib = Fiber.new { Comb.generate((0..4).toList, 3) }
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/335374...348688"