Anonymous user
Combinations: Difference between revisions
m
no edit summary
imported>Lacika7 mNo edit summary |
|||
(52 intermediate revisions by 28 users not shown) | |||
Line 28:
=={{header|11l}}==
{{trans|D}}
<
I k == 0
R [[Int]()]
Line 40:
R result
print(comb([0, 1, 2, 3, 4], 3))</
{{out}}
<pre>
Line 52:
For maximum compatibility, this program uses only the basic instruction set (S/360)
and two ASSIST macros (XDECO, XPRNT) to keep the code as short as possible.
<
COMBINE CSECT
USING COMBINE,R13 base register
Line 115:
PG DC CL92' ' buffer
YREGS
END COMBINE</
{{out}}
<pre>
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>
=={{header|Action!}}==
<syntaxhighlight lang="action!">PROC PrintComb(BYTE ARRAY c BYTE len)
BYTE i
Put('()
FOR i=0 TO len-1
DO
IF i>0 THEN Put(',) FI
PrintB(c(i))
OD
Put(')) PutE()
RETURN
BYTE FUNC Increasing(BYTE ARRAY c BYTE len)
BYTE i
IF len<2 THEN RETURN (1) FI
FOR i=0 TO len-2
DO
IF c(i)>=c(i+1) THEN
RETURN (0)
FI
OD
RETURN (1)
BYTE FUNC NextComb(BYTE ARRAY c BYTE n,k)
INT pos,i
DO
pos=k-1
DO
c(pos)==+1
IF c(pos)<n THEN
EXIT
ELSE
pos==-1
IF pos<0 THEN RETURN (0) FI
FI
FOR i=pos+1 TO k-1
DO
c(i)=c(pos)
OD
OD
UNTIL Increasing(c,k)
OD
RETURN (1)
PROC Comb(BYTE n,k)
BYTE ARRAY c(10)
BYTE i
IF k>n THEN
Print("Error! k is greater than n.")
Break()
FI
FOR i=0 TO k-1
DO
c(i)=i
OD
DO
PrintComb(c,k)
UNTIL NextComb(c,n,k)=0
OD
RETURN
PROC Main()
Comb(5,3)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Combinations.png Screenshot from Atari 8-bit computer]
<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|Ada}}==
<
procedure Test_Combinations is
Line 186 ⟶ 306:
when Constraint_Error =>
null;
end Test_Combinations;</
The solution is generic the formal parameter is the integer type to make combinations of. The type range determines ''n''.
In the example it is
<
The parameter ''m'' is the object's constraint.
When ''n'' < ''m'' the procedure First (selects the first combination) will propagate Constraint_Error.
Line 213 ⟶ 333:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.6 algol68g-2.6].}}
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}
'''File: prelude_combinations.a68'''<
COMMENT REQUIRED BY "prelude_combinations_generative.a68"
Line 244 ⟶ 364:
);
SKIP</
# -*- coding: utf-8 -*- #
Line 265 ⟶ 385:
# OD # ))
)
</syntaxhighlight>
{{out}}
<pre>
Line 284 ⟶ 404:
===Iteration===
<
set c to {}
repeat with i from 1 to k
Line 310 ⟶ 430:
end next_comb
return comb(5, 3)</
{{out}}
<
===Functional composition===
{{Trans|JavaScript}}
<syntaxhighlight lang="applescript">----------------------- COMBINATIONS ---------------------
-- comb :: Int -> [a] -> [[a]]
on comb(n, lst)
if
{{}}
else
Line 324 ⟶ 446:
set {h, xs} to uncons(lst)
map(
comb(n - 1, xs)) & comb(n, xs)
else
{}
Line 331 ⟶ 454:
end comb
on run
Line 339 ⟶ 462:
end run
-- cons :: a -> [a] -> [a]
on cons(x
script
on |λ|(
end |λ|
end script
end
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if
set
repeat with i from m to n
set end of lst to i
end repeat
lst
else
end if
end enumFromTo
Line 432 ⟶ 545:
on unwords(xs)
intercalate(space, xs)
end unwords</
{{Out}}
<pre>0 1 2
Line 444 ⟶ 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}}==
contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276224.html#276224 forum]
<
MsgBox % Comb(3,3)
MsgBox % Comb(3,2)
Line 472 ⟶ 601:
c%j% += 1
}
}</
=={{header|AWK}}==
<
## Default values for r and n (Choose 3 from pool of 5). Can
## alternatively be set on the command line:-
Line 511 ⟶ 640:
if (i < r) printf A[i] OFS
else print A[i]}}
exit}</
Usage:
Line 531 ⟶ 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}}==
{{works with|BBC BASIC for Windows}}
<
sort% = FN_sortinit(0,0)
Line 579 ⟶ 815:
DEF FNfact(N%)
IF N%<=1 THEN = 1 ELSE = N%*FNfact(N%-1)
</syntaxhighlight>
=={{header|BQN}}==
<syntaxhighlight lang="bqn">Cmat←{⊑𝕨∊0‿𝕩?≍↕𝕨;0⊸∾˘⊸∾´1+(𝕨-1‿0)𝕊¨𝕩-1} # Recursive
Cmat1←{k←⌽↕d←𝕩¬𝕨⋄∾⌽{k∾˘¨∾˜`1+𝕩}⍟𝕨d↑↓1‿0⥊0} # Roger Hui</syntaxhighlight>
<syntaxhighlight lang="text">┌─
╵ 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
┘</syntaxhighlight>
=={{header|Bracmat}}==
The program first constructs a pattern with <code>m</code> variables and an expression that evaluates <code>m</code> variables into a combination.
Line 587 ⟶ 838:
When all combinations are found, the pattern fails and we are in the rhs of the last <code>|</code> operator.
<
bvar combination combinations list m n pat pvar var
. !arg:(?m.?n)
Line 610 ⟶ 861:
' (!n+-1:~<0:?n&!n !list:?list)
& !list:!pat
| !combinations);</
comb$(3.5)
Line 626 ⟶ 877:
=={{header|C}}==
<
/* Type marker stick: using bits to indicate what's chosen. The stick can't
Line 654 ⟶ 905:
comb(5, 3, 0, 0);
return 0;
}</
===Lexicographic ordered generation===
Without recursions, generate all combinations in sequence. Basic logic: put n items in the first n of m slots; each step, if right most slot can be moved one slot further right, do so; otherwise
find right most item that can be moved, move it one step and put all items already to its right next to it.
<
void comb(int m, int n, unsigned char *c)
Line 685 ⟶ 936:
comb(5, 3, buf);
return 0;
}</
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
Line 726 ⟶ 977:
}
}
}</
Here is another implementation that uses recursion, intead of an explicit stack:
<
using System;
using System.Collections.Generic;
Line 767 ⟶ 1,018:
}
}
</syntaxhighlight>
Line 773 ⟶ 1,024:
Recursive version
<
class Combinations
{
Line 793 ⟶ 1,044:
}
}
}</
=={{header|C++}}==
<
#include <iostream>
#include <string>
Line 818 ⟶ 1,069:
{
comb(5, 3);
}</
{{out}}
<pre>
Line 834 ⟶ 1,085:
=={{header|Clojure}}==
<
"If m=1, generate a nested list of numbers [0,n)
If m>1, for each x in [0,n), and for each list in the recursion on [x+1,n), cons the two"
Line 853 ⟶ 1,104:
(doseq [n line]
(printf "%s " n))
(printf "%n")))</
The below code do not comply to the task described above. However, the combinations of n elements taken from m elements might be more natural to be expressed as a set of unordered sets of elements in Clojure using its Set data structure.
<
(defn combinations
"Generate the combinations of n elements from a list of [0..m)"
Line 869 ⟶ 1,120:
:when (not-any? #{x} r)]
(conj r x))))))))
</syntaxhighlight>
=={{header|CLU}}==
<syntaxhighlight lang="clu">% generate the size-M combinations from 0 to n-1
combinations = iter (m, n: int) yields (sequence[int])
if m<=n then
state: array[int] := array[int]$predict(1, m)
for i: int in int$from_to(0, m-1) do
array[int]$addh(state, i)
end
i: int := m
while i>0 do
yield (sequence[int]$a2s(state))
i := m
while i>0 do
state[i] := state[i] + 1
for j: int in int$from_to(i,m-1) do
state[j+1] := state[j] + 1
end
if state[i] < n-(m-i) then break end
i := i - 1
end
end
end
end combinations
% print a combination
print_comb = proc (s: stream, comb: sequence[int])
for i: int in sequence[int]$elements(comb) do
stream$puts(s, int$unparse(i) || " ")
end
end print_comb
start_up = proc ()
po: stream := stream$primary_output()
for comb: sequence[int] in combinations(3, 5) do
print_comb(po, comb)
stream$putl(po, "")
end
end start_up</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|CoffeeScript}}==
Basic backtracking solution.
<
combinations = (n, p) ->
return [ [] ] if p == 0
Line 900 ⟶ 1,202:
console.log combo
</syntaxhighlight>
{{out}}
Line 946 ⟶ 1,248:
=={{header|Common Lisp}}==
<
"Call fn with each m combination of the integers from 0 to n-1 as a list. The list may be destroyed after fn returns."
(let ((combination (make-list m)))
Line 963 ⟶ 1,265:
(mc (1+ curr) (1- left) (1- needed) (rest comb-tail))
(mc (1+ curr) (1- left) needed comb-tail)))))
(mc 0 n m combination))))</
{{out}}Example use
Line 981 ⟶ 1,283:
=== Recursive method ===
<
(labels ((comb1 (l c m)
(when (>= (length l) m)
Line 989 ⟶ 1,291:
(comb1 list nil m)))
(comb 3 '(0 1 2 3 4 5) #'print)</
=== Alternate, iterative method ===
<
(let ((k (length a)) m)
(loop for i from 1 do
Line 1,037 ⟶ 1,339:
(1 2 4 5)
(1 3 4 5)
(2 3 4 5)</
=={{header|Crystal}}==
<syntaxhighlight lang="ruby">
def comb(m, n)
(0...n).to_a.each_combination(m) { |p| puts(p) }
end
</syntaxhighlight>
<syntaxhighlight lang="bash">
[0, 1, 2]
[0, 1, 3]
Line 1,057 ⟶ 1,359:
[1, 3, 4]
[2, 3, 4]
</syntaxhighlight>
=={{header|D}}==
===Slow Recursive Version===
{{trans|Python}}
<
if (k == 0) return [[]];
typeof(return) result;
Line 1,074 ⟶ 1,376:
import std.stdio;
[0, 1, 2, 3].comb(2).writeln;
}</
{{out}}
<pre>[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]</pre>
Line 1,081 ⟶ 1,383:
{{trans|Haskell}}
Same output.
<
immutable(int)[][] comb(immutable int[] s, in int m) pure nothrow @safe {
Line 1,091 ⟶ 1,393:
void main() {
4.iota.array.comb(2).writeln;
}</
===Lazy Version===
<
import std.traits: Unqual;
Line 1,187 ⟶ 1,489:
[1, 2, 3, 4].combinations!true(2).array.writeln;
[1, 2, 3, 4].combinations(2).map!(x => x).writeln;
}</
===Lazy Lexicographical Combinations===
Includes an algorithm to find [http://msdn.microsoft.com/en-us/library/aa289166.aspx#mth_lexicograp_topic3 mth Lexicographical Element of a Combination].
<
import std.stdio, std.algorithm, std.conv;
Line 1,290 ⟶ 1,592:
foreach (c; Comb.On([1, 2, 3], 2))
writeln(c);
}</
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Combinations#Pascal Pascal].
=={{header|E}}==
<
return if (m <=> 0) { [[]] } else {
def combGenerator {
Line 1,305 ⟶ 1,608:
}
}
}</
? for x in combinations(3, 0..4) { println(x) }
Line 1,311 ⟶ 1,614:
=={{header|EasyLang}}==
{{trans|Julia}}
<syntaxhighlight lang="text">
n = 5
m = 3
len result[] m
#
if pos <= m
for i = val to n - m
result[pos] = pos + i
.
else
print result[]
.
.
</syntaxhighlight>
{{out}}
<pre>
[ 1 2 3 ]
[ 1 2 4 ]
[ 1 2 5 ]
[ 1 3 4 ]
[ 1 3 5 ]
[ 1 4 5 ]
[ 2 3 4 ]
[ 2 3 5 ]
[ 2 4 5 ]
[ 3 4 5 ]
</pre>
=={{header|EchoLisp}}==
<
;;
;; using the native (combinations) function
Line 1,367 ⟶ 1,672:
(combine (iota 5) 3)
→ ((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))
</syntaxhighlight>
=={{header|Egison}}==
<
(define $comb
(lambda [$n $xs]
Line 1,378 ⟶ 1,683:
(test (comb 3 (between 0 4)))
</syntaxhighlight>
{{out}}
<pre>
Line 1,386 ⟶ 1,691:
=={{header|Eiffel}}==
The core of the program is the recursive feature solve, which returns all possible strings of length n with k "ones" and n-k "zeros". The strings are then evaluated, each resulting in k corresponding integers for the digits where ones are found.
<syntaxhighlight lang="eiffel">
class
Line 1,502 ⟶ 1,807:
end
</syntaxhighlight>
Test:
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 1,527 ⟶ 1,832:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,534 ⟶ 1,839:
=={{header|Elena}}==
ELENA
<
import extensions;
import extensions'routines;
Line 1,544 ⟶ 1,849:
Numbers(n)
{
^ Array.allocate(n).populate::(int n => n)
}
Line 1,550 ⟶ 1,855:
{
var numbers := Numbers(N);
Combinator.new(M, numbers).forEach::(row)
{
console.printLine(row.toString())
Line 1,556 ⟶ 1,861:
console.readChar()
}</
{{out}}
<pre>
Line 1,573 ⟶ 1,878:
=={{header|Elixir}}==
{{trans|Erlang}}
<
def comb(0, _), do: [[]]
def comb(_, []), do: []
Line 1,583 ⟶ 1,888:
{m, n} = {3, 5}
list = for i <- 1..n, do: i
Enum.each(RC.comb(m, list), fn x -> IO.inspect x end)</
{{out}}
Line 1,601 ⟶ 1,906:
=={{header|Emacs Lisp}}==
{{trans|Haskell}}
<
(cond ((zerop m) '(()))
((= n-max n) '())
Line 1,611 ⟶ 1,916:
(comb-recurse m 0 n))
(comb 3 5)</
{{out}}
Line 1,618 ⟶ 1,923:
=={{header|Erlang}}==
<
-module(comb).
-compile(export_all).
Line 1,628 ⟶ 1,933:
comb(N,[H|T]) ->
[[H|L] || L <- comb(N-1,T)]++comb(N,T).
</syntaxhighlight>
===Dynamic Programming===
Line 1,636 ⟶ 1,941:
Could be optimized with a custom <code>zipwith/3</code> function instead of using <code>lists:sublist/2</code>.
<
-module(comb).
-export([combinations/2]).
Line 1,650 ⟶ 1,955:
lists:zipwith(fun lists:append/2, Step, Next)
end, [[[]]] ++ lists:duplicate(K, []), List).
</syntaxhighlight>
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM COMBINATIONS
Line 1,690 ⟶ 1,995:
GENERATE(1)
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>
Line 1,706 ⟶ 2,011:
=={{header|F_Sharp|F#}}==
<
let rec fC prefix m from = seq {
let rec loopFor f = seq {
Line 1,727 ⟶ 2,032:
choose 3 5
|> Seq.iter (printfn "%A")
0</
{{out}}
<pre>[0; 1; 2]
Line 1,741 ⟶ 2,046:
=={{header|Factor}}==
<
5 iota 3 all-combinations .</
<pre>
{
Line 1,759 ⟶ 2,064:
</pre>
This works with any kind of sequence:
<
<pre>{ { "a" "b" } { "a" "c" } { "b" "c" } }</pre>
=={{header|Fortran}}==
<
use iso_fortran_env
implicit none
Line 1,851 ⟶ 2,156:
end subroutine comb
end program Combinations</
Alternatively:
<
implicit none
Line 1,884 ⟶ 2,189:
end subroutine gen
end program combinations</
{{out}}
<pre>1 2 3
Line 1,896 ⟶ 2,201:
2 4 5
3 4 5</pre>
=={{Header|FreeBASIC}}==
This is remarkably compact and elegant.
<syntaxhighlight lang="freebasic">sub iterate( byval curr as string, byval start as uinteger,_
byval stp as uinteger, byval depth as uinteger )
dim as uinteger i
for i = start to stp
if depth = 0 then
print curr + " " + str(i)
end if
iterate( curr+" "+str(i), i+1, stp, depth-1 )
next i
return
end sub
dim as uinteger m, n
input "Enter n comb m. ", n, m
dim as string outstr = ""
iterate outstr, 0, m-1, n-1</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|GAP}}==
<
Combinations([1 .. n], m);
Combinations([1 .. 5], 3);
# [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 3, 5 ],
# [ 1, 4, 5 ], [ 2, 3, 4 ], [ 2, 3, 5 ], [ 2, 4, 5 ], [ 3, 4, 5 ] ]</
=={{header|Glee}}==
<
$$(5!3) give all combinations of 3 out of 5
$$(>>>) sorted up,
$$(,,\) printed with crlf delimiters.</
Result:
<
1 2 3
1 2 4
Line 1,924 ⟶ 2,261:
2 3 5
2 4 5
3 4 5</
=={{header|Go}}==
<
import (
Line 1,955 ⟶ 2,292:
}
rc(0, 0)
}</
{{out}}
<pre>[0 1 2]
Line 1,973 ⟶ 2,310:
===In General===
A recursive closure must be ''pre-declared''.
<
comb = { m, list ->
def n = list.size()
Line 1,982 ⟶ 2,319:
newlist += comb(m-1, sublist).collect { [list[k]] + it }
}
}</
Test program:
<
println "Choose from ${csny}"
(0..(csny.size())).each { i -> println "Choose ${i}:"; comb(i, csny).each { println it }; println() }</
{{out}}
Line 2,018 ⟶ 2,355:
===Zero-based Integers===
<
Test program:
<
(0..3).each { i -> println "Choose ${i}:"; comb0(i, 5).each { println it }; println() }</
{{out}}
Line 2,061 ⟶ 2,398:
===One-based Integers===
<
Test program:
<
(0..3).each { i -> println "Choose ${i}:"; comb1(i, 5).each { println it }; println() }</
{{out}}
Line 2,108 ⟶ 2,445:
Straightforward, unoptimized implementation with divide-and-conquer:
<
comb 0 _ = [[]]
comb _ [] = []
comb m (x:xs) = map (x:) (comb (m-1) xs) ++ comb m xs</
In the induction step, either ''x'' is not in the result and the recursion proceeds with the rest of the list ''xs'', or it is in the result and then we only need ''m-1'' elements.
Shorter version of the above:
<
comb :: Int -> [a] -> [[a]]
comb 0 _ = [[]]
comb m l = [x:ys | x:xs <- tails l, ys <- comb (m-1) xs]</
To generate combinations of integers between 0 and ''n-1'', use
<
Similar, for integers between 1 and ''n'', use
<
Another method is to use the built in ''Data.List.subsequences'' function, filter for subsequences of length ''m'' and then sort:
<
comb m n = sort . filter ((==m) . length) $ subsequences [0..n-1]</
And yet another way is to use the list monad to generate all possible subsets:
<
===Dynamic Programming===
The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion. For example, <code>comb m (x1:x2:xs)</code> involves computing <code>comb (m-1) (x2:xs)</code> and <code>comb m (x2:xs)</code>, both of which (separately) compute <code>comb (m-1) xs</code>. To avoid repeated computation, we can use dynamic programming:
<
comb m xs = combsBySize xs !! m
combsBySize = foldr f ([[]] : repeat [])
f x next =
zipWith
(<>)
(fmap (x :) <$> ([] : next))
next
main :: IO ()
main = print $ comb 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|Icon}} and {{header|Unicon}}==
<
return combinations(3,5,0)
end
Line 2,168 ⟶ 2,514:
end
link lists</
The {{libheader|Icon Programming Library}} provides the core procedure [http://www.cs.arizona.edu/icon/library/src/procs/lists.icn lcomb in lists] written by Ralph E. Griswold and Richard L. Goerwitz.
<
local j
Line 2,178 ⟶ 2,524:
else [L[j := 1 to *L - i + 1]] ||| lcomb(L[j + 1:0],i - 1)
end</
{{out}}
<pre>3 combinations of 5 integers starting from 0
Line 2,194 ⟶ 2,540:
[ 1 3 4 ]
[ 2 3 4 ]</pre>
=={{header|J}}==
Line 2,221 ⟶ 2,545:
===Library===
<syntaxhighlight lang
Example use:
<
0 1 2
0 1 3
Line 2,235 ⟶ 2,559:
1 2 4
1 3 4
2 3 4</
All implementations here give that same result if given the same arguments.
===Iteration===
<
c=. 1 {.~ - d=. 1+y-x
z=. i.1 0
for_j. (d-1+y)+/&i.d do. z=. (c#j) ,. z{~;(-c){.&.><i.{.c=. +/\.c end.
)</
another iteration version
<
d =. 1 + y - x
k =. >: |. i. d
Line 2,256 ⟶ 2,580:
end.
;{.z
)</
===Recursion===
<
if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x combr&.<: y),1+x combr y-1 end.
)</
The <code>M.</code> uses memoization (caching) which greatly reduces the running time. As a result, this is probably the fastest of the implementations here.
A less efficient but easier to understand recursion (similar to Python and Haskell).
<
if.(x=#y) +. x=1 do.
y
Line 2,272 ⟶ 2,596:
end.
)
</syntaxhighlight>
You need to supply the "list" for example <code>i.5</code>
<code>
Line 2,280 ⟶ 2,604:
===Brute Force===
We can also generate all permutations and exclude those which are not properly sorted combinations. This is inefficient, but efficiency is not always important.
<
=={{header|Java}}==
Line 2,286 ⟶ 2,610:
{{works with|Java|1.5+}}
<
import java.util.LinkedList;
Line 2,315 ⟶ 2,639:
return s;
}
}</
=={{header|JavaScript}}==
Line 2,321 ⟶ 2,645:
===Imperative===
<
var s="";
for (var n=0; u; ++n, u>>=1)
Line 2,338 ⟶ 2,662:
return s.sort();
}
comb(3,5)</
Alternative recursive version using and an array of values instead of length:
{{trans|Python}}
<
var i,
subI,
Line 2,368 ⟶ 2,692:
combinations(["Crosby", "Stills", "Nash", "Young"], 3);
// produces: [["Crosby", "Stills", "Nash"], ["Crosby", "Stills", "Young"], ["Crosby", "Nash", "Young"], ["Stills", "Nash", "Young"]]
</syntaxhighlight>
===Functional===
Line 2,376 ⟶ 2,700:
Simple recursion:
<
function comb(n, lst) {
Line 2,404 ⟶ 2,728:
}).join('\n');
})();</
We can significantly improve on the performance of the simple recursive function by deriving a memoized version of it, which stores intermediate results for repeated use.
<
// n -> [a] -> [[a]]
Line 2,453 ⟶ 2,777:
}).join('\n');
})(3);</
{{Out}}
<syntaxhighlight lang="javascript">0 1 2
0 1 3
0 1 4
Line 2,467 ⟶ 2,791:
1 2 4
1 3 4
2 3 4</
====ES6====
Defined in terms of a recursive helper function:
<
'use strict';
// ------------------ COMBINATIONS -------------------
// combinations :: Int -> [a] -> [[a]]
const combinations =
return 1 > n ? [
[]
return comb(n - 1)(tail)
.map(cons(h))
.concat(comb(n)(tail));
})()
};
return comb(n)(xs);
};
//
const main = () =>
show(
combinations(3)(
enumFromTo(0)(4)
)
);
// ---------------- GENERIC FUNCTIONS ----------------
// cons :: a -> [a] -> [a]
const cons =
// A list constructed from the item x,
// followed by the existing list xs.
xs => [x].concat(xs);
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo =
}, (_, i) => m + i)
) : enumFromTo_(m)(n);
// show :: a -> String
Line 2,533 ⟶ 2,854:
);
return main();
})();</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>
Or, defining combinations in terms of a more general subsequences function:
<
'use strict';
//
// comb :: Int -> Int -> [[Int]]
const comb =
n => combinations(m)(
enumFromTo(0)(n - 1)
);
// combinations :: Int -> [a] -> [[a]]
const combinations =
filter(xs => k === xs.length)(
subsequences(xs)
)
);
// --------------------- TEST ---------------------
const main = () =>
show(
comb(3)(5)
);
//
// cons :: a -> [a] -> [a]
const cons =
// A list constructed from the item x,
// followed by the existing list xs.
xs => [x].concat(xs);
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo =
}, (_, i) => m + i)
) : enumFromTo_(m)(n);
// filter :: (a -> Bool) -> [a] -> [a]
const filter =
// The elements of xs which match
// the predicate p.
xs => [...xs].filter(p);
//
const
// xs itself, if it is an Array,
// or an Array derived from xs.
Array.isArray(xs) ? (
xs
) : Array.from(xs || []);
// show :: a -> String
const show = x =>
// JSON stringification of a JS value.
JSON.stringify(x)
// sort :: Ord a => [a] -> [a]
const sort = xs => list(xs).
.sort((a, b) => a < b ? -1 : (a > b ? 1 : 0));
// subsequences :: [a] -> [[a]]
// subsequences :: String -> [String]
const subsequences = xs => {
const
// nonEmptySubsequences :: [a] -> [[a]]
if
const [x, xs] =
const f = (r, ys) => cons(ys
return cons([x])(nonEmptySubsequences(xs)
};
return ('string' === typeof xs) ? (
) : cons([])(nonEmptySubsequences(xs));
};
//
return main();
})();</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>
With recursions:
<syntaxhighlight lang="javascript">function combinations(k, arr, prefix = []) {
if (prefix.length == 0) arr = [...Array(arr).keys()];
if (k == 0) return [prefix];
return arr.flatMap((v, i) =>
combinations(k - 1, arr.slice(i + 1), [...prefix, v])
);
}</syntaxhighlight>
=={{header|jq}}==
combination(r) generates a stream of combinations of the input array.
The stream can be captured in an array as shown in the second example.
<
if r > length or r < 0 then empty
elif r == length then .
Line 2,624 ⟶ 2,976:
# select r integers from the set (0 .. n-1)
def combinations(n;r): [range(0;n)] | combination(r);</
'''Example 1'''
combinations(5;3)
Line 2,646 ⟶ 2,998:
=={{header|Julia}}==
The <code>combinations</code> function in the <code>Combinatorics.jl</code> package generates an iterable sequence of the combinations that you can loop over. (Note that the combinations are computed on the fly during the loop iteration, and are not pre-computed or stored since there many be a very large number of them.)
<
n = 4
m = 3
for i in combinations(0:n,m)
println(i')
end</
{{out}}
<pre>[0 1 2]
Line 2,669 ⟶ 3,021:
If, on the other hand we wanted to show how it could be done in Julia, this recursive solution shows some potentials of Julia lang.
<
# COMBINATIONS OF 3 OUT OF 5 #
##############################
Line 2,695 ⟶ 3,047:
combinations(1, 0)
end</
{{out}}
<pre>
Line 2,709 ⟶ 3,061:
[3, 4, 5]
</pre>
===Iterator Solution===
Alternatively, Julia's Iterators can be used for a very nice solution for any collection.
<syntaxhighlight lang="julia">
using Base.Iterators
function bitmask(u, max_size)
res = BitArray(undef, max_size)
res.chunks[1] = u%UInt64
res
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) |>
size_filter |>
bitmask_map |>
getindex_map |>
collect
end
</syntaxhighlight>
{{out}}
<pre>
julia> show(combinations([1,2,3,4,5], 3))
[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 5], [1, 3, 5], [2, 3, 5], [1, 4, 5], [2, 4, 5], [3, 4, 5]]
</pre>
end
=={{header|K}}==
Recursive implementation:
<
f:{:[k=#x; :,x; :,/_f' x,'(1+*|x) _ !n]}
:,/f' !n
}</
=={{header|Lambdatalk}}==
Translation from Emacs-lisp
<syntaxhighlight lang="scheme">
{def comb
Line 2,741 ⟶ 3,124:
[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
</syntaxhighlight>
=={{header|Kotlin}}==
===Recursion===
{{trans|Pascal}}
<
private val combination = IntArray(m)
Line 2,770 ⟶ 3,153:
fun main(args: Array<String>) {
Combinations(3, 5)
}</
{{out}}
Line 2,788 ⟶ 3,171:
===Lazy===
{{trans|C#}}
<
inline fun <reified T> combinations(arr: Array<T>, m: Int) = sequence {
Line 2,816 ⟶ 3,199:
combinations((1..n).toList().toTypedArray(), m).forEach { println(it.joinToString(separator = " ")) }
}
</syntaxhighlight>
{{out}}
Line 2,834 ⟶ 3,217:
=={{header|Lobster}}==
{{trans|Nim}}
<
// combi is an itertor that solves the Combinations problem for iota arrays as stated
Line 2,854 ⟶ 3,237:
i += 1
combi(5, 3): print(_)</
{{out}}
<pre>[0, 1, 2]
Line 2,868 ⟶ 3,251:
{{trans|JavaScript}}
<
// comba solves the general problem for any values in an input array
Line 2,889 ⟶ 3,272:
var s = ""
combi(4, 3): s += (map(_) i: ["Crosby", "Stills", "Nash", "Young"][i]) + " "
print s</
{{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]]
Line 2,897 ⟶ 3,280:
=={{header|Logo}}==
<
if :n = 0 [output [[]]]
if empty? :list [output []]
Line 2,903 ⟶ 3,286:
comb :n bf :list
end
print comb 3 [0 1 2 3 4]</
=={{header|Lua}}==
<
function map(f, a, ...) if a then return f(a), map(f, ...) end end
function incr(k) return function(a) return k > a and a or a+1 end end
Line 2,919 ⟶ 3,302:
for k, v in ipairs(combs(3, 5)) do print(unpack(v)) end
</syntaxhighlight>
=={{header|M2000 Interpreter}}==
Including a helper sub to export result to clipboard through a global variable (a temporary global variable)
<syntaxhighlight lang="m2000 interpreter">
Module Checkit {
Global a$
Line 2,965 ⟶ 3,348:
}
Checkit
</syntaxhighlight>
{{out}}
<pre>
Line 2,981 ⟶ 3,364:
===Step by Step===
<syntaxhighlight lang="m2000 interpreter">
Module StepByStep {
Function CombinationsStep (a, nn) {
Line 3,027 ⟶ 3,410:
}
StepByStep
</syntaxhighlight>
=={{header|M4}}==
<
define(`set',`define(`$1[$2]',`$3')')
define(`get',`defn(`$1[$2]')')
Line 3,055 ⟶ 3,438:
divert
comb(3,5)</
=={{header|Maple}}==
This is built-in in Maple:
<
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5],
[2, 4, 5], [3, 4, 5]]
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">combinations[n_Integer, m_Integer]/;m>= 0:=Union[Sort /@ Permutations[Range[0, n - 1], {m}]]</syntaxhighlight>
built-in function example
<syntaxhighlight lang="mathematica">Subsets[Range[5], {2}]</syntaxhighlight>
=={{header|MATLAB}}==
Line 3,076 ⟶ 3,457:
Task Solution:
<
ans =
Line 3,089 ⟶ 3,470:
1 2 4
1 3 4
2 3 4</
=={{header|Maxima}}==
<
[a: copylist(a), i: p],
if a[1] + p = n + 1 then return(und),
Line 3,117 ⟶ 3,498:
[2, 3, 5],
[2, 4, 5],
[3, 4, 5]] */</
=={{header|Modula-2}}==
{{trans|Pascal}}
{{works with|ADW Modula-2|any (Compile with the linker option ''Console Application'').}}
<
MODULE Combinations;
FROM STextIO IMPORT
Line 3,159 ⟶ 3,540:
Generate(1);
END Combinations.
</syntaxhighlight>
{{out}}
<pre>
Line 3,175 ⟶ 3,556:
=={{header|Nim}}==
<
var c = newSeq[int](n)
for i in 0 ..
block outer:
Line 3,183 ⟶ 3,564:
yield c
var i = n - 1
inc c[i]
if c[i] <= m - 1: continue
Line 3,195 ⟶ 3,576:
inc i
for i in comb(5, 3):
echo i</syntaxhighlight>
{{out}}
<pre>@[0, 1, 2]
Line 3,209 ⟶ 3,591:
<
var result = newSeq[int](n)
var stack = newSeq[int]()
stack.add 0
while stack.len > 0:
var index = stack.high
var value = stack.pop()
while value < m:
result[index] = value
inc value
inc index
stack.add value
if index == n:
yield result
break
for i in combinations(5, 3):
echo i</syntaxhighlight>
=={{header|OCaml}}==
<
let rec c = function
| (0,_) -> [[]]
Line 3,244 ⟶ 3,631:
| hd :: tl -> print_int hd ; print_string " "; print_list tl
in List.iter print_list (combinations 3 5)
</syntaxhighlight>
=={{header|Octave}}==
<
=={{header|OpenEdge/Progress}}==
{{trans|Julia}}
<syntaxhighlight lang="openedge/progress">
define variable r as integer no-undo extent 3.
define variable m as integer no-undo initial 5.
Line 3,271 ⟶ 3,658:
combinations(1, 0).
</syntaxhighlight>
{{out}}
0 1 2<br>
Line 3,286 ⟶ 3,673:
=={{header|Oz}}==
This can be implemented as a trivial application of finite set constraints:
<
fun {Comb M N}
proc {CombScript Comb}
Line 3,301 ⟶ 3,688:
end
in
{Inspect {Comb 3 5}}</
=={{header|PARI/GP}}==
<
if( d == k,
,
v[ d + 2 ] = i;
Crv( k, v, d + 1 ) ));
}
combRV( n, k ) = Crv ( k, vector( n, X, X-1), 0 );</syntaxhighlight>
<syntaxhighlight lang="parigp">Cr ( c, z, b, n, k ) = {
if( z < b, print1( c, " " );
if( n>0, Cr( c+1, z , b* k \n, n-1, k - 1 ))
,
}
combR( n, k ) = {
local(
bnk = binomial( n, k ),
b11 = bnk * k \ n ); \\binomial( n-1, k-1 )
for( z = 0, bnk - 1,
Cr( 1, z, b11, n-1, k-1 );
print
);
}</syntaxhighlight>
<syntaxhighlight lang="parigp">Ci( z, b, n, k ) = { local( c = 1 );
n--; k--;
while( k >= 0 ,
if( z < b,
print1(c, " ");
c++;
if( n > 0,
b = b*k \ n);
n--; k--;
,
c++;
z -= b;
b = b*(n-k)\n;
n--
)
);
print;
}
combI( n, k ) = {
local( bnk = binomial( n, k ),
b11 = bnk * k \ n ); \\ binomial( n-1, k-1 )
for( z = 0, bnk - 1,
Ci(z, b11, n, k ) );
}</syntaxhighlight>
=={{header|Pascal}}==
<
const
Line 3,348 ⟶ 3,776:
begin
generate(1);
end.</
{{out}}
Line 3,367 ⟶ 3,795:
The [https://metacpan.org/pod/ntheory ntheory] module has a combinations iterator that runs in lexicographic order.
{{libheader|ntheory}}
<
forcomb { print "@_\n" } 5,3</
{{out}}
<pre>
Line 3,385 ⟶ 3,813:
[https://metacpan.org/pod/Algorithm::Combinatorics Algorithm::Combinatorics] also does lexicographic order and can return the whole array or an iterator:
{{libheader|Algorithm::Combinatorics}}
<
my @c = combinations( [0..4], 3 );
print "@$_\n" for @c;</
<
my $iter = combinations([0..4],3);
while (my $c = $iter->next) {
print "@$c\n";
}</
[https://metacpan.org/pod/Math::Combinatorics Math::Combinatorics] is another option but results will not be in lexicographic order as specified by the task.
Line 3,411 ⟶ 3,839:
The major <i>Perl5i</i> -isms are the implicit "autoboxing" of the intermediate resulting array into an array object, with the use of unshift() as a method, and the "func" keyword and signature.
Note that Perl can construct ranges of numbers or of letters, so it is natural to identify the characters as 'a' .. 'e'.
<syntaxhighlight lang="perl5i">
use perl5i::2;
Line 3,434 ⟶ 3,862:
say @$_ for combine( 3, ('a'..'e') );
</syntaxhighlight>
{{out}}
Line 3,452 ⟶ 3,880:
=={{header|Phix}}==
It does not get much simpler or easier than this. See [[Sudoku#Phix|Sudoku]] for a practical application of this algorithm
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">pool</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">needed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">done</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">={})</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">needed</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- got a full set</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">chosen</span> <span style="color: #000080;font-style:italic;">-- (or use a routine_id, result arg, or whatever)</span>
<span style="color: #008080;">return</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">done</span><span style="color: #0000FF;">+</span><span style="color: #000000;">needed</span><span style="color: #0000FF;">></span><span style="color: #000000;">pool</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- cannot fulfil
-- get all combinations with and without the next item:</span>
<span style="color: #000000;">done</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">,</span><span style="color: #000000;">needed</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">done</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;">chosen</span><span style="color: #0000FF;">),</span><span style="color: #000000;">done</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">,</span><span style="color: #000000;">needed</span><span style="color: #0000FF;">,</span><span style="color: #000000;">done</span><span style="color: #0000FF;">,</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 3,477 ⟶ 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 3,485 ⟶ 3,924:
Much slower than normal algorithm.
<
<?php
Line 3,535 ⟶ 3,974:
?>
</syntaxhighlight>
'''
Output:'''
Line 3,558 ⟶ 3,997:
===recursive===
<
function combinations_set($set = [], $size = 0) {
Line 3,606 ⟶ 4,045:
echo implode(", ", $combination), "\n";
}
</syntaxhighlight>
Outputs:
Line 3,623 ⟶ 4,062:
2, 3, 4
</pre>
=={{header|Picat}}==
===Recursion===
<syntaxhighlight lang="picat">go =>
% Integers 1..K
N = 3,
K = 5,
printf("comb1(3,5): %w\n", comb1(N,K)),
nl.
% Recursive (numbers)
comb1(M,N) = comb1_(M, 1..N).
comb1_(0, _X) = [[]].
comb1_(_M, []) = [].
comb1_(M, [X|Xs]) = [ [X] ++ Xs2 : Xs2 in comb1_(M-1, Xs) ] ++ comb1_(M, Xs).</syntaxhighlight>
{{out}}
<pre>comb1(3,5): [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]</pre>
===Using built-in power_set===
<syntaxhighlight lang="picat">comb2(K, N) = sort([[J : J in I] : I in power_set(1..N), I.length == K]).</syntaxhighlight>
===Combinations from a list===
<syntaxhighlight lang="picat">go3 =>
L = "abcde",
printf("comb3(%d,%w): %w\n",3,L,comb3(3,L)).
comb3(M, List) = [ [List[P[I]] : I in 1..P.length] : P in comb1(M,List.length)].</syntaxhighlight>
{{out}}
<pre>comb3(3,abcde): [abc,abd,abe,acd,ace,ade,bcd,bce,bde,cde]</pre>
=={{header|PicoLisp}}==
{{trans|Scheme}}
<
(cond
((=0 M) '(NIL))
Line 3,637 ⟶ 4,107:
(comb M (cdr Lst)) ) ) ) )
(comb 3 (1 2 3 4 5))</
=={{header|Pop11}}==
Line 3,644 ⟶ 4,114:
The 'el_lst' parameter to 'do_combs' contains partial combination (list of numbers which were chosen in previous steps) in reverse order.
<
lvars ress = [];
define do_combs(l, m, el_lst);
Line 3,660 ⟶ 4,130:
enddefine;
comb(5, 3) ==></
=={{header|PowerShell}}==
An example of how PowerShell itself can translate C# code:
<syntaxhighlight lang="powershell">
$source = @'
using System;
Line 3,700 ⟶ 4,170:
[Powershell.CSharp]::Combinations(3,5) | Format-Wide {$_} -Column 3 -Force
</syntaxhighlight>
{{Out}}
<pre>
Line 3,718 ⟶ 4,188:
The solutions work with SWI-Prolog <BR>
Solution with library clpfd : we first create a list of M elements, we say that the members of the list are numbers between 1 and N and there are in ascending order, finally we ask for a solution.
<
comb_clpfd(L, M, N) :-
Line 3,724 ⟶ 4,194:
L ins 1..N,
chain(L, #<),
label(L).</
{{out}}
<pre> ?- comb_clpfd(L, 3, 5), writeln(L), fail.
Line 3,739 ⟶ 4,209:
false.</pre>
Another solution :
<
length(L, M),
fill(L, 1, N).
Line 3,749 ⟶ 4,219:
H1 is H + 1,
fill(T, H1, Max).
</syntaxhighlight>
with the same output.
===List comprehension===
Works with SWI-Prolog, library '''clpfd''' from '''Markus Triska''', and list comprehension (see [[List comprehensions]] ).
<
comb_lstcomp(N, M, V) :-
V <- {L & length(L, N), L ins 1..M & all_distinct(L), chain(L, #<), label(L)}.
</syntaxhighlight>
{{out}}
Line 3,766 ⟶ 4,236:
=={{header|Pure}}==
<
comb 0 _ = [[]];
comb _ [] = [];
Line 3,772 ⟶ 4,242:
end;
comb 3 5;</
=={{header|PureBasic}}==
<
NewList comb.s()
; all possible combinations with {amount} Bits
Line 3,808 ⟶ 4,278:
EndProcedure
Debug Combinations(5, 3)</
=={{header|Pyret}}==
<
fun combos<a>(lst :: List<a>, size :: Number) -> List<List<a>>:
Line 3,917 ⟶ 4,387:
</syntaxhighlight>
=={{header|Python}}==
Starting from Python 2.6 and 3.0 you have a pre-defined function that returns an iterator. Here we turn the result into a list for easy printing:
<
>>> list(combinations(range(5),3))
[(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)]</
Earlier versions could use functions like the following:
{{trans|E}}
<
if m == 0: return [[]]
return [[x] + suffix for i, x in enumerate(lst)
for suffix in comb(m - 1, lst[i + 1:])]</
Example:
<
[[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]]</
{{trans|Haskell}}
<
if m == 0: return [[]]
if s == []: return []
return [s[:1] + a for a in comb(m-1, s[1:])] + comb(m, s[1:])
print comb(3, range(5))</
A slightly different recursion version
<
def comb(m, s):
if m == 1: return [[x] for x in s]
Line 3,950 ⟶ 4,420:
return [s[:1] + a for a in comb(m-1, s[1:])] + comb(m, s[1:])
</syntaxhighlight>
=={{header|Quackery}}==
===Bit Bashing===
<syntaxhighlight lang="quackery"> [ 0 swap
[ dup 0 != while
dup 1 & if
[ dip 1+ ]
1 >> again ]
drop ] is bits ( n --> n )
[ [] unrot
bit times
[ i bits
over = if
[ dip
[ i join ] ] ]
drop ] is combnums ( n n --> [ )
[ [] 0 rot
[ dup 0 != while
dup 1 & if
[ dip
[ dup dip join ] ]
dip 1+
1 >>
again ]
2drop ] is makecomb ( n --> [ )
[ over 0 = iff
[ 2drop [] ] done
combnums
[] swap witheach
[ makecomb
nested join ] ] is comb ( n n --> [ )
[ behead swap witheach max ] is largest ( [ --> n )
[ 0 rot witheach
[ [ dip [ over * ] ] + ]
nip ] is comborder ( [ n --> n )
[ dup [] != while
sortwith
[ 2dup join
largest 1+ dup dip
[ comborder swap ]
comborder < ] ] is sortcombs ( [ --> [ )
3 5 comb
sortcombs
witheach [ witheach [ echo sp ] cr ]</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>
===Iterative===
<syntaxhighlight lang="quackery"> [ stack ] is comb.stack
[ stack ] is comb.items
[ stack ] is comb.required
[ stack ] is comb.result
[ 1 - comb.items put
1+ comb.required put
0 comb.stack put
[] comb.result put
[ comb.required share
comb.stack size = if
[ comb.result take
comb.stack behead
drop nested join
comb.result put ]
comb.stack take
dup comb.items share
= iff
[ drop
comb.stack size 1 > iff
[ 1 comb.stack tally ] ]
else
[ dup comb.stack put
1+ comb.stack put ]
comb.stack size 1 = until ]
comb.items release
comb.required release
comb.result take ] is comb ( n n --> )
3 5 comb
witheach [ witheach [ echo sp ] cr ]</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>
===… and a handy tool===
Can be used with <code>comb</code>, and is general purpose.
<syntaxhighlight lang="quackery"> [ dup size dip
[ witheach
[ over swap peek swap ] ]
nip pack ] is arrange ( [ [ --> [ )
' [ 10 20 30 40 50 ]
3 5 comb
witheach
[ dip dup arrange
witheach [ echo sp ]
cr ]
drop
cr
$ "zero one two three four" nest$
' [ 4 3 1 0 1 4 3 ] arrange
witheach [ echo$ sp ] </syntaxhighlight>
{{out}}
<pre>10 20 30
10 20 40
10 20 50
10 30 40
10 30 50
10 40 50
20 30 40
20 30 50
20 40 50
30 40 50
four three one zero one four three</pre>
=={{header|R}}==
<
Combinations are organized per column,
so to provide an output similar to the one in the task text, we need the following:
<
for(i in 1:choose(5,3)) print(r[,i])</
=={{header|Racket}}==
{{trans|Haskell}}
<
(define sublists
(match-lambda**
Line 3,972 ⟶ 4,591:
(define (combinations n m)
(sublists n (range m)))
</syntaxhighlight>
{{out}}
Line 3,993 ⟶ 4,612:
{{works with|rakudo|2015.12}}
There actually is a builtin:
<syntaxhighlight lang="raku"
{{out}}
<pre>(0 1 2)
Line 4,007 ⟶ 4,626:
Here is an iterative routine with the same output:
<syntaxhighlight lang="raku"
return ([],) unless $k;
return if $k > $n || $n <= 0;
Line 4,021 ⟶ 4,640:
}
}
.say for combinations(5,3);</
=={{header|REXX}}==
===Version 1===
This REXX program supports up to 100 symbols (one symbol for each "thing").
Line 4,029 ⟶ 4,649:
The symbol list could be extended by added any unique viewable symbol (character).
<
If things='?' Then Do
Say 'rexx combi things size characters'
Say ' defaults: 5 3 123456789...'
Say 'example rexx combi , , 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*/
If chars==''|chars=="," Then /* No chars specified? Then Use default*/
chars='123456789abcdefghijklmnopqrstuvwxyz'||,
'ABCDEFGHIJKLMNOPQRSTUVWXYZ'||,
"~!@#chars%^&*()_+`{}|[]\:;<>?,./¦++++±==˜·" /*some extended chars */
show_details=sign(size)
size=abs(size)
If things<size Then
Call exit 'Not enough things ('things') for size ('size').'
Say '------------' things 'things taken' size 'times at a time:'
Say '------------' combn(things,size) 'combinations.'
Exit /* stick a fork in it, we're all */
/*-------------------------------------------------------------------------------*/
combn: Procedure Expose chars show_details
Parse Arg things,size
thingsp=things+1
thingsm=thingsp-size
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= when using the input of: <tt> 5 3 01234 </tt>}}
<pre>
0 1 2
0 1 3
Line 4,070 ⟶ 4,735:
1 3 4
2 3 4
</pre>
{{out|output|text= when using the input of: <tt> 5 3 abcde </tt>}}
<pre>
a b c
a b d
Line 4,085 ⟶ 4,750:
b d e
c d e
</pre>
{{out|output|text= when using the input of: <tt> 44 0 </tt>}}
<pre>
</pre>
{{out|output|text= when using the input of: <tt> 52 -5 </tt>}}
<pre>
</pre>
{{out|output|text= when using the input of: <tt> 5 -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}}==
<
# Project : Combinations
Line 4,172 ⟶ 4,890:
next
return aList
</syntaxhighlight>
Output:
<pre>
Line 4,185 ⟶ 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>
=={{header|Ruby}}==
{{works with|Ruby|1.8.7+}}
<
(0...n).to_a.combination(m).to_a
end
comb(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]]</
=={{header|Rust}}==
{{works with|Rust|0.9}}
<
fn comb<T: std::fmt::Default>(arr: &[T], n: uint) {
let mut incl_arr: ~[bool] = std::vec::from_elem(arr.len(), false);
Line 4,228 ⟶ 4,977:
comb(arr2, 3);
}
</syntaxhighlight>
{{works with|Rust|1.26}}
<
struct Combo<T> {
data_len: usize,
Line 4,294 ⟶ 5,043:
}
}
</syntaxhighlight>
{{works with|Rust|1.47|}}
<syntaxhighlight lang="rust">
fn comb<T>(slice: &[T], k: usize) -> Vec<Vec<T>>
where
T: Copy,
{
// If k == 1, return a vector containing a vector for each element of the slice.
if k == 1 {
return slice.iter().map(|x| vec![*x]).collect::<Vec<Vec<T>>>();
}
// If k is exactly the slice length, return the slice inside a vector.
if k == slice.len() {
return vec![slice.to_vec()];
}
// Make a vector from the first element + all combinations of k - 1 elements of the rest of the slice.
let mut result = comb(&slice[1..], k - 1)
.into_iter()
.map(|x| [&slice[..1], x.as_slice()].concat())
.collect::<Vec<Vec<T>>>();
// Extend this last vector with the all the combinations of k elements after from index 1 onward.
result.extend(comb(&slice[1..], k));
// Return final vector.
return result;
}
</syntaxhighlight>
=={{header|Scala}}==
<
def comb(n: Int) = recurse(m, List.range(0, n))
private def recurse(m: Int, l: List[Int]): List[List[Int]] = (m, l) match {
Line 4,304 ⟶ 5,081:
case _ => (recurse(m - 1, l.tail) map (l.head :: _)) ::: recurse(m, l.tail)
}
}</
Usage:
Line 4,315 ⟶ 5,092:
Lazy version using iterators:
<
case _ if n < 0 || l.lengthCompare(n) < 0 => Iterator.empty
case 0 => Iterator(List.empty)
Line 4,322 ⟶ 5,099:
case x :: xs => combs(n - 1, xs).map(x :: _)
})
}</
Usage:
<pre>
Line 4,331 ⟶ 5,108:
===Dynamic programming===
Adapted from Haskell version:
<
combsBySize(xs)(n)
Line 4,346 ⟶ 5,123:
def f[A](x: A, xsss: Stream[Stream[List[A]]]): Stream[Stream[List[A]]] =
Stream.empty #:: xsss.map(_.map(x :: _))</
Usage:
<pre>
Line 4,355 ⟶ 5,132:
===Using Scala Standard Runtime Library===
====Scala REPL====
<
res0: List[scala.collection.immutable.IndexedSeq[Int]] = List(Vector(0, 1, 2), Vector(0, 1, 3), Vector(0, 1, 4), Vector(0, 2, 3), Vector(0, 2, 4), Vector(0, 3, 4), Vector(1, 2, 3), Vector(1, 2, 4), Vector(1, 3, 4), Vector(2, 3, 4))</
====Other environments====
{{Out}}See it running in your browser by [https://scalafiddle.io/sf/DH34cqq/0 ScalaFiddle (JavaScript, non JVM)] or by [https://scastie.scala-lang.org/bwADub2XR8eu6bVVDbQw7g Scastie (JVM)].
Line 4,362 ⟶ 5,139:
=={{header|Scheme}}==
Like the Haskell code:
<
(cond ((= m 0) '(()))
((null? lst) '())
Line 4,369 ⟶ 5,146:
(comb m (cdr lst))))))
(comb 3 '(0 1 2 3 4))</
=={{header|Seed7}}==
<
const type: combinations is array array integer;
Line 4,406 ⟶ 5,183:
writeln;
end for;
end func;</
{{out}}
Line 4,423 ⟶ 5,200:
=={{header|SETL}}==
<
=={{header|Sidef}}==
===Built-in===
<
===Recursive===
{{trans|Perl5i}}
<
set.len || return []
Line 4,449 ⟶ 5,226:
}
combine(3, @^5).each {|c| say c }</
===Iterative===
<
if (k == 0) {
Line 4,482 ⟶ 5,259:
}
forcomb({|c| say c }, 5, 3)</
{{out}}
<pre>
Line 4,500 ⟶ 5,277:
{{works with|Pharo}}
{{works with|Squeak}}
<
(0 to: 4) combinations: 3 atATimeDo: [ :x | Transcript cr; show: x printString].
Line 4,514 ⟶ 5,291:
#(1 3 4)
#(2 3 4)"
</syntaxhighlight>
=={{header|SPAD}}==
Line 4,520 ⟶ 5,297:
{{works with|OpenAxiom}}
{{works with|Axiom}}
<syntaxhighlight lang="spad">
[reverse subSet(5,3,i)$SGCF for i in 0..binomial(5,3)-1]
Line 4,527 ⟶ 5,304:
[1,3,4], [2,3,4]]
Type: List(List(Integer))
</syntaxhighlight>
[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}}==
<
| comb (_, [] ) = []
| comb (m, x::xs) = map (fn y => x :: y) (comb (m-1, xs)) @
comb (m, xs)
;
comb (3, [0,1,2,3,4]);</
=={{header|Stata}}==
<
tempfile cp
tempvar k
Line 4,553 ⟶ 5,414:
}
sort `1'*
end</
'''Example'''
<
. gen a=_n
. combin a 3
Line 4,576 ⟶ 5,437:
9. | 2 4 5 |
10. | 3 4 5 |
+--------------+</
=== Mata ===
<
a = J(comb(n,k),k,.)
u = 1..k
Line 4,591 ⟶ 5,452:
}
combinations(5,3)</
'''Output'''
Line 4,610 ⟶ 5,471:
=={{header|Swift}}==
<
return (0..<pivotList.count)
Line 4,629 ⟶ 5,490:
}
println(combosOfLength(5, 3))</
{{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 4,635 ⟶ 5,496:
=={{header|Tcl}}==
ref[http://wiki.tcl.tk/2553]
<
set set [list]
for {set i 0} {$i < $n} {incr i} {lappend set $i}
Line 4,655 ⟶ 5,516:
}
comb 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}</
=={{header|TXR}}==
Line 4,663 ⟶ 5,524:
Combinations and permutations are produced in lexicographic order (except in the case of hashes).
<
(comb (range* 0 n) m))
(put-line `3 comb 5 = @(comb-n-m 5 3)`)</
{{out|Run}}
Line 4,672 ⟶ 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}}==
Most of the work is done by the standard library function <code>choices</code>, whose implementation is shown here for the sake of comparison with other solutions,
<
where <code>leql</code> is the predicate that compares list lengths. The main body of the algorithm (<code>~&arh2fabt2RDfalrtPXPRT</code>) concatenates the results of two recursive calls, one of which finds all combinations of the required size from the tail of the list, and the other of which finds all combinations of one less size from the tail, and then inserts the head into each.
<code>choices</code> generates combinations of an arbitrary set but
not necessarily in sorted order, which can be done like this.
<
#import nat
combinations = @rlX choices^|(iota,~&); -< @p nleq+ ==-~rh</
* The sort combinator (<code>-<</code>) takes a binary predicate to a function that sorts a list in order of that predicate.
* The predicate in this case begins by zipping its two arguments together with <code>@p</code>.
Line 4,690 ⟶ 5,586:
* The overall effect of using everything starting from the <code>@p</code> as the predicate to a sort combinator is therefore to sort a list of lists of natural numbers according to the order of the numbers in the first position where they differ.
test program:
<
example = combinations(3,5)</
{{out}}
<pre><
Line 4,708 ⟶ 5,604:
=={{header|V}}==
like scheme (using variables)
<
[ [m zero?] [[[]]]
[lst null?] [[]]
[true] [m pred lst rest comb [lst first swap cons] map
m lst rest comb concat]
] when].</
Using destructuring view and stack not *pure at all
<
[ [pop zero?] [pop pop [[]]]
[null?] [pop pop []]
[true] [ [m lst : [m pred lst rest comb [lst first swap cons] map
m lst rest comb concat]] view i ]
] when].</
Pure concatenative version
<
[2dup [a b : a b a b] view].
[2pop pop pop].
Line 4,731 ⟶ 5,627:
[null?] [2pop []]
[true] [2dup [pred] dip uncons swapd comb [cons] map popd rollup rest comb concat]
] when].</
Using it
Line 4,738 ⟶ 5,634:
=={{header|VBA}}==
<
Option Base 0
'Option Base 1
Line 4,801 ⟶ 5,697:
Transposition = T
Erase T
End Function</
{{Out}}
If Option Base 0 :
Line 4,826 ⟶ 5,722:
3 4 5</pre>
{{trans|Phix}}
<
If needed = 0 Then '-- got a full set
For Each x In chosen: Debug.Print x;: Next x
Line 4,849 ⟶ 5,745:
Public Sub main()
comb 5, 3
End Sub</
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
Function Dec2Bin(n)
q = n
Line 4,893 ⟶ 5,789:
'Testing with n = 5 / k = 3
Call Combination(5,3)
</syntaxhighlight>
{{Out}}
Line 4,910 ⟶ 5,806:
=={{header|Wren}}==
{{
<syntaxhighlight lang="wren">import "./perm" for Comb
var fib = Fiber.new { Comb.generate((0..4).toList, 3) }
while (true) {
var c = fib.call()
if (!c) return
System.print(c)
}</syntaxhighlight>
{{out}}
Line 4,947 ⟶ 5,831:
=={{header|XPL0}}==
<
def M=3, N=5;
int A(N-1);
Line 4,965 ⟶ 5,849:
];
Combos(0, 0)</
{{out}}
Line 4,983 ⟶ 5,867:
=={{header|zkl}}==
{{trans|OCaml}}
<
seq=seq.makeReadOnly(); // because I append to parts of seq
fcn(k,seq){
Line 4,991 ⟶ 5,875:
.extend(self.fcn(k,seq[1,*]));
}(k,seq);
}</
<
{{out}}<pre>L("abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde")</pre>
|