Combinations
Given non-negative integers m and n, generate all size m combinations of the integers from 0 to n-1 in sorted order (each combination is sorted and the entire table is sorted).
You are encouraged to solve this task according to the task description, using any language you may know.
For example, 3 comb 5 is
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
If it is more "natural" in your language to start counting from 1 instead of 0 the combinations can be of the integers from 1 to n.
Ada
<lang ada>with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Combinations is
generic
type Integers is range <>;
package Combinations is
type Combination is array (Positive range <>) of Integers;
procedure First (X : in out Combination);
procedure Next (X : in out Combination);
procedure Put (X : Combination);
end Combinations;
package body Combinations is
procedure First (X : in out Combination) is
begin
X (1) := Integers'First;
for I in 2..X'Last loop
X (I) := X (I - 1) + 1;
end loop;
end First;
procedure Next (X : in out Combination) is
begin
for I in reverse X'Range loop
if X (I) < Integers'Val (Integers'Pos (Integers'Last) - X'Last + I) then
X (I) := X (I) + 1;
for J in I + 1..X'Last loop
X (J) := X (J - 1) + 1;
end loop;
return;
end if;
end loop;
raise Constraint_Error;
end Next;
procedure Put (X : Combination) is
begin
for I in X'Range loop
Put (Integers'Image (X (I)));
end loop;
end Put;
end Combinations;
type Five is range 0..4;
package Fives is new Combinations (Five);
use Fives;
X : Combination (1..3);
begin
First (X);
loop
Put (X); New_Line;
Next (X);
end loop;
exception
when Constraint_Error =>
null;
end Test_Combinations;</lang> 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 <lang ada>type Five is range 0..4;</lang> The parameter m is the object's constraint. When n < m the procedure First (selects the first combination) will propagate Constraint_Error. The procedure Next selects the next combination. Constraint_Error is propagated when it is the last one. Sample output:
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
ALGOL 68
<lang algol68>MODE DATA = INT;
PRIO C = 7;
- Calculate the number of combinations anticipated #
OP C = (INT n, k)INT:
CASE k + 1 IN # case 0: # 1, # case 1: # n OUT (n - 1) C (k - 1) * n OVER k ESAC;
PROC combinations = (INT m, []DATA list)[,]DATA: (
CASE m IN
# case 1: # ( # transpose list #
[UPB list,1]DATA out;
out[,1]:=list;
out
)
OUT
[UPB list C m, m]DATA out;
INT index out := 1;
FOR i TO UPB list DO
DATA x = list[i];
[,]DATA y = combinations(m - 1, list[i+1:]);
FOR suffix TO UPB y DO
out[index out,1 ] := x;
out[index out,2:] := y[suffix,];
index out +:= 1
OD
OD;
out
ESAC
);
PRIO COMB = 7; OP COMB = (INT n, k)[,]INT: (
[k]DATA list; # create a list to recombine # FOR i TO UPB list DO list[i]:=i OD; combinations(n,list)
);
INT m = 3;
- IF formatted transput possible THEN#
FORMAT data repr = $d$;
FORMAT list repr = $"("n(m-1)(f(data repr)",")f(data repr)")"$;
printf ((list repr, 3 COMB 5, $l$));
- ELSE#
[,]DATA result = 3 COMB 5; FOR row TO UPB result DO print ((result[row,], new line)) OD
- FI#</lang>
Output:
(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)
+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
AppleScript
<lang AppleScript>on comb(n, k) set c to {} repeat with i from 1 to k set end of c to i's contents end repeat set r to {c's contents} repeat while my next_comb(c, k, n) set end of r to c's contents end repeat return r end comb
on next_comb(c, k, n) set i to k set c's item i to (c's item i) + 1 repeat while (i > 1 and c's item i ≥ n - k + 1 + i) set i to i - 1 set c's item i to (c's item i) + 1 end repeat if (c's item 1 > n - k + 1) then return false repeat with i from i + 1 to k set c's item i to (c's item (i - 1)) + 1 end repeat return true end next_comb
return comb(5, 3)</lang>Output:<lang AppleScript>{{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}}</lang>
AutoHotkey
contributed by Laszlo on the ahk forum <lang AutoHotkey>MsgBox % Comb(1,1) MsgBox % Comb(3,3) MsgBox % Comb(3,2) MsgBox % Comb(2,3) MsgBox % Comb(5,3)
Comb(n,t) { ; Generate all n choose t combinations of 1..n, lexicographically
IfLess n,%t%, Return
Loop %t%
c%A_Index% := A_Index
i := t+1, c%i% := n+1
Loop {
Loop %t%
i := t+1-A_Index, c .= c%i% " "
c .= "`n" ; combinations in new lines
j := 1, i := 2
Loop
If (c%j%+1 = c%i%)
c%j% := j, ++j, ++i
Else Break
If (j > t)
Return c
c%j% += 1
}
}</lang>
C
<lang c>#include <stdio.h>
- include <stdlib.h>
typedef unsigned long u_long; typedef unsigned int u_int;
u_long choose(u_long n, u_long k, int *err) {
u_long imax, ans, i, imin;
if ( err != NULL ) *err = 0;
if ( (n<0) || (k<0) ) {
fprintf(stderr, "negative in choose\n");
if ( err != NULL ) *err = 1;
return 0;
}
if ( n < k ) return 0;
if ( n == k ) return 1;
imax = ( k > (n-k) ) ? k : n-k;
imin = ( k > (n-k) ) ? n-k : k;
ans = 1;
for(i=imax+1; i <= n; i++ ) ans *= i;
for(i=2; i <= imin; i++ ) ans /= i;
return ans;
}
u_int **comb(u_int n, u_int k) {
u_int **r, i, j, s, ix, kx; int err; u_long hm, t;
hm = choose(n, k, &err);
if ( err != 0 ) return NULL;
r = malloc(hm*sizeof(u_int *));
if ( r == NULL ) return NULL;
for(i=0; i < hm; i++) {
r[i] = malloc(sizeof(u_int)*k);
if ( r[i] == NULL ) {
for(j=0; j < i; j++) free(r[i]);
free(r);
return NULL;
}
}
for(i=0; i < hm; i++)
{
ix = i; kx = k;
for(s=0; s < n; s++) {
if ( kx == 0 ) break;
t = choose(n-(s+1), kx-1, NULL);
if ( ix < t ) {
r[i][kx-1] = s; kx--;
} else {
ix -= t;
} } } return r;
}
int main()
{
u_int **r; int i, j;
r = comb(5, 3);
for(i=0; i < choose(5, 3, NULL); i++) {
for(j=2; j >= 0; j--) {
printf("%d ", r[i][j]);
}
free(r[i]);
printf("\n");
}
free(r);
return 0;
}</lang>
C#
<lang csharp>using System; using System.Collections.Generic;
public class Program {
public static IEnumerable<int[]> Combinations(int m, int n)
{
int[] result = new int[m];
Stack<int> stack = new Stack<int>();
for (int j = 0; j <= n - m; j++)
{
result[0] = j;
stack.Push(j + 1);
while (stack.Count > 0)
{
int i = stack.Count;
int tail = result.Length - i;
int k = stack.Pop();
while (k <= n - tail)
{
result[i] = k;
stack.Push(k + 1);
k++;
i++;
tail--;
if (i == result.Length)
{
yield return result;
break;
}
}
}
}
}
static void Main()
{
foreach (int[] c in Combinations(3, 5))
{
for (int i = 0; i < c.Length; i++)
{
Console.Write(c[i] + " ");
}
Console.WriteLine();
}
}
}</lang>
Clojure
<lang clojure>(defn combinations
"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" [m n] (letfn [(comb-aux
[m start] (if (= 1 m) (for [x (range start n)] (list x)) (for [x (range start n) xs (comb-aux (dec m) (inc x))] (cons x xs))))]
(comb-aux m 0)))
(defn print-combinations
[m n]
(doseq [line (combinations m n)]
(doseq [n line]
(printf "%s " n))
(printf "%n")))</lang>
Common Lisp
<lang lisp>(defun map-combinations (m n fn)
"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)))
(labels ((up-from (low)
(let ((start (1- low)))
(lambda () (incf start))))
(mc (curr left needed comb-tail)
(cond
((zerop needed)
(funcall fn combination))
((= left needed)
(map-into comb-tail (up-from curr))
(funcall fn combination))
(t
(setf (first comb-tail) curr)
(mc (1+ curr) (1- left) (1- needed) (rest comb-tail))
(mc (1+ curr) (1- left) needed comb)))))
(mc 0 n m combination))))</lang>
Example use
> (map-combinations 3 5 'print) (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) (2 3 4)
D
Includes an algorithm to find mth Lexicographical Element of a Combination. <lang d>module combin ; import std.stdio, std.format: fmx = format ;
struct Combin{
const int n_, m_ ;
int opApply(int delegate(inout int[]) dg) {
int breaked = m_ < 0 || n_ < 0 ? 1 : 0 ;
int combinate(int[] sel, int cur, int left) {
if(breaked == 0) {
if(left > 0)
for(int i = cur ; i + left <= n_ ; i++)
combinate(sel ~ [i], i + 1, left - 1) ;
else
breaked = dg(sel) ;
}
return breaked ;
}
return combinate([], 0, m_) ;
}
string toString() { return fmx("%s",opSlice(0,length)) ; }
size_t length() { return choose(n_, m_) ; }
int[] opIndex(size_t idx) {
ulong largestV(ulong p, ulong q, ulong r) {
ulong v = p - 1 ;
while(choose(v,q) > r) v-- ;
return v ;
}
if(m_ < 0 || n_ < 0) return null ;
if(idx >= length) throw new Exception("Out of bound") ;
int[] result ;
ulong a = n_ , b = m_ , x = choose(n_,m_) - 1 - idx ;
for(ulong i = 0 ; i < m_; i++) {
a = largestV(a, b, x) ;
x = x - choose(a,b) ;
b = b - 1 ;
result ~= (n_ - 1 - a) ;
}
return result ;
}
int[][] opSlice(size_t a = 0, size_t b = size_t.max) {
int[][] slice ;
if(b == size_t.max) b = length ;
for(size_t i = a; i < b ; i++) slice ~= opIndex(i) ;
return slice ;
}
}
ulong choose(ulong n, ulong k) {
if(n<0 || k < 0) throw new Exception("No negative") ;
if(n < k) return 0 ;
else if(n == k) return 1 ;
ulong delta, iMax ;
if(k < n - k) { delta = n - k ; iMax = k ; }
else { delta = k ; iMax = n - k ; }
ulong ans = delta + 1 ;
for(ulong i = 2 ; i <= iMax ; i++)
ans = ans * (delta + i) / i ;
return ans ;
}
void main() {
foreach(c ; Combin(5,3))
writefln(c) ;
auto cm = Combin(5,3) ;
writefln("%s\n%s", typeid(typeof(cm)), cm) ;
auto cp = cm[] ;
writefln("%s\n%s", typeid(typeof(cp)), cp) ;
for(int i = 0 ; i< cm.length ; i++)
writefln(cm[i]) ;
}</lang> Slow recursive version based on the Python one: <lang d>import std.stdio: writefln;
T[][] comb(T)(T[] arr, int k) {
if (k == 0)
return [new T[0]];
else {
T[][] result;
foreach (i, x; arr)
foreach (suffix; comb(arr[i+1 .. $], k-1))
result ~= [x] ~ suffix;
return result;
}
}
void main() {
writefln(comb([0,1,2,3,4], 3));
}</lang>
E
<lang e>def combinations(m, range) {
return if (m <=> 0) { [[]] } else {
def combGenerator {
to iterate(f) {
for i in range {
for suffix in combinations(m.previous(), range & (int > i)) {
f(null, [i] + suffix)
}
}
}
}
}
}</lang>
? for x in combinations(3, 0..4) { println(x) }
Factor
<lang factor>USING: math.combinatorics prettyprint ;
5 iota 3 all-combinations .</lang>
{
{ 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 }
}
This works with any kind of sequence: <lang factor>{ "a" "b" "c" } 2 all-combinations .</lang>
{ { "a" "b" } { "a" "c" } { "b" "c" } }
Fortran
<lang fortran>program Combinations
use iso_fortran_env implicit none
type comb_result
integer, dimension(:), allocatable :: combs
end type comb_result
type(comb_result), dimension(:), pointer :: r integer :: i, j
call comb(5, 3, r)
do i = 0, choose(5, 3) - 1
do j = 2, 0, -1
write(*, "(I4, ' ')", advance="no") r(i)%combs(j)
end do
deallocate(r(i)%combs)
write(*,*) ""
end do
deallocate(r)
contains
function choose(n, k, err) integer :: choose integer, intent(in) :: n, k integer, optional, intent(out) :: err
integer :: imax, i, imin, ie
ie = 0
if ( (n < 0 ) .or. (k < 0 ) ) then
write(ERROR_UNIT, *) "negative in choose"
choose = 0
ie = 1
else
if ( n < k ) then
choose = 0
else if ( n == k ) then
choose = 1
else
imax = max(k, n-k)
imin = min(k, n-k)
choose = 1
do i = imax+1, n
choose = choose * i
end do
do i = 2, imin
choose = choose / i
end do
end if
end if
if ( present(err) ) err = ie
end function choose
subroutine comb(n, k, co) integer, intent(in) :: n, k type(comb_result), dimension(:), pointer, intent(out) :: co
integer :: i, j, s, ix, kx, hm, t
integer :: err
hm = choose(n, k, err)
if ( err /= 0 ) then
nullify(co)
return
end if
allocate(co(0:hm-1))
do i = 0, hm-1
allocate(co(i)%combs(0:k-1))
end do
do i = 0, hm-1
ix = i; kx = k
do s = 0, n-1
if ( kx == 0 ) exit
t = choose(n-(s+1), kx-1)
if ( ix < t ) then
co(i)%combs(kx-1) = s
kx = kx - 1
else
ix = ix - t
end if
end do
end do
end subroutine comb
end program Combinations</lang> Alternatively: <lang fortran>program combinations
implicit none
integer, parameter :: m_max = 3
integer, parameter :: n_max = 5
integer, dimension (m_max) :: comb
character (*), parameter :: fmt = '(i0' // repeat (', 1x, i0', m_max - 1) // ')'
call gen (1)
contains
recursive subroutine gen (m)
implicit none integer, intent (in) :: m integer :: n
if (m > m_max) then
write (*, fmt) comb
else
do n = 1, n_max
if ((m == 1) .or. (n > comb (m - 1))) then
comb (m) = n
call gen (m + 1)
end if
end do
end if
end subroutine gen
end program combinations</lang> Output: <lang>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</lang>
Groovy
Following the spirit of the Haskell solution.
In General
A recursive closure must be pre-declared. <lang groovy>def comb comb = { m, list ->
def n = list.size()
m == 0 ?
[[]] :
(0..(n-m)).inject([]) { newlist, k ->
def sublist = (k+1 == n) ? [] : list[(k+1)..<n]
newlist += comb(m-1, sublist).collect { [list[k]] + it }
}
}</lang>
Test program: <lang groovy>def csny = [ "Crosby", "Stills", "Nash", "Young" ] println "Choose from ${csny}" (0..(csny.size())).each { i -> println "Choose ${i}:"; comb(i, csny).each { println it }; println() }</lang>
Output:
Choose from [Crosby, Stills, Nash, Young] Choose 0: [] Choose 1: [Crosby] [Stills] [Nash] [Young] Choose 2: [Crosby, Stills] [Crosby, Nash] [Crosby, Young] [Stills, Nash] [Stills, Young] [Nash, Young] Choose 3: [Crosby, Stills, Nash] [Crosby, Stills, Young] [Crosby, Nash, Young] [Stills, Nash, Young] Choose 4: [Crosby, Stills, Nash, Young]
Zero-based Integers
<lang groovy>def comb0 = { m, n -> comb(m, (0..<n)) }</lang>
Test program: <lang groovy>println "Choose out of 5 (zero-based):" (0..3).each { i -> println "Choose ${i}:"; comb0(i, 5).each { println it }; println() }</lang>
Output:
Choose out of 5 (zero-based): Choose 0: [] Choose 1: [0] [1] [2] [3] [4] Choose 2: [0, 1] [0, 2] [0, 3] [0, 4] [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] Choose 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]
One-based Integers
<lang groovy>def comb1 = { m, n -> comb(m, (1..n)) }</lang>
Test program: <lang groovy>println "Choose out of 5 (one-based):" (0..3).each { i -> println "Choose ${i}:"; comb1(i, 5).each { println it }; println() }</lang>
Output:
Choose out of 5 (one-based): Choose 0: [] Choose 1: [1] [2] [3] [4] [5] Choose 2: [1, 2] [1, 3] [1, 4] [1, 5] [2, 3] [2, 4] [2, 5] [3, 4] [3, 5] [4, 5] Choose 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]
Haskell
It's more natural to extend the task to all (ordered) sublists of size m of a list.
Straightforward, unoptimized implementation with divide-and-conquer: <lang haskell>comb :: Int -> [a] -> a comb 0 _ = [[]] comb _ [] = [] comb m (x:xs) = map (x:) (comb (m-1) xs) ++ comb m xs</lang>
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.
To generate combinations of integers between 0 and n-1, use
<lang haskell>comb0 m n = comb m [0..n-1]</lang>
Similar, for integers between 1 and n, use
<lang haskell>comb1 m n = comb m [1..n]</lang>
J
Iteration
<lang j>comb1=: dyad define
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.
)</lang>
Recursion
<lang j>comb=: dyad define M.
if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x comb&.<: y),1+x comb y-1 end.
)</lang>
The M. uses memoization which greatly reduces the running time.
Java
<lang java5>import java.util.Collections; import java.util.LinkedList;
public class Comb{
public static void main(String[] args){
System.out.println(comb(3,5));
}
public static String bitprint(int u){
String s= "";
for(int n= 0;u > 0;++n, u>>= 1)
if((u & 1) > 0) s+= n + " ";
return s;
}
public static int bitcount(int u){
int n;
for(n= 0;u > 0;++n, u&= (u - 1));
return n;
}
public static LinkedList<String> comb(int c, int n){
LinkedList<String> s= new LinkedList<String>();
for(int u= 0;u < 1 << n;u++)
if(bitcount(u) == c) s.push(bitprint(u));
Collections.sort(s);
return s;
}
}</lang>
JavaScript
<lang javascript>function bitprint(u) {
var s=""; for (var n=0; u; ++n, u>>=1) if (u&1) s+=n+" "; return s;
} function bitcount(u) {
for (var n=0; u; ++n, u=u&(u-1)); return n;
} function comb(c,n) {
var s=[];
for (var u=0; u<1<<n; u++)
if (bitcount(u)==c)
s.push(bitprint(u))
return s.sort();
} comb(3,5)</lang>
Logo
<lang logo>to comb :n :list
if :n = 0 [output [[]]]
if empty? :list [output []]
output sentence map [sentence first :list ?] comb :n-1 bf :list ~
comb :n bf :list
end print comb 3 [0 1 2 3 4]</lang>
Lua
<lang 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 function combs(m, n)
if m * n == 0 then return {{}} end
local ret, old = {}, combs(m-1, n-1)
for i = 1, n do
for k, v in ipairs(old) do ret[#ret+1] = {i, map(incr(i), unpack(v))} end
end
return ret
end
for k, v in ipairs(combs(3, 5)) do print(unpack(v)) end</lang>
M4
<lang M4>divert(-1) define(`set',`define(`$1[$2]',`$3')') define(`get',`defn(`$1[$2]')') define(`setrange',`ifelse(`$3',`',$2,`define($1[$2],$3)`'setrange($1,
incr($2),shift(shift(shift($@))))')')
define(`for',
`ifelse($#,0,``$0, `ifelse(eval($2<=$3),1, `pushdef(`$1',$2)$4`'popdef(`$1')$0(`$1',incr($2),$3,`$4')')')')
define(`show',
`for(`k',0,decr($1),`get(a,k) ')')
define(`chklim',
`ifelse(get(`a',$3),eval($2-($1-$3)),
`chklim($1,$2,decr($3))',
`set(`a',$3,incr(get(`a',$3)))`'for(`k',incr($3),decr($2),
`set(`a',k,incr(get(`a',decr(k))))')`'nextcomb($1,$2)')')
define(`nextcomb',
`show($1)
ifelse(eval(get(`a',0)<$2-$1),1,
`chklim($1,$2,decr($1))')')
define(`comb',
`for(`j',0,decr($1),`set(`a',j,j)')`'nextcomb($1,$2)')
divert
comb(3,5)</lang>
MATLAB
This a built-in function in MATLAB called "nchoosek(n,k)". The argument "n" is a vector of values from which the combinations are made, and "k" is a scalar representing the amount of values to include in each combination.
Task Solution: <lang MATLAB>>> nchoosek((0:4),3)
ans =
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</lang>
OCaml
Like the Haskell code:
<lang ocaml>let rec comb m lst =
match m, lst with
0, _ -> [[]]
| _, [] -> []
| m, x :: xs -> List.map (fun y -> x :: y) (comb (pred m) xs) @
comb m xs
comb 3 [0;1;2;3;4];;</lang>
Octave
<lang octave>nchoosek([0:4], 3)</lang>
Oz
This can be implemented as a trivial application of finite set constraints: <lang oz>declare
fun {Comb M N}
proc {CombScript Comb}
%% Comb is a subset of [0..N-1]
Comb = {FS.var.upperBound {List.number 0 N-1 1}}
%% Comb has cardinality M
{FS.card Comb M}
%% enumerate all possibilities
{FS.distribute naive [Comb]}
end
in
%% Collect all solutions and convert to lists
{Map {SearchAll CombScript} FS.reflect.upperBoundList}
end
in
{Inspect {Comb 3 5}}</lang>
Perl
<lang perl>use Math::Combinatorics;
@n = (0 .. 4); print join("\n", map { join(" ", @{$_}) } combine(3, @n)), "\n";</lang>
PicoLisp
<lang PicoLisp>(de comb (M Lst)
(cond
((=0 M) '(NIL))
((not Lst))
(T
(append
(mapcar
'((Y) (cons (car Lst) Y))
(comb (dec M) (cdr Lst)) )
(comb M (cdr Lst)) ) ) ) )
(comb 3 (1 2 3 4 5))</lang>
Pop11
Natural recursive solution: first we choose first number i and then we recursively generate all combinations of m - 1 numbers between i + 1 and n - 1. Main work is done in the internal 'do_combs' function, the outer 'comb' just sets up variable to accumulate results and reverses the final result.
The 'el_lst' parameter to 'do_combs' contains partial combination (list of numbers which were chosen in previous steps) in reverse order.
<lang pop11>define comb(n, m);
lvars ress = [];
define do_combs(l, m, el_lst);
lvars i;
if m = 0 then
cons(rev(el_lst), ress) -> ress;
else
for i from l to n - m do
do_combs(i + 1, m - 1, cons(i, el_lst));
endfor;
endif;
enddefine;
do_combs(0, m, []);
rev(ress);
enddefine;
comb(5, 3) ==></lang>
PureBasic
<lang PureBasic>Procedure.s Combinations(amount, choose)
NewList comb.s()
; all possible combinations with {amount} Bits
For a = 0 To 1 << amount
count = 0
; count set bits
For x = 0 To amount
If (1 << x)&a
count + 1
EndIf
Next
; if set bits are equal to combination length
; we generate a String representing our combination and add it to list
If count = choose
string$ = ""
For x = 0 To amount
If (a >> x)&1
; replace x by x+1 to start counting with 1
String$ + Str(x) + " "
EndIf
Next
AddElement(comb())
comb() = string$
EndIf
Next
; now we sort our list and format it for output as string
SortList(comb(), #PB_Sort_Ascending)
ForEach comb()
out$ + ", [ " + comb() + "]"
Next
ProcedureReturn Mid(out$, 3)
EndProcedure
Debug Combinations(5, 3)</lang>
Python
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: <lang python>>>> from itertools import combinations >>> 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)]</lang>
Earlier versions could use a function like the following (
):
<lang python>def comb(m, lst):
if m == 0:
return [[]]
else:
return [[x] + suffix for i, x in enumerate(lst)
for suffix in comb(m - 1, lst[i + 1:])]</lang>
Example: <lang python>>>> comb(3, range(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]]</lang>
R
<lang R>print(combn(0:4, 3))</lang> Combinations are organized per column, so to provide an output similar to the one in the task text, we need the following: <lang R>r <- combn(0:4, 3) for(i in 1:choose(5,3)) print(r[,i])</lang>
Ruby
<lang ruby>def comb(m, n)
(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]]</lang>
Scala
<lang scala>implicit def toComb(m: Int) = new AnyRef {
def comb(n: Int) = recurse(m, List.range(0, n))
private def recurse(m: Int, l: List[Int]): List[List[Int]] = (m, l) match {
case (0, _) => List(Nil)
case (_, Nil) => Nil
case _ => (recurse(m - 1, l.tail) map (l.head :: _)) ::: recurse(m, l.tail)
}
}</lang>
Usage:
scala> 3 comb 5 res170: List[List[Int]] = List(List(0, 1, 2), List(0, 1, 3), List(0, 1, 4), List(0, 2, 3), List(0, 2, 4), List(0, 3, 4), List(1, 2, 3), List(1, 2, 4), List(1, 3, 4), List(2, 3, 4))
Scheme
Like the Haskell code: <lang scheme>(define (comb m lst)
(cond ((= m 0) '(()))
((null? lst) '())
(else (append (map (lambda (y) (cons (car lst) y))
(comb (- m 1) (cdr lst)))
(comb m (cdr lst))))))
(comb 3 '(0 1 2 3 4))</lang>
SETL
<lang SETL>print({0..4} npow 3);</lang>
Standard ML
<lang sml>fun comb (0, _ ) = [[]]
| comb (_, [] ) = []
| comb (m, x::xs) = map (fn y => x :: y) (comb (m-1, xs)) @
comb (m, xs)
comb (3, [0,1,2,3,4]);</lang>
Tcl
ref[1] <lang tcl>proc comb {m n} {
set set [list]
for {set i 0} {$i < $n} {incr i} {lappend set $i}
return [combinations $set $m]
} proc combinations {list size} {
if {$size == 0} {
return [list [list]]
}
set retval {}
for {set i 0} {($i + $size) <= [llength $list]} {incr i} {
set firstElement [lindex $list $i]
set remainingElements [lrange $list [expr {$i + 1}] end]
foreach subset [combinations $remainingElements [expr {$size - 1}]] {
lappend retval [linsert $subset 0 $firstElement]
}
}
return $retval
}
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}</lang>
Ursala
Most of the work is done by the standard library function choices, whose implementation is shown here for the sake of comparison with other solutions,
<lang Ursala>choices = ^(iota@r,~&l); leql@a^& ~&al?\&! ~&arh2fabt2RDfalrtPXPRT</lang>
where leql is the predicate that compares list lengths. The main body of the algorithm (~&arh2fabt2RDfalrtPXPRT) 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.
choices generates combinations of an arbitrary set but
not necessarily in sorted order, which can be done like this.
<lang Ursala>#import std
- import nat
combinations = @rlX choices^|(iota,~&); -< @p nleq+ ==-~rh</lang>
- The sort combinator (
-<) 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
@p. - The prefiltering operator
-~scans a list from the beginning until it finds the first item to falsify a predicate (in this case equality,==) and returns a pair of lists with the scanned items satisfying the predicate on the left and the remaining items on the right. - The
rhsuffix on the-~operator causes it to return only the head of the right list as its result, which in this case will be the first pair of unequal items in the list. - The
nleqfunction then tests whether the left side of this pair is less than or equal to the right. - The overall effect of using everything starting from the
@pas 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: <lang Ursala>#cast %nLL
example = combinations(3,5)</lang> output:
< <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>>
V
like scheme (using variables) <lang v>[comb [m lst] let
[ [m zero?] [[[]]]
[lst null?] [[]]
[true] [m pred lst rest comb [lst first swap cons] map
m lst rest comb concat]
] when].</lang>
Using destructuring view and stack not *pure at all <lang v>[comb
[ [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].</lang>
Pure concatenative version <lang v>[comb
[2dup [a b : a b a b] view]. [2pop pop pop].
[ [pop zero?] [2pop [[]]]
[null?] [2pop []]
[true] [2dup [pred] dip uncons swapd comb [cons] map popd rollup rest comb concat]
] when].</lang>
Using it
|3 [0 1 2 3 4] comb =[[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]]