Combinations

Given non-negative integers m and n, generate all size m combinations of the integers from 0 to n-1 in sorted order (each combination is sorted and the entire table is sorted).

For example, 3 comb 5 is

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.

D

Compiler: DMD 2.007

module cmbi;
import std.stdio;

class Combinator(T) {
	const(T)[] data ;
	T[] cData ;
	uint	nsize, msize ;
	
	static if (typeid(T) is typeid(int)) {
		static Combinator!(T) opCall(int n, int m) {
			if (n < 0) n = 0 ;
			int[] intdata = new int[n] ;
			for(int i = 0 ; i < n ; i++)
				intdata[i] = i ;
			return Combinator!(T)(intdata.idup, m) ;
		}
	}

	static Combinator!(T) opCall(const(T)[] d, int m) {
		return new Combinator!(T)(d, m) ;
	}

	private this(const(T)[] d, int m) {
		nsize = d.length ;
		msize = (m > 0) ? m : 0 ;	
		data = d ;
		cData.length = msize ;
	}
	
	alias int delegate(inout T[]) dg_type ;
	
	int opApply(dg_type dg) {
		if (msize <= nsize)
			combinate([], 0, msize, dg) ;
		return 0 ;
	}

	private void combinate(int[] fixed, int head, int left, dg_type dg) {		
		if(left <= 0) {
			foreach(i, ci ; fixed)
				cData[i] = cast(T)data[ci] ;
			dg(cData) ;
		} else {
			for(int i = head ; i <= nsize - left ; i++)
				combinate(fixed ~ [i], i + 1, left - 1, dg) ;
		}
	}
}

void main(string[] args) {
	foreach(cc ; Combinator!(int)(5, 3))
		writefln(cc) ;
	foreach(cc ; Combinator!(string)(["zero ","one  ","two  ","three","four "], 3))
		writefln("%s ",cc) ;
}

/***sample
D:\00MY\dmd>dmd cmbi
h:\dmd\bin\..\..\dm\bin\link.exe cmbi,,,user32+kernel32/noi;

D:\00MY\dmd>cmbi
[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]
[zero  one   two  ]
[zero  one   three]
[zero  one   four ]
[zero  two   three]
[zero  two   four ]
[zero  three four ]
[one   two   three]
[one   two   four ]
[one   three four ]
[two   three four ]
***/

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) = comb m xs ++ map (x:) (comb (m-1) xs)

In the induction step, either x is not in the result and the recursion proceeds with the rest of the list xs, or it is in the result and then we only need m-1 elements.

To generate combinations of integers between 0 and n-1, use

comb0 m n = comb m [0..n-1]

Similar, for integers between 1 and n, use

comb1 m n = comb m [1..n]

J

Iteration

comb1=: 4 : 0
 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.
)

Recursion

comb=: 4 : 0 M.
 if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x comb&.<: y),1+x comb y-1 end.
)

The M. uses memoization which greatly reduces the running time.

Perl

use Math::Combinatorics;

@n = (0 .. 4);
print join("\n", map { join(" ", @{$_}) } combine(3, @n)), "\n";