# Combinations

Combinations
You are encouraged to solve this task according to the task description, using any language you may know.
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).

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.

The number of samples of size k from n objects.
With combinations and permutations generation tasks.
Order Unimportant Order Important
Without replacement $\binom nk = ^n\operatorname C_k = \frac{n(n-1)\ldots(n-k+1)}{k(k-1)\dots1}$ $^n\operatorname P_k = n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)$
With replacement $\binom {n+k+1}k = ^{n+k-1}\operatorname C_k = {(n+k+1)! \over (n+1)!k!}$ nk

## Contents

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


## ALGOL 68

Translation of: Python
Works with: ALGOL 68 version Revision 1 - one minor extension to language used - PRAGMA READ, similar to C's #include directive.
Works with: ALGOL 68G version Any - tested with release algol68g-2.6.
File: prelude_combinations.a68
# -*- coding: utf-8 -*- # COMMENT REQUIRED BY "prelude_combinations_generative.a68"  MODE COMBDATA = ~;PROVIDES:# COMBDATA*=~* ## comb*=~ list* #END COMMENT MODE COMBDATALIST = REF[]COMBDATA;MODE COMBDATALISTYIELD = PROC(COMBDATALIST)VOID; PROC comb gen combinations = (INT m, COMBDATALIST list, COMBDATALISTYIELD yield)VOID:(  CASE m IN  # case 1: transpose list #    FOR i TO UPB list DO yield(list[i]) OD  OUT    [m + LWB list - 1]COMBDATA out;    INT index out := 1;    FOR i TO UPB list DO      COMBDATA first = list[i];    # FOR COMBDATALIST sub recombination IN # comb gen combinations(m - 1, list[i+1:] #) DO (#,    ##   (COMBDATALIST sub recombination)VOID:(        out[LWB list   ] := first;        out[LWB list+1:] := sub recombination;        yield(out)    # OD #))    OD  ESAC); SKIP
File: test_combinations.a68
#!/usr/bin/a68g --script ## -*- coding: utf-8 -*- # CO REQUIRED BY "prelude_combinations.a68" CO  MODE COMBDATA = INT;#PROVIDES:## COMBDATA~=INT~ ## comb ~=int list ~#PR READ "prelude_combinations.a68" PR; FORMAT data fmt = $g(0)$; main:(  INT m = 3;  FORMAT list fmt = $"("n(m-1)(f(data fmt)",")f(data fmt)")"$;  FLEX[0]COMBDATA test data list := (1,2,3,4,5);# FOR COMBDATALIST recombination data IN # comb gen combinations(m, test data list #) DO (#,##    (COMBDATALIST recombination)VOID:(    printf ((list fmt, recombination, $l$))# OD # )))
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)


## 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 rend 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 trueend next_comb return comb(5, 3)
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}}

## 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   }}

## AWK

BEGIN {	## Default values for r and n (Choose 3 from pool of 5).  Can	## alternatively be set on the command line:-	## awk -v r=<number of items being chosen> -v n=<how many to choose from> -f <scriptname>	if (length(r) == 0) r = 3	if (length(n) == 0) n = 5 	for (i=1; i <= r; i++) { ## First combination of items:		A[i] = i		if (i < r ) printf i OFS		else print i} 	## While 1st item is less than its maximum permitted value...	while (A[1] < n - r + 1) {		## loop backwards through all items in the previous		## combination of items until an item is found that is		## less than its maximum permitted value:		for (i = r; i >= 1; i--) {			## If the equivalently positioned item in the			## previous combination of items is less than its			## maximum permitted value...			if (A[i] < n - r + i) {				## increment the current item by 1:				A[i]++				## Save the current position-index for use				## outside this "for" loop:				p = i				break}}		## Put consecutive numbers in the remainder of the array,		## counting up from position-index p.		for (i = p + 1; i <= r; i++) A[i] = A[i - 1] + 1 		## Print the current combination of items:		for (i=1; i <= r; i++) {			if (i < r) printf A[i] OFS			else print A[i]}}	exit}

Usage:

awk -v r=3 -v n=5 -f combn.awk


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


      INSTALL @lib$+"SORTLIB" sort% = FN_sortinit(0,0) M% = 3 N% = 5 C% = FNfact(N%)/(FNfact(M%)*FNfact(N%-M%)) DIM s$(C%)      PROCcomb(M%, N%, s$()) CALL sort%, s$(0)      FOR I% = 0 TO C%-1        PRINT s$(I%) NEXT END DEF PROCcomb(C%, N%, s$())      LOCAL I%, U%      FOR U% = 0 TO 2^N%-1        IF FNbits(U%) = C% THEN          s$(I%) = FNlist(U%) I% += 1 ENDIF NEXT ENDPROC DEF FNbits(U%) LOCAL N% WHILE U% N% += 1 U% = U% AND (U%-1) ENDWHILE = N% DEF FNlist(U%) LOCAL N%, s$      WHILE U%        IF U% AND 1 s$+= STR$(N%) + " "        N% += 1        U% = U% >> 1      ENDWHILE      = s$DEF FNfact(N%) IF N%<=1 THEN = 1 ELSE = N%*FNfact(N%-1)  ## Bracmat The program first constructs a pattern with m variables and an expression that evaluates m variables into a combination. Then the program constructs a list of the integers 0 ... n-1. The real work is done in the expression !list:!pat. When a combination is found, it is added to the list of combinations. Then we force the program to backtrack and find the next combination by evaluating the always failing ~. When all combinations are found, the pattern fails and we are in the rhs of the last | operator. (comb= bvar combination combinations list m n pat pvar var. !arg:(?m.?n) & ( pat = ? & !combinations (.!combination):?combinations & ~ ) & :?list:?combination:?combinations & whl ' ( !m+-1:~<0:?m & chu$(utf$a+!m):?var & glf$('(%@?.$var)):(=?pvar) & '(? ()$pvar ()$pat):(=?pat) & glf$('(!.$var)):(=?bvar) & ( '$combination:(=)            & '$bvar:(=?combination) | '($bvar ()$combination):(=?combination) ) ) & whl ' (!n+-1:~<0:?n&!n !list:?list) & !list:!pat | !combinations); 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)


## C

#include <stdio.h> /* Type marker stick: using bits to indicate what's chosen.  The stick can't * handle more than 32 items, but the idea is there; at worst, use array instead */typedef unsigned long marker;marker one = 1; void comb(int pool, int need, marker chosen, int at){	if (pool < need + at) return; /* not enough bits left */ 	if (!need) {		/* got all we needed; print the thing.  if other actions are		 * desired, we could have passed in a callback function. */		for (at = 0; at < pool; at++)			if (chosen & (one << at)) printf("%d ", at);		printf("\n");		return;	}	/* if we choose the current item, "or" (|) the bit to mark it so. */	comb(pool, need - 1, chosen | (one << at), at + 1);	comb(pool, need, chosen, at + 1);  /* or don't choose it, go to next */} int main(){	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.

#include <stdio.h> void comb(int m, int n, unsigned char *c){	int i;	for (i = 0; i < n; i++) c[i] = n - i; 	while (1) {		for (i = n; i--;)			printf("%d%c", c[i], i ? ' ': '\n'); 		/* this check is not strictly necessary, but if m is not close to n,		   it makes the whole thing quite a bit faster */		if (c[i]++ < m) continue; 		for (i = 0; c[i] >= m - i;) if (++i >= n) return;		for (c[i]++; i; i--) c[i-1] = c[i] + 1;	}} int main(){	unsigned char buf[100];	comb(5, 3, buf);	return 0;}

## C++

#include <algorithm>#include <iostream>#include <string> void comb(int N, int K){    std::string bitmask(K, 1); // K leading 1's    bitmask.resize(N, 0); // N-K trailing 0's     // print integers and permute bitmask    do {        for (int i = 0; i < N; ++i) // [0..N-1] integers        {            if (bitmask[i]) std::cout << " " << i;        }        std::cout << std::endl;    } while (std::prev_permutation(bitmask.begin(), bitmask.end()));} int main(){    comb(5, 3);}

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


## 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>();            stack.Push(0);             while (stack.Count > 0) {                int index = stack.Count - 1;                int value = stack.Pop();                 while (value < n) {                    result[index++] = value++;                    stack.Push(value);                    if (index == m) {                        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();        }    }}

Here is another implementation that uses recursion, intead of an explicit stack:

 using System;using System.Collections.Generic; public class Program{  public static IEnumerable<int[]> FindCombosRec(int[] buffer, int done, int begin, int end)  {    for (int i = begin; i < end; i++)    {      buffer[done] = i;       if (done == buffer.Length - 1)        yield return buffer;      else        foreach (int[] child in FindCombosRec(buffer, done+1, i+1, end))          yield return child;    }  }   public static IEnumerable<int[]> FindCombinations(int m, int n)  {    return FindCombosRec(new int[m], 0, 0, n);  }   static void Main()  {    foreach (int[] c in FindCombinations(3, 5))    {      for (int i = 0; i < c.Length; i++)      {        Console.Write(c[i] + " ");      }      Console.WriteLine();    }  }} 

## 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")))

## CoffeeScript

Basic backtracking solution.

 combinations = (n, p) ->  return [ [] ] if p == 0  i = 0  combos = []  combo = []  while combo.length < p    if i < n      combo.push i      i += 1    else      break if combo.length == 0      i = combo.pop() + 1     if combo.length == p      combos.push clone combo      i = combo.pop() + 1  combos clone = (arr) -> (n for n in arr) N = 5for i in [0..N]  console.log "------ #{N} #{i}"  for combo in combinations N, i    console.log combo  

output

> coffee combo.coffee ------ 5 0[]------ 5 1[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ]------ 5 2[ 0, 1 ][ 0, 2 ][ 0, 3 ][ 0, 4 ][ 1, 2 ][ 1, 3 ][ 1, 4 ][ 2, 3 ][ 2, 4 ][ 3, 4 ]------ 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 ]------ 5 4[ 0, 1, 2, 3 ][ 0, 1, 2, 4 ][ 0, 1, 3, 4 ][ 0, 2, 3, 4 ][ 1, 2, 3, 4 ]------ 5 5[ 0, 1, 2, 3, 4 ]  

## 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)

###  Recursive method

(defun comb (m list fn)  (labels ((comb1 (l c m)		  (when (>= (length l) m)		    (if (zerop m) (return-from comb1 (funcall fn c)))		    (comb1 (cdr l) c m)		    (comb1 (cdr l) (cons (first l) c) (1- m)))))    (comb1 list nil m))) (comb 3 '(0 1 2 3 4 5) #'print)

###  Alternate, iterative method

(defun next-combination (n a)    (let ((k (length a)) m)    (loop for i from 1 do        (when (> i k) (return nil))        (when (< (aref a (- k i)) (- n i))            (setf m (aref a (- k i)))            (loop for j from i downto 1 do                (incf m)                (setf (aref a (- k j)) m))            (return t))))) (defun all-combinations (n k)    (if (or (< k 0) (< n k)) '()        (let ((a (make-array k)))            (loop for i below k do (setf (aref a i) i))            (loop collect (coerce a 'list) while (next-combination n a))))) (defun map-combinations (n k fun)    (if (and (>= k 0) (>= n k))        (let ((a (make-array k)))            (loop for i below k do (setf (aref a i) i))            (loop do (funcall fun (coerce a 'list)) while (next-combination n a))))) ; all-combinations returns a list of lists > (all-combinations 4 3)((0 1 2) (0 1 3) (0 2 3) (1 2 3)) ; map-combinations applies a function to each combination > (map-combinations 6 4 #'print)(0 1 2 3)(0 1 2 4)(0 1 2 5)(0 1 3 4)(0 1 3 5)(0 1 4 5)(0 2 3 4)(0 2 3 5)(0 2 4 5)(0 3 4 5)(1 2 3 4)(1 2 3 5)(1 2 4 5)(1 3 4 5)(2 3 4 5)

## D

### Slow Recursive Version

Translation of: Python
T[][] comb(T)(in T[] arr, in int k) pure nothrow {    if (k == 0) return [[]];    typeof(return) result;    foreach (immutable i, immutable x; arr)        foreach (suffix; arr[i + 1 .. $].comb(k - 1)) result ~= x ~ suffix; return result;} void main() { import std.stdio; [0, 1, 2, 3].comb(2).writeln;} Output: [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]] ### More Functional Recursive Version Translation of: Haskell Same output. import std.stdio, std.algorithm, std.range; T[][] comb(T)(in T[] s, in int m) /*pure*/ nothrow { if (!m) return [[]]; if (s.empty) return []; return s[1 ..$].comb(m - 1).map!(x => s[0] ~ x).array ~         s[1 .. $].comb(m);} void main() { 4.iota.array.comb(2).writeln;} ### Fast lazy version module combinations3; ulong binomial(long n, long k) pure nothrowin { assert(n > 0, "binomial: n must be > 0.");} body { if (k < 0 || k > n) return 0; if (k > (n / 2)) k = n - k; ulong result = 1; foreach (ulong d; 1 .. k + 1) { result *= n; n--; result /= d; } return result;} struct Combinations(T, bool copy=true) { // Algorithm by Knuth, Pre-fascicle 3A, draft of // section 7.2.1.3: "Generating all partitions". T[] items; int k; size_t len = -1; // computed lazily this(in T[] items, in int k) in { assert(items.length, "combinations: items can't be empty."); } body { this.items = items.dup; this.k = k; } @property size_t length() /*logic_const*/ { if (len == -1) // set cache len = cast(size_t)binomial(items.length, k); return len; } int opApply(int delegate(ref T[]) dg) { if (k == items.length) return dg(items); // yield items auto outarr = new T[k]; if (k == 0) return dg(outarr); // yield [] if (k < 0 || k > items.length) return 0; // yield nothing int result, x; immutable n = items.length; auto c = new uint[k + 3]; // c[0] isn'k used foreach (j; 1 .. k + 1) c[j] = j - 1; c[k + 1] = n; c[k + 2] = 0; int j = k; while (true) { // The following lines equal to: //int pos; //foreach (i; 1 .. k +1) // outarr[pos++] = items[c[i]]; auto outarr_ptr = outarr.ptr; auto c_ptr = &(c[1]); auto c_ptrkp1 = &(c[k + 1]); while (c_ptr != c_ptrkp1) *outarr_ptr++ = items[*c_ptr++]; static if (copy) { auto outarr2 = outarr.dup; result = dg(outarr2); // yield outarr2 } else { result = dg(outarr); // yield outarr } if (j > 0) { x = j; c[j] = x; j--; continue; } if ((c[1] + 1) < c[2]) { c[1]++; continue; } else j = 2; while (true) { c[j - 1] = j - 2; x = c[j] + 1; if (x == c[j + 1]) j++; else break; } if (j > k) return result; // End c[j] = x; j--; } }} Combinations!(T,copy) combinations(bool copy=true, T) (in T[] items, in int k)in { assert(items.length, "combinations: items can't be empty.");} body { return Combinations!(T, copy)(items, k);} // compile with -version=combinations3_main to run mainversion(combinations3_main) void main() { import std.stdio, std.array; writeln(array(combinations([1, 2, 3, 4], 2)));} ### Lazy Lexicographical Combinations Includes an algorithm to find mth Lexicographical Element of a Combination. module combinations4;import std.stdio, std.algorithm, std.conv; ulong choose(int n, int k) nothrowin { assert(n >= 0 && k >= 0, "choose: no negative input.");} body { static ulong[][] cache; if (n < k) return 0; else if (n == k) return 1; while (n >= cache.length) cache ~= [1UL]; // = choose(m, 0); auto kmax = min(k, n - k); while(kmax >= cache[n].length) { immutable h = cache[n].length; cache[n] ~= choose(n - 1, h - 1) + choose(n - 1, h); } return cache[n][kmax];} int largestV(in int p, in int q, in long r) nothrowin { assert(p > 0 && q >= 0 && r >= 0, "largestV: no negative input.");} body { auto v = p - 1; while (choose(v, q) > r) v--; return v;} struct Comb { immutable int n, m; @property size_t length() const /*nothrow*/ { return to!size_t(choose(n, m)); } int[] opIndex(in size_t idx) const { if (m < 0 || n < 0) return []; if (idx >= length) throw new Exception("Out of bound"); ulong x = choose(n, m) - 1 - idx; int a = n, b = m; auto res = new int[m]; foreach (i; 0 .. m) { a = largestV(a, b, x); x = x - choose(a, b); b = b - 1; res[i] = n - 1 - a; } return res; } int opApply(int delegate(ref int[]) dg) const { int[] yield; foreach (i; 0 .. length) { yield = this[i]; if (dg(yield)) break; } return 0; } static auto On(T)(in T[] arr, in int m) { auto comb = Comb(arr.length, m); return new class { @property size_t length() const /*nothrow*/ { return comb.length; } int opApply(int delegate(ref T[]) dg) const { auto yield = new T[m]; foreach (c; comb) { foreach (idx; 0 .. m) yield[idx] = arr[c[idx]]; if (dg(yield)) break; } return 0; } }; }} version(combinations4_main) void main() { foreach (c; Comb.On([1, 2, 3], 2)) writeln(c); } ## 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) }  ## Erlang  -module(comb).-compile(export_all). comb(0,_) -> [[]];comb(_,[]) -> [];comb(N,[H|T]) -> [[H|L] || L <- comb(N-1,T)]++comb(N,T).  ## 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" } } ## 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 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5 ## GAP # Built-inCombinations([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 ] ] ## Go package main import ( "fmt") func main() { comb(5, 3, func(c []int) { fmt.Println(c) })} func comb(n, m int, emit func([]int)) { s := make([]int, m) last := m - 1 var rc func(int, int) rc = func(i, next int) { for j := next; j < n; j++ { s[i] = j if i == last { emit(s) } else { rc(i+1, j+1) } } return } rc(0, 0)} 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] ## Groovy Following the spirit of the Haskell solution. ### In General A recursive closure must be pre-declared. def combcomb = { 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] ### 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]

### 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] ## 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. Shorter version of the above: import Data.List (tails) 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 comb0 m n = comb m [0..n-1] Similar, for integers between 1 and n, use comb1 m n = comb m [1..n] Another method is to use the built in Data.List.subsequences function, filter for subsequences of length m and then sort:  import Data.List (sort, subsequences)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:

## 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.

>> 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

## Maxima

next_comb(n, p, a) := block(   [a: copylist(a), i: p],   if a[1] + p = n + 1 then return(und),   while a[i] - i >= n - p do i: i - 1,   a[i]: a[i] + 1,   for j from i + 1 thru p do a[j]: a[j - 1] + 1,   a)$combinations(n, p) := block( [a: makelist(i, i, 1, p), v: [ ]], while a # 'und do (v: endcons(a, v), a: next_comb(n, p, a)), v)$ combinations(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]] */

## 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];;

## Octave

nchoosek([0:4], 3)

## 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}  endin  {Inspect {Comb 3 5}}

## PARI/GP

c(n,k,r,d)={    if(d==k,        for(i=2,k+1,            print1(r[i]" "));        print    ,        for(i=r[d+1]+1,n,            r[d+2]=i;            c(n,k,r,d+1)));} c(5,3,vector(5,i,i-1),0)

## Pascal

Program Combinations; const m_max = 3; n_max = 5;var combination: array [1..m_max] of integer;  procedure generate(m: integer);  var   n, i: integer;  begin   if (m > m_max) then    begin    for i := 1 to m_max do     write (combination[i], ' ');    writeln;    end   else    for n := 1 to n_max do     if ((m = 1) or (n > combination[m-1])) then      begin       combination[m] := n;       generate(m + 1);      end;   end;  begin generate(1);end.

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


use Math::Combinatorics; @n = (0 .. 4);print join("\n", map { join(" ", @{$_}) } combine(3, @n)), "\n"; ## Perl5i Use a recursive solution, derived from the Perl6 (Haskell) solution • If we run out of eligable characters, we've gone too far, and won't find a solution along this path. • If we are looking for a single character, each character in @set is elegible, so return each as the single element of an array. • We have not yet reached the last character, so there are two possibilities: 1. push the first element of the set onto the front of an N-1 length combination from the remainder of the set. 2. skip the current element, and generate an N-length combination from the remainder The major Perl5i -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'.  use perl5i::2; # ----------------------------------------# generate combinations of length$n consisting of characters# from the sorted set @set, using each character once in a# combination, with sorted strings in sorted order.## Returns a list of array references, each containing one combination.#func combine($n, @set) { return unless @set; return map { [$_ ] } @set if $n == 1; my ($head) = shift @set;  my @result = combine( $n-1, @set ); for my$subarray ( @result ) {   $subarray->unshift($head );  }  return ( @result, combine( $n, @set ) );} say @$_ for combine( 3, ('a'..'e') );

Output

abc
abd
abe
acd
ace
bcd
bce
bde
cde


## Perl 6

The List class has a method that returns a list of all combinations. The only catch for now, is that we have to use .tree to get a list of Arrays.

.say for (^5).list.combinations(3).tree;
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

Here is a more explicit code, with the same output.

## 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:

>>> 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 functions 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]]
def comb(m, s):    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))

## Racket

 (define sublists  (match-lambda**   [(0 _)           '(())]   [(_ '())         '()]   [(m (cons x xs)) (append (map (curry cons x) (sublists (- m 1) xs))                             (sublists m xs))])) (define (combinations n m)  (sublists n (range m)))

Output:

> (combinations 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))


## 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])

## REXX

This REXX program supports up to 62 symbols (one symbol for each "thing").
It supports any number of "things" beyond the 62 symbols by using the actual number instead of a symbol.

/*REXX program shows combination sets for  X  things taken  Y  at a time*/@abc='abcdefghijklmnopqrstuvwxyz'; @abcU=@abc; upper @abcU; @digs=123456789parse arg x y symbols .;  if x=='' | x==',' then x=5                          if y=='' | y==',' then y=3if symbols=='' then symbols=@digs||@abc||@abcU    /*symbol table string.*/say "────────────" x 'things taken' y "at a time:"say "────────────" combN(x,y) 'combinations.'exit                                   /*stick a fork in it, we're done.*//*──────────────────────────────────COMBN subroutine────────────────────*/combN: procedure expose symbols;  parse arg x,y;   base=x+1;  bbase=base-y!.=0;           do i=1 for y;    !.i=i                end   /*i*/           do j=1;  L=;           do d=1 for y                                 L=L   word(substr(symbols,!.d,1)   !.d,1)                                 end   /*d*/          say L          !.y=!.y+1;   if !.y==base   then   if .combUp(y-1)   then leave          end         /*j*/return j .combUp: procedure expose !. y bbase;  parse arg d;  if d==0 then return 1p=!.d;        do u=d to y;     !.u=p+1              if !.u==bbase+u then return .combUp(u-1)              p=!.u              end     /*u*/return 0

output when the following was specified: 5 3 01234

──────────── 5 things taken 3 at a time:
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
──────────── 10 combinations.


output when the following was specified: 5 3 abcde

──────────── 5 things taken 3 at a time:
a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e
──────────── 10 combinations.


## Ruby

Works with: Ruby version 1.8.7+
def comb(m, n)  (0...n).to_a.combination(m).to_aend 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]]

## 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))


### Scala 2.9.x

Works with: Scala version 2.9.1
scala> (0 to 4 toList) combinations(3) toListres1: 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

(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))

## 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 rh suffix 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 nleq function 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 @p 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:

#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>>

## 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]]


## XPL0

code ChOut=8, CrLf=9, IntOut=11;def M=3, N=5;int A(N-1); proc Combos(D, S);      \Display all size M combinations of N in sorted orderint  D, S;              \depth of recursion, starting value of Nint  I;[if D<M then            \depth < size      for I:= S to N-1 do        [A(D):= I;        Combos(D+1, I+1);        ]else [for I:= 0 to M-1 do        [IntOut(0, A(I));  ChOut(0, ^ )];     CrLf(0);     ];]; Combos(0, 0)

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