# C++ combinations with repetition

## July 31, 2018

c++

algorithms

## A handy template function to generate all possible combinations of a set with repetition.

### Combinations

The STL provides some very handy functions for permutations, namely `next_permutation`

and `prev_permutation`

.

A combination is also a selection of items from a collection, but it differs from a permutation in that the order of the selection does not matter.

An SO user @mitchnull has posted a way to generate combinations using `std::prev_permutation`

here. Note that the code there generates combinations without repetition.

### Combinations with repetitions

A k-combination with repetitions, or k-multicombination, or multisubset of size k from a set S is given by a sequence of k not necessarily distinct elements of S, where order is not taken into account: two sequences define the same multiset if one can be obtained from the other by permuting the terms. In other words, the number of ways to sample k elements from a set of n elements allowing for duplicates (i.e., with replacement) but disregarding different orderings.

^{1}

I found this C code on SO and modified it for C++ to add a `for_each`

like interface.

```
#include <cmath>
template<typename V, typename Callable>
void for_each_combination(V &v, size_t gp_sz, Callable f) {
V gp(gp_sz);
auto total_n = std::pow(v.size(), gp.size());
for (auto i = 0; i < total_n; ++i) {
auto n = i;
for (auto j = 0ul; j < gp.size(); ++j) {
gp[gp.size() - j - 1] = v[n % v.size()];
n /= v.size();
}
f(gp);
}
}
```

#### Example

```
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {'a', 'b', 'd'};
for_each_combination(v, v.size(), [&](std::vector<int> &gp) {
for (auto c: gp)
std::cout << char(c) << " ";
std::cout << std::endl;
});
}
```

Output:

```
a a a
a a b
a a d
a b a
a b b
a b d
a d a
a d b
a d d
b a a
b a b
b a d
b b a
b b b
b b d
b d a
b d b
b d d
d a a
d a b
d a d
d b a
d b b
d b d
d d a
d d b
d d d
```