Combinations: Difference between revisions
Content added Content deleted
(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}}== |
||