Combinations with repetitions is a computer algorithm that is primarily used in the field of probability and statistics. The algorithm is usually implemented to find all the possible combinations that can be made from a set of items when each item can be used more than once. This type of problem is often encountered in mining, physics, chemistry and other fields that rely on statistics to make decisions or predictions.
(* Combinations with repetitions *)
let rec combs_with_rep k xxs =
match k, xxs with
| 0, _ -> []
| _,  -> 
| k, x::xs ->
List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs)
@ combs_with_rep k xs
The Combinations with Repetitions algorithm is implemented in the programming language OCaml. The algorithm is recursive and uses pattern matching to break down the problem into smaller sub-problems.
- The function
combs_with_reptakes in two arguments:
kwhich is the size of the combination to be generated and
xxswhich is the list of items to be combined.
- The first step checks if
kis zero. If it is, an empty list is returned since there are no combinations of zero elements.
- The second step checks if
xxsis an empty list. If it is, an empty list is returned since there are no items to form a combination with.
- The third step breaks the list
xxsinto its head
xand its tail
- A recursive call is made to the function
combs_with_repwith one less element to select (
k-1) and the rest of the list of items as the second argument
xs. This gives us all the possible combinations of size
k-1that can be formed from the list
- The result of the recursive call is then mapped over using a lambda function that adds the element
xto the head of each sub-list. This generates all the possible combinations of size
kthat can be formed with
- The two lists of combinations formed in steps 5 and 6 are then concatenated to form the final list of combinations with repetitions of size
The time complexity of the Combinations with Repetitions algorithm can be approximated as O(n^k) where
n is the size of the list of items and
k is the size of the combination to be generated. This is because the algorithm generates all the possible combinations of size
k by recursively breaking the problem into smaller sub-problems and iterating over the entire list each time. The space complexity of the algorithm is also O(n^k) since it generates all the possible combinations before returning them as a list.