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.
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 ; static int wasBreak ; // previous version didn't _break_ int opApply(dg_type dg) { wasBreak = 0 ; return (msize <= nsize) ? combinate([], 0, msize, dg) : 0 ; } private int combinate(int[] fixed, int head, int left, dg_type dg) { if (!wasBreak) if(left <= 0) { foreach(i, ci ; fixed) cData[i] = cast(T)data[ci] ; wasBreak = dg(cData) ; } else { for(int i = head ; i <= nsize - left ; i++) combinate(fixed ~ [i], i + 1, left - 1, dg) ; } return wasBreak ; } } void main(string[] args) { foreach(cc ; Combinator!(int)(5, 3)) writefln(cc) ; foreach(cc ; Combinator!(string)(["zero ","one ","two ","three","four "].reverse, 3)) writefln(cc) ; }
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";