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.
See Also:
The number of samples of size k from n objects.
With combinations and permutations generation tasks.
Order Unimportant Order Important Without replacement Task: Combinations Task: Permutations With replacement Task: Combinations with repetitions Task: Permutations with repetitions
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.
- 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
File: prelude_combinations.a68<lang algol68># -*- 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</lang>File: test_combinations.a68<lang algol68>#!/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 # ))
) </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)
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:
{{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 <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>
AWK
<lang 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}</lang>
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
BBC BASIC
<lang bbcbasic> 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)
</lang>
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.
<lang bracmat>(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);</lang>
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
<lang 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; }</lang>
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. <lang c>#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; }</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>();
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();
}
}
}</lang>
Here is another implementation that uses recursion, intead of an explicit stack:
<lang csharp> 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();
}
}
} </lang>
C++
<lang cpp>#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);
}</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
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>
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.
<lang clojure> (defn combinations
"Generate the combinations of n elements from a list of [0..m)"
[m n]
(let [xs (range m)]
(loop [i (int 0) res #{#{}}]
(if (== i n)
res
(recur (+ 1 i)
(set (for [x xs r res
:when (not-any? #{x} r)]
(conj r x))))))))
</lang>
CoffeeScript
Basic backtracking solution. <lang coffeescript> 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 = 5 for i in [0..N]
console.log "------ #{N} #{i}"
for combo in combinations N, i
console.log combo
</lang>
- 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
<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>
- Output:
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
<lang lisp>(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)</lang>
Alternate, iterative method
<lang lisp>(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)</lang>
D
Slow Recursive Version
<lang d>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;
}</lang>
- Output:
[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
More Functional Recursive Version
Same output. <lang d>import std.stdio, std.algorithm, std.range;
immutable(int)[][] comb(immutable int[] s, in int m) pure nothrow @safe {
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;
}</lang>
Lazy Version
<lang d>module combinations3;
import std.traits: Unqual;
struct Combinations(T, bool copy=true) {
Unqual!T[] pool, front; size_t r, n; bool empty = false; size_t[] indices; size_t len; bool lenComputed = false;
this(T[] pool_, in size_t r_) pure nothrow @safe {
this.pool = pool_.dup;
this.r = r_;
this.n = pool.length;
if (r > n)
empty = true;
indices.length = r;
foreach (immutable i, ref ini; indices)
ini = i;
front.length = r;
foreach (immutable i, immutable idx; indices)
front[i] = pool[idx];
}
@property size_t length() /*logic_const*/ pure nothrow @nogc {
static size_t binomial(size_t n, size_t k) pure nothrow @safe @nogc
in {
assert(n > 0, "binomial: n must be > 0.");
} body {
if (k < 0 || k > n)
return 0;
if (k > (n / 2))
k = n - k;
size_t result = 1;
foreach (size_t d; 1 .. k + 1) {
result *= n;
n--;
result /= d;
}
return result;
}
if (!lenComputed) {
// Set cache.
len = binomial(n, r);
lenComputed = true;
}
return len;
}
void popFront() pure nothrow @safe {
if (!empty) {
bool broken = false;
size_t pos = 0;
foreach_reverse (immutable i; 0 .. r) {
pos = i;
if (indices[i] != i + n - r) {
broken = true;
break;
}
}
if (!broken) {
empty = true;
return;
}
indices[pos]++;
foreach (immutable j; pos + 1 .. r)
indices[j] = indices[j - 1] + 1;
static if (copy)
front = new Unqual!T[front.length];
foreach (immutable i, immutable idx; indices)
front[i] = pool[idx];
}
}
}
Combinations!(T, copy) combinations(bool copy=true, T)
(T[] items, in size_t k)
in {
assert(items.length, "combinations: items can't be empty.");
} body {
return typeof(return)(items, k);
}
// Compile with -version=combinations3_main to run main. version(combinations3_main) void main() {
import std.stdio, std.array, std.algorithm; [1, 2, 3, 4].combinations!false(2).array.writeln; [1, 2, 3, 4].combinations!true(2).array.writeln; [1, 2, 3, 4].combinations(2).map!(x => x).writeln;
}</lang>
Lazy Lexicographical Combinations
Includes an algorithm to find mth Lexicographical Element of a Combination. <lang d>module combinations4; import std.stdio, std.algorithm, std.conv;
ulong choose(int n, int k) nothrow in {
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) nothrow in {
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);
}</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) }
EchoLisp
<lang scheme>
- using the native (combinations) function
(lib 'list) (combinations (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))
- using an iterator
(lib 'sequences) (take (combinator (iota 5) 3) #:all) → ((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))
- defining a function
(define (combine lst p) (cond
[(null? lst) null]
[(< (length lst) p) null]
[(= (length lst) p) (list lst)]
[(= p 1) (map list lst)]
[else (append
(map cons (circular-list (first lst)) (combine (rest lst) (1- p)))
(combine (rest lst) p))]))
(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))
</lang>
Egison
<lang egison> (define $comb
(lambda [$n $xs]
(match-all xs (list integer)
[(loop $i [1 ,n] <join _ <cons $a_i ...>> _) a])))
(test (comb 3 (between 0 4))) </lang>
- Output:
{[|0 1 2|] [|0 1 3|] [|0 2 3|] [|1 2 3|] [|0 1 4|] [|0 2 4|] [|0 3 4|] [|1 2 4|] [|1 3 4|] [|2 3 4|]}
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. <lang Eiffel>
class COMBINATIONS
create make
feature
make (n, k: INTEGER) require n_positive: n > 0 k_positive: k > 0 k_smaller_equal: k <= n do create set.make set.extend ("") create sol.make sol := solve (set, k, n - k) sol := convert_solution (n, sol) ensure correct_num_of_sol: num_of_comb (n, k) = sol.count end
sol: LINKED_LIST [STRING]
feature {None}
set: LINKED_LIST [STRING]
convert_solution (n: INTEGER; solution: LINKED_LIST [STRING]): LINKED_LIST [STRING] -- strings of 'k' digits between 1 and 'n' local i, j: INTEGER temp: STRING do create temp.make (n) from i := 1 until i > solution.count loop from j := 1 until j > n loop if solution [i].at (j) = '1' then temp.append (j.out) end j := j + 1 end solution [i].deep_copy (temp) temp.wipe_out i := i + 1 end Result := solution end
solve (seta: LINKED_LIST [STRING]; one, zero: INTEGER): LINKED_LIST [STRING] -- list of strings with a number of 'one' 1s and 'zero' 0, standig for wether the corresponing digit is taken or not. local new_P1, new_P0: LINKED_LIST [STRING] do create new_P1.make create new_P0.make if one > 0 then new_P1.deep_copy (seta) across new_P1 as P1 loop new_P1.item.append ("1") end new_P1 := solve (new_P1, one - 1, zero) end if zero > 0 then new_P0.deep_copy (seta) across new_P0 as P0 loop new_P0.item.append ("0") end new_P0 := solve (new_P0, one, zero - 1) end if one = 0 and zero = 0 then Result := seta else create Result.make Result.fill (new_p0) Result.fill (new_p1) end end
num_of_comb (n, k: INTEGER): INTEGER -- number of 'k' sized combinations out of 'n'. local upper, lower, m, l: INTEGER do upper := 1 lower := 1 m := n l := k from until m < n - k + 1 loop upper := m * upper lower := l * lower m := m - 1 l := l - 1 end Result := upper // lower end
end </lang> Test: <lang Eiffel> class APPLICATION
create make
feature
make do create comb.make (5, 3) across comb.sol as ar loop io.put_string (ar.item.out + "%T") end end
comb: COMBINATIONS
end
</lang>
- Output:
345 245 235 234 145 135 134 125 124 123
Elena
<lang elena>#define system.
- define system'routines.
- define extensions.
- define extensions'routines.
- symbol(const)M = 3.
- symbol(const)N = 5.
// --- Numbers ---
- symbol numbers = (:anN)
[
Array new &length:(anN int) set &every: (&index:n) [ Integer new &int:n ]
].
// --- Program ---
- symbol program =
[
#var aNumbers := numbers:N.
Combinator new:M &of:aNumbers run &each: aRow
[
console writeLine:aRow.
].
].</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
Elixir
<lang elixir>defmodule RC do
def comb(0, _), do: [[]] def comb(_, []), do: [] def comb(m, [h|t]) do (for l <- comb(m-1, t), do: [h|l]) ++ comb(m, t) end
end
{m, n} = {3, 5} list = for i <- 1..n, do: i Enum.each(RC.comb(m, list), fn x -> IO.inspect x end)</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]
Erlang
<lang erlang> -module(comb). -compile(export_all).
comb(0,_) ->
[[]];
comb(_,[]) ->
[];
comb(N,[H|T]) ->
[[H|L] || L <- comb(N-1,T)]++comb(N,T).
</lang>
Dynamic Programming
Could be optimized with a custom zipwith/3 function instead of using lists:sublist/2.
<lang erlang> -module(comb). -export([combinations/2]).
combinations(K, List) ->
lists:last(all_combinations(K, List)).
all_combinations(K, List) ->
lists:foldr(
fun(X, Next) ->
Sub = lists:sublist(Next, length(Next) - 1),
Step = [[]] ++ [[[X|S] || S <- L] || L <- Sub],
lists:zipwith(fun lists:append/2, Step, Next)
end, [[[]]] ++ lists:duplicate(K, []), List).
</lang>
ERRE
<lang ERRE> PROGRAM COMBINATIONS
CONST M_MAX=3,N_MAX=5
DIM COMBINATION[M_MAX],STACK[100,1]
PROCEDURE GENERATE(M)
LOCAL I
IF (M>M_MAX) THEN
FOR I=1 TO M_MAX DO
PRINT(COMBINATION[I];" ";)
END FOR
PRINT
ELSE
FOR N=1 TO N_MAX DO
IF ((M=1) OR (N>COMBINATION[M-1])) THEN
COMBINATION[M]=N
! --- PUSH STACK -----------
STACK[SP,0]=M STACK[SP,1]=N
SP=SP+1
! --------------------------
GENERATE(M+1)
! --- POP STACK ------------
SP=SP-1
M=STACK[SP,0] N=STACK[SP,1]
! --------------------------
END IF
END FOR
END IF
END PROCEDURE
BEGIN
GENERATE(1)
END PROGRAM </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
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:
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
GAP
<lang gap># Built-in 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 ] ]</lang>
Go
<lang 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)
}</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]
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.
Shorter version of the above: <lang haskell>import Data.List (tails)
comb :: Int -> [a] -> a comb 0 _ = [[]] comb m l = [x:ys | x:xs <- tails l, ys <- comb (m-1) xs]</lang>
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>
Another method is to use the built in Data.List.subsequences function, filter for subsequences of length m and then sort:
<lang haskell>import Data.List (sort, subsequences) comb m n = sort . filter ((==m) . length) $ subsequences [0..n-1]</lang>
And yet another way is to use the list monad to generate all possible subsets:
<lang haskell>comb m n = filter ((==m . length) $ filterM (const [True, False]) [0..n-1]</lang>
Dynamic Programming
The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion. For example, comb m (x1:x2:xs) involves computing comb (m-1) (x2:xs) and comb m (x2:xs), both of which (separately) compute comb (m-1) xs. To avoid repeated computation, we can use dynamic programming:
<lang haskell>comb :: Int -> [a] -> a comb m xs = combsBySize xs !! m
where combsBySize = foldr f ([[]] : repeat []) f x next = zipWith (++) (map (map (x:)) ([]:next)) next</lang>
Icon and Unicon
<lang Icon>procedure main() return combinations(3,5,0) end
procedure combinations(m,n,z) # demonstrate combinations /z := 1
write(m," combinations of ",n," integers starting from ",z) every put(L := [], z to n - 1 + z by 1) # generate list of n items from z write("Intial list\n",list2string(L)) write("Combinations:") every write(list2string(lcomb(L,m))) end
procedure list2string(L) # helper function every (s := "[") ||:= " " || (!L|"]") return s end
link lists</lang>
The
provides the core procedure lcomb in lists written by Ralph E. Griswold and Richard L. Goerwitz.
<lang Icon>procedure lcomb(L,i) #: list combinations
local j
if i < 1 then fail
suspend if i = 1 then [!L]
else [L[j := 1 to *L - i + 1]] ||| lcomb(L[j + 1:0],i - 1)
end</lang>
- Output:
3 combinations of 5 integers starting from 0 Intial list [ 0 1 2 3 4 ] 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 ]
J
Library
<lang j>require'stats'</lang>
Example use:
<lang j> 3 comb 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>
All implementations here give that same result if given the same arguments.
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>combr=: dyad define M.
if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x combr&.<: y),1+x combr y-1 end.
)</lang>
The M. uses memoization (caching) which greatly reduces the running time. As a result, this is probably the fastest of the implementations here.
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. <lang j>combb=: (#~ ((-:/:~)>/:~-:\:~)"1)@(# #: [: i. ^~)</lang>
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));//Turn the last set bit to a 0
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
Imperative
<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>
Alternative recursive version using and an array of values instead of length:
<lang javascript>function combinations(arr, k){
var i,
subI,
ret = [],
sub,
next;
for(i = 0; i < arr.length; i++){
if(k === 1){
ret.push( [ arr[i] ] );
}else{
sub = combinations(arr.slice(i+1, arr.length), k-1);
for(subI = 0; subI < sub.length; subI++ ){
next = sub[subI];
next.unshift(arr[i]);
ret.push( next );
}
}
}
return ret;
} combinations([0,1,2,3,4], 3); // produces: [[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]]
combinations(["Crosby", "Stills", "Nash", "Young"], 3); // produces: [["Crosby", "Stills", "Nash"], ["Crosby", "Stills", "Young"], ["Crosby", "Nash", "Young"], ["Stills", "Nash", "Young"]] </lang>
Functional (ES 5)
Simple recursion:
<lang JavaScript>(function () {
function comb(n, lst) {
if (!n) return [[]];
if (!lst.length) return [];
var x = lst[0],
xs = lst.slice(1);
return comb(n - 1, xs).map(function (t) {
return [x].concat(t);
}).concat(comb(n, xs));
}
// [m..n]
function range(m, n) {
return Array.apply(null, Array(n - m + 1)).map(function (x, i) {
return m + i;
});
}
return comb(3, range(0, 4))
.map(function (x) {
return x.join(' ');
}).join('\n');
})();</lang>
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.
<lang JavaScript>(function (n) {
// n -> [a] -> a function comb(n, lst) { if (!n) return [[]]; if (!lst.length) return [];
var x = lst[0],
xs = lst.slice(1);
return comb(n - 1, xs).map(function (t) {
return [x].concat(t);
}).concat(comb(n, xs));
}
// f -> f
function memoized(fn) {
m = {};
return function (x) {
var args = [].slice.call(arguments),
strKey = args.join('-');
v = m[strKey];
if ('u' === (typeof v)[0])
m[strKey] = v = fn.apply(null, args);
return v;
}
}
// [m..n]
function range(m, n) {
return Array.apply(null, Array(n - m + 1)).map(function (x, i) {
return m + i;
});
}
var fnMemoized = memoized(comb), lstRange = range(0, 4);
return fnMemoized(n, lstRange)
.map(function (x) {
return x.join(' ');
}).join('\n');
})(3);</lang>
- Output:
<lang JavaScript>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>
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. <lang jq>def combination(r):
if r > length or r < 0 then empty
elif r == length then .
else ( [.[0]] + (.[1:]|combination(r-1))),
( .[1:]|combination(r))
end;
- select r integers from the set (0 .. n-1)
def combinations(n;r): [range(0;n)] | combination(r);</lang> Example 1
combinations(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]
Example 2
["a", "b", "c", "d", "e"] | combination(3) ] | length
- Output:
10
Julia
There is a built-in function combinations that 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.)
<lang julia>for i in combinations(1:5,3)
print(i')
end</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
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>
Maple
This is built-in in Maple: <lang Maple>> combinat:-choose( 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]]
</lang>
Mathematica
<lang Mathematica>combinations[n_Integer, m_Integer]/;m>= 0:=Union[Sort /@ Permutations[Range[0, n - 1], {m}]]</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>
Maxima
<lang 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]] */</lang>
Nim
<lang nim>iterator comb(m, n): seq[int] =
var c = newSeq[int](n) for i in 0 .. <n: c[i] = i
block outer:
while true:
yield c
var i = n-1
inc c[i]
if c[i] <= m - 1: continue
while c[i] >= m - n + i:
dec i
if i < 0: break outer
inc c[i]
while i < n-1:
c[i+1] = c[i] + 1
inc i
for i in comb(5, 3): echo i</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]
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>
Dynamic Programming solution: <lang ocaml>let comb m xs =
let xs = Array.of_list xs in
if m > Array.length xs then
[]
else begin
let arr = Array.make (m+1) [] in
arr.(0) <- [[]];
for j = 0 to Array.length xs - m do
for i = 1 to m do
arr.(i) <- arr.(i) @ List.map (fun ys -> xs.(j+i-1)::ys) arr.(i-1)
done
done;
arr.(m)
end
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>
PARI/GP
<lang parigp>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) </lang>
Pascal
<lang 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.</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
Perl
The ntheory module has a combinations iterator that runs in lexicographic order.
<lang perl>use ntheory qw/forcomb/; forcomb { print "@_\n" } 5,3</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
Algorithm::Combinatorics also does lexicographic order and can return the whole array or an iterator:
<lang perl>use Algorithm::Combinatorics qw/combinations/; my @c = combinations( [0..4], 3 ); print "@$_\n" for @c;</lang>
<lang perl>use Algorithm::Combinatorics qw/combinations/; my $iter = combinations([0..4],3); while (my $c = $iter->next) {
print "@$c\n";
}</lang>
Math::Combinatorics is another option but results will not be in lexicographic order as specified by the task.
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:
- push the first element of the set onto the front of an N-1 length combination from the remainder of the set.
- 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'. <lang Perl5i> 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') ); </lang>
- Output:
abc abd abe acd ace ade bcd bce bde cde
Perl 6
There actually is a builtin: <lang perl6>.say for combinations(5,3);</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
Here is an iterative routine with the same output: <lang perl6>sub combinations(Int $n, Int $k) {
return ([],) unless $k;
return if $k > $n || $n <= 0;
my @c = ^$k;
gather loop {
take [@c];
next if @c[$k-1]++ < $n-1;
my $i = $k-2;
$i-- while $i >= 0 && @c[$i] >= $n-($k-$i);
last if $i < 0;
@c[$i]++;
while ++$i < $k { @c[$i] = @c[$i-1] + 1; }
}
} .say for combinations(5,3);</lang>
Phix
It does not get much simpler or easier than this. See Sudoku for a practical application of this algorithm <lang Phix>procedure comb(integer pool, needed, done=0, sequence chosen={})
if needed=0 then -- got a full set
?chosen -- (or use a routine_id, result arg, or whatever)
return
end if
if done+needed>pool then return end if -- cannot fulfil
-- get all combinations with and without the next item:
done += 1
comb(pool,needed-1,done,append(chosen,done))
comb(pool,needed,done,chosen)
end procedure
comb(5,3)</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}
PicoLisp
<lang PicoLisp>(de comb (M Lst)
(cond
((=0 M) '(NIL))
((not Lst))
(T
(conc
(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>
Prolog
The solutions work with SWI-Prolog
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.
<lang prolog>:- use_module(library(clpfd)).
comb_clpfd(L, M, N) :-
length(L, M), L ins 1..N, chain(L, #<), label(L).</lang>
- Output:
?- comb_clpfd(L, 3, 5), writeln(L), fail. [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] false.
Another solution : <lang prolog>comb_Prolog(L, M, N) :-
length(L, M), fill(L, 1, N).
fill([], _, _).
fill([H | T], Min, Max) :-
between(Min, Max, H), H1 is H + 1, fill(T, H1, Max).
</lang> with the same output.
List comprehension
Works with SWI-Prolog, library clpfd from Markus Triska, and list comprehension (see List comprehensions ). <lang Prolog>:- use_module(library(clpfd)). comb_lstcomp(N, M, V) :- V <- {L & length(L, N), L ins 1..M & all_distinct(L), chain(L, #<), label(L)}. </lang>
- Output:
2?- comb_lstcomp(3, 5, V). V = [[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]] ; false.
Pure
<lang pure>comb m n = comb m (0..n-1) with
comb 0 _ = [[]]; comb _ [] = []; comb m (x:xs) = [x:xs | xs = comb (m-1) xs] + comb m xs;
end;
comb 3 5;</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
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: <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 functions like the following:
<lang python>def comb(m, lst):
if m == 0: return [[]]
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>
<lang python>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))</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>
Racket
<lang 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)))
</lang>
- 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))
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.
<lang rexx>/*REXX program shows combination sets for X things taken Y at a time*/
parse arg x y $ . /*get optional args from the C.L.*/
if x== | x==',' then x=5 /*X specified? No, use default.*/
if y== | y==',' then y=3 /*Y specified? No, use default.*/
@abc='abcdefghijklmnopqrstuvwxyz'; @abcU=@abc; upper @abcU
if $== then $=123456789||@abc||@abcU /*chars for 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 $; 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($,!.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 1 p=!.d; do u=d to y; !.u=p+1
if !.u==bbase+u then return .combUp(u-1)
p=!.u
end /*u*/
return 0</lang>
- Output:
when the following was specified
──────────── 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 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
<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>
Rust
<lang rust> fn comb<T: std::fmt::Default>(arr: &[T], n: uint) {
let mut incl_arr: ~[bool] = std::vec::from_elem(arr.len(), false); comb_intern(arr, n, incl_arr, 0);
}
fn comb_intern<T: std::fmt::Default>(arr: &[T], n: uint, incl_arr: &mut [bool], index: uint) {
if (arr.len() < n + index) { return; }
if (n == 0) {
let mut it = arr.iter().zip(incl_arr.iter()).filter_map(|(val, incl)|
if (*incl) { Some(val) } else { None }
);
for val in it { print!("{} ", *val); }
print("\n");
return;
}
incl_arr[index] = true; comb_intern(arr, n-1, incl_arr, index+1); incl_arr[index] = false;
comb_intern(arr, n, incl_arr, index+1);
}
fn main() {
let arr1 = ~[1, 2, 3, 4, 5]; comb(arr1, 3);
let arr2 = ~["A", "B", "C", "D", "E"]; comb(arr2, 3);
} </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))
Lazy version using iterators: <lang scala> def combs[A](n: Int, l: List[A]): Iterator[List[A]] = n match {
case _ if n < 0 || l.lengthCompare(n) < 0 => Iterator.empty
case 0 => Iterator(List.empty)
case n => l.tails.flatMap({
case Nil => Nil
case x :: xs => combs(n - 1, xs).map(x :: _)
})
}</lang>
Usage:
scala> combs(3, (0 to 4).toList).toList res0: 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))
Dynamic programming
Adapted from Haskell version: <lang scala> def combs[A](n: Int, xs: List[A]): Stream[List[A]] =
combsBySize(xs)(n)
def combsBySize[A](xs: List[A]): Stream[Stream[List[A]]] = {
val z: Stream[Stream[List[A]]] = Stream(Stream(List())) ++ Stream.continually(Stream.empty)
xs.toStream.foldRight(z)((a, b) => zipWith[Stream[List[A]]](_ ++ _, f(a, b), b))
}
def zipWith[A](f: (A, A) => A, as: Stream[A], bs: Stream[A]): Stream[A] = (as, bs) match {
case (Stream.Empty, _) => Stream.Empty
case (_, Stream.Empty) => Stream.Empty
case (a #:: as, b #:: bs) => f(a, b) #:: zipWith(f, as, bs)
}
def f[A](x: A, xsss: Stream[Stream[List[A]]]): Stream[Stream[List[A]]] = Stream.empty #:: xsss.map(_.map(x :: _))</lang>
Usage:
combs(3, (0 to 4).toList).toList res0: 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
<lang scala>scala> (0 to 4 toList) combinations(3) toList res1: 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)) </lang>
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>
Seed7
<lang seed7>$ include "seed7_05.s7i";
const type: combinations is array array integer;
const func combinations: comb (in array integer: arr, in integer: k) is func
result
var combinations: combResult is combinations.value;
local
var integer: x is 0;
var integer: i is 0;
var array integer: suffix is 0 times 0;
begin
if k = 0 then
combResult := 1 times 0 times 0;
else
for x key i range arr do
for suffix range comb(arr[succ(i) ..], pred(k)) do
combResult &:= [] (x) & suffix;
end for;
end for;
end if;
end func;
const proc: main is func
local
var array integer: aCombination is 0 times 0;
var integer: element is 0;
begin
for aCombination range comb([] (0, 1, 2, 3, 4), 3) do
for element range aCombination do
write(element lpad 3);
end for;
writeln;
end for;
end func;</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
SETL
<lang SETL>print({0..4} npow 3);</lang>
Sidef
<lang ruby>func combine(n, set) {
set.len || return [];
n == 1 && return set.map{[_]};
var (head, result); head = set.shift; result = __FUNC__(n-1, set.copy);
result.each { |subarray|
subarray.prepend(head);
};
result + __FUNC__(n, set);
}
combine(3, 0..4).each {|row|
say row.join(' ');
}</lang>
Smalltalk
<lang smalltalk> (0 to: 4) combinations: 3 atATimeDo: [ :x | Transcript cr; show: x printString].
"output on Transcript:
- (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>
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>
Swift
<lang Swift>func addCombo(prevCombo: [Int], var pivotList: [Int]) -> [([Int], [Int])] {
return (0..<pivotList.count)
.map {
_ -> ([Int], [Int]) in
(prevCombo + [pivotList.removeAtIndex(0)], pivotList)
}
} func combosOfLength(n: Int, m: Int) -> Int {
return [Int](1...m)
.reduce([([Int](), [Int](0..<n))]) {
(accum, _) in
accum.flatMap(addCombo)
}.map {
$0.0
}
}
println(combosOfLength(5, 3))</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]]
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>
TXR
TXR has repeating and non-repeating permutation and combination functions that produce lazy lists. They are generic over lists, strings and vectors. In addition, the combinations function also works over hashes.
Combinations and permutations are produced in lexicographic order (except in the case of hashes).
<lang txrlisp>(defun comb-n-m (n m)
(comb (range* 0 n) m))
(put-line `3 comb 5 = @(comb-n-m 5 3)`)</lang>
- Run:
$ 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))
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]]
VBScript
<lang vb> Function Dec2Bin(n) q = n Dec2Bin = "" Do Until q = 0 Dec2Bin = CStr(q Mod 2) & Dec2Bin q = Int(q / 2) Loop Dec2Bin = Right("00000" & Dec2Bin,6) End Function
Sub Combination(n,k) Dim arr() ReDim arr(n-1) For h = 0 To n-1 arr(h) = h + 1 Next Set list = CreateObject("System.Collections.Arraylist") For i = 1 To 2^n bin = Dec2Bin(i) c = 0 tmp_combo = "" If Len(Replace(bin,"0","")) = k Then For j = Len(bin) To 1 Step -1 If CInt(Mid(bin,j,1)) = 1 Then tmp_combo = tmp_combo & arr(c) & "," End If c = c + 1 Next list.Add Mid(tmp_combo,1,(k*2)-1) End If Next list.Sort For l = 0 To list.Count-1 WScript.StdOut.Write list(l) WScript.StdOut.WriteLine Next End Sub
'Testing with n = 5 / k = 3 Call Combination(5,3) </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
XPL0
<lang 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 order int D, S; \depth of recursion, starting value of N int 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)</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
zkl
<lang zkl>fcn comb(k,seq){ // no repeats, seq is finite
seq=seq.makeReadOnly(); // because I append to parts of seq
fcn(k,seq){
if(k<=0) return(T(T));
if(not seq) return(T);
self.fcn(k-1,seq[1,*]).pump(List,seq[0,1].extend)
.extend(self.fcn(k,seq[1,*]));
}(k,seq);
}</lang> <lang zkl>comb(3,"abcde".split("")).apply("concat")</lang>
- Output:
L("abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde")
- Programming Tasks
- Discrete math
- Ada
- ALGOL 68
- AppleScript
- AutoHotkey
- AWK
- BBC BASIC
- Bracmat
- C
- C sharp
- C++
- Clojure
- CoffeeScript
- Common Lisp
- D
- E
- EchoLisp
- Egison
- Eiffel
- Elena
- Elixir
- Erlang
- ERRE
- Factor
- Fortran
- GAP
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Icon Programming Library
- J
- Java
- JavaScript
- Jq
- Julia
- Logo
- Lua
- M4
- Maple
- Mathematica
- MATLAB
- Maxima
- Nim
- OCaml
- Octave
- Oz
- PARI/GP
- Pascal
- Perl
- Ntheory
- Perl5i
- Perl 6
- Phix
- PicoLisp
- Pop11
- Prolog
- Pure
- PureBasic
- Python
- R
- Racket
- REXX
- Ruby
- Rust
- Scala
- Scheme
- Seed7
- SETL
- Sidef
- Smalltalk
- Standard ML
- Swift
- Tcl
- TXR
- Ursala
- V
- VBScript
- XPL0
- Zkl