Combinations
From Rosetta Code
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.
[edit] 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;
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
type Five is range 0..4;
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
[edit] ALGOL 68
Translation of: python
Works with: ALGOL 68 version Standard - no extensions to language used
Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386
Works with: ELLA ALGOL 68 version Any (with appropriate job cards AND formatted transput statements removed) - tested with release 1.8.8d.fc9.i386
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#
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
[edit] AppleScript
on comb(n, k)Output:
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)
{{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}}
[edit] AutoHotkey
contributed by Laszlo on the ahk forum
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
}
}
[edit] 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;
}
[edit] C#
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();
}
}
}
[edit] 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")))
[edit] Common 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))))
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)
[edit] D
Includes an algorithm to find mth Lexicographical Element of a Combination.
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]) ;
}
Slow recursive version based on the Python one:
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));
}
[edit] 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)
}
}
}
}
}
}
? for x in combinations(3, 0..4) { println(x) }
[edit] Factor
USING: math.combinatorics prettyprint ;
5 iota 3 all-combinations .
{
{ 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:
{ "a" "b" "c" } 2 all-combinations .
{ { "a" "b" } { "a" "c" } { "b" "c" } }
[edit] 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
Alternatively:
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
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
[edit] Groovy
Following the spirit of the Haskell solution.
[edit] In General
A recursive closure must be pre-declared.
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 }
}
}
Test program:
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() }
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]
[edit] Zero-based Integers
def comb0 = { m, n -> comb(m, (0..<n)) }
Test program:
println "Choose out of 5 (zero-based):"
(0..3).each { i -> println "Choose ${i}:"; comb0(i, 5).each { println it }; println() }
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]
[edit] One-based Integers
def comb1 = { m, n -> comb(m, (1..n)) }
Test program:
println "Choose out of 5 (one-based):"
(0..3).each { i -> println "Choose ${i}:"; comb1(i, 5).each { println it }; println() }
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]
[edit] 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:
comb :: Int -> [a] -> [[a]]
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.
To generate combinations of integers between 0 and n-1, use
comb0 m n = comb m [0..n-1]
Similar, for integers between 1 and n, use
comb1 m n = comb m [1..n]
[edit] J
[edit] Iteration
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.
)
[edit] Recursion
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.
)
The M. uses memoization which greatly reduces the running time.
[edit] Java
Translation of: JavaScript
Works with: Java version 1.5+
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;
}
}
[edit] 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)
[edit] 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]
[edit] 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
[edit] 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)
[edit] 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:
>> 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
[edit] OCaml
Like the Haskell code:
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];;
[edit] Octave
nchoosek([0:4], 3)
[edit] Oz
This can be implemented as a trivial application of finite set constraints:
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}}
[edit] Perl
Library: Math::CombinatoricsCombinatoricswarning.pngUnsupported type "" defined for property.
use Math::Combinatorics;
@n = (0 .. 4);
print join("\n", map { join(" ", @{$_}) } combine(3, @n)), "\n";
[edit] PicoLisp
Translation of: Scheme
(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))
[edit] 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.
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) ==>
[edit] 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)
[edit] 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:
>>> 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)]
Earlier versions could use a function like the following (Translation of: E):
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:])]
Example:
>>> 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]]
[edit] R
print(combn(0:4, 3))
Combinations are organized per column, so to provide an output similar to the one in the task text, we need the following:
r <- combn(0:4, 3)
for(i in 1:choose(5,3)) print(r[,i])
[edit] Ruby
Works with: Ruby version 1.8.7+
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]]
[edit] 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)
}
}
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))
[edit] Scheme
Like the Haskell code:
(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))
[edit] SETL
print({0..4} npow 3);
[edit] Standard ML
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]);
[edit] Tcl
ref[1]
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}
[edit] 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,
choices = ^(iota@r,~&l); leql@a^& ~&al?\&! ~&arh2fabt2RDfalrtPXPRT
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.
#import std
#import nat
combinations = @rlX choices^|(iota,~&); -< @p nleq+ ==-~rh
- 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:
#cast %nLL
example = combinations(3,5)
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>>
[edit] V
like scheme (using variables)
[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].
Using destructuring view and stack not *pure at all
[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].
Pure concatenative version
[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].
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]]
Categories: Programming Tasks | Discrete math | Ada | ALGOL 68 | AppleScript | AutoHotkey | C | C sharp | Clojure | Common Lisp | D | E | Factor | Fortran | Groovy | Haskell | J | Java | JavaScript | Logo | Lua | M4 | MATLAB | OCaml | Octave | Oz | Perl | PicoLisp | Pop11 | PureBasic | Python | R | Ruby | Scala | Scheme | SETL | Standard ML | Tcl | Ursala | V
