Combinations
Given non-negative integers m and n, generate all size m combinations of the integers from 0 to n-1 in sorted order (each combination is sorted and the entire table is sorted).
You are encouraged to solve this task according to the task description, using any language you may know.
For example, 3 comb 5 is
0 1 2 0 1 3 0 1 4 0 2 3 0 2 4 0 3 4 1 2 3 1 2 4 1 3 4 2 3 4
If it is more "natural" in your language to start counting from 1 instead of 0 the combinations can be of the integers from 1 to n.
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
This is an example of a library. You may see a list of other libraries used on Rosetta Code at Category:Solutions by Library.
use Math::Combinatorics; @n = (0 .. 4); print join("\n", map { join(" ", @{$_}) } combine(3, @n)), "\n";