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 .

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.