Combinations: Difference between revisions
Added Haskell example |
m →{{header|Haskell}}: Added type signature, improved aesthetics |
||
Line 25: | Line 25: | ||
Straightforward, unoptimized implementation with divide-and-conquer: |
Straightforward, unoptimized implementation with divide-and-conquer: |
||
<pre> |
|||
⚫ | |||
comb :: Int -> [a] -> [[a]] |
|||
comb 0 _ = [[]] |
|||
⚫ | |||
comb m (x:xs) = comb m xs ++ map (x:) (comb (m-1) xs) |
|||
</pre> |
|||
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. |
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. |
||
Line 33: | Line 36: | ||
To generate combinations of integers between 0 and ''n-1'', use |
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 |
Similar, for integers between 1 and ''n'', use |
||
comb1 m n = comb m [1..n] |
|||
=={{header|J}}== |
=={{header|J}}== |
Revision as of 21:53, 9 December 2007
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.