Motivation and terminology
Synopsis
Function templates description (next_partial_permutation, prev_partial_permutation, next_combination, prev_combination,
next_mapping, prev_mapping, next_combination_counts, prev_combination_counts)
Definition
Example (next_partial_permutation, next_combination, next_mapping, next_combination_counts)
Rationale
Acknowledgements
The combination library is composed of a single header, <boost/algorithm/combination.hpp>. The problem solved by this library is to enumerate all the subsequences of a prescribed size from a given size from a sequence of elements, ordered or not, with or without repetitions. This seems to be an oft requested feature, although the solutions have varying degrees of difficulty.
Terminology. In this library, we follow accepted terminology (e.g., the combinatorics article from Wikipedia) and call permutations the subsequences when order matters, and combinations those subsequences where order does not matter. Formally:
Illustration. For instance, given a ground set {1, 2, 3, 4, 5} of five elements, the following are examples of:
{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 2}, {1, 3, 4}, {1, 3, 5},
{1, 4, 2}, {1, 4, 3}, {1, 4, 5}, {1, 5, 2}, {1, 5, 3}, {1, 5, 4},
{2, 1, 3}, {2, 1, 4}, {2, 1, 5}, {2, 3, 1}, {2, 3, 4}, {2, 3, 5},
{2, 4, 1}, {2, 4, 3}, {2, 4, 5}, {2, 5, 1}, {2, 5, 3}, {2, 5, 4},
{3, 1, 2}, {3, 1, 4}, {3, 1, 5}, {3, 2, 1}, {3, 2, 4}, {3, 2, 5},
{3, 4, 1}, {3, 4, 2}, {3, 4, 5}, {3, 5, 1}, {3, 5, 2}, {3, 5, 4},
{4, 1, 2}, {4, 1, 3}, {4, 1, 5}, {4, 2, 1}, {4, 2, 3}, {4, 2, 5},
{4, 3, 1}, {4, 3, 2}, {4, 3, 5}, {4, 5, 1}, {4, 5, 2}, {4, 5, 3},
{5, 1, 2}, {5, 1, 3}, {5, 1, 4}, {5, 2, 1}, {5, 2, 3}, {5, 2, 4},
{5, 3, 1}, {5, 3, 2}, {5, 3, 4}, {5, 4, 1}, {5, 4, 2}, {5, 4, 3}.
Here, there are 60 of them. In general, there are
P(n,r)=(n)r=n!/(n-r)! permutations of size r out of
n elements. (These numbers are sometimes called the
permutation numbers, or falling factorials.)
{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5},
{1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}.
Here, there are just 10 of them. In general, there are
C(n,r)=(nr)=n!/(r!*(n-r)!) permutations of size r out of
n elements. (These numbers are known as
binomial coefficients.)
{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5},
{2, 1}, {2, 2}, {2, 3}, {2, 4}, {2, 5},
{3, 1}, {3, 2}, {3, 3}, {3, 4}, {3, 5},
{4, 1}, {4, 2}, {4, 3}, {4, 4}, {4, 5},
{5, 1}, {5, 2}, {5, 3}, {5, 4}, {5, 5}.
Here, there are 25 of them. In general, there are
nr mappings from r positions to a set of
n elements.
{1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 2, 2}, {1, 2, 3},
{1, 3, 3}, {2, 2, 2}, {2, 2, 3}, {2, 3, 3}, {3, 3, 3}.
Here, there are just 10 of them. In general, there are
Cn-1n+r-1=<nr>=(n+r-1)!/(r!*(n-1)!) combinations of size
r, with repetitions, out of n elements. (These numbers are
known as multiset coefficients.)Without repetitions. Without repetitions, r is specified by a middle position in the input range [first, last) which is r positions away from first. The permutation or combination is therefore expressed by the range [first, middle).
It turns out it is very easy to enumerate permutations without repetitions, in lexicographic order, and we supply algorithms next_partial_permutation and prev_partial_permutation for this purpose.
Unlike permutations, combinations enumerate subsets and therefore require sorting. Typically, one starts with a sorted sequence, and the pre-condition invariants are maintained by next_combination and prev_combination. As their counterparts std::next_permutation and std::prev_permutation, both algorithms next_combination and prev_combination return false when they reach the end of combinations, and return the range to its original sorted state. Note that there is only one combination of size n (i.e., the sorted range), so there is no need to follow symmetry and name those functions next_partial_combination and prev_partial_combination
Like standard permutations, our permutations and combinations do not require all the elements of a sequence to be unique. Note that in the presence of elements that compare equal for the ordering, combinations corresponding to distinct set of indices may compare equal. When all elements compare equal, there is a single permutation and a single combination for each size.
Note that it is also very simple to enumerate permutations without repetition uniquely once combinations can be enumerated: starting from the ascendingly sorted sequence, simply apply std::next_permutation repeatedly, starting from each combination, until getting back to that combination and then applying next_combination, until all combinations have been exhausted. (Note that the cycles std::next_permutation may vary in length in the presence of equal elements.) The enumeration ordering is however not in lexicographic order, so prefer next_partial_permutation and prev_partial_permutation for that.
With repetitions. With repetitions, however, it suffices to provide algorithms that operate on a sequence of positions into the input range [first, last). In fact, in that case, since we can repeat elements, it does not matter how many copies of the elements are in the input range, and we may as well assume that they are unique. In that case, the values in the input range do not matter and the algorithms operate on a range of positions (which can be iterators into some input range, or integers, or any type that supports operator== and operator++; note the absence of requirement for operator*).
Miscellaneous There are other meanings of combinations. However, one finds that such cases can usually be handled by a "combination" (pun intended) of next_mapping, next_combination, and other exisiting standard algorithms. For instance, requiring all combinations of size r without repetitions from a range of size n in which all elements are unique (even though the elements in the range may not be) is no different from first removing all duplicates (using std::unique) and, if the resulting size is m ≥ r, enumerating all the permutations of r elements out of these m unique elements.
#include <algorithm> // used in the implementation
namespace boost {
// Partial permutations (without repetitions)
template <class BidirectionalIterator>
bool
next_partial_permutation(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template <class BidirectionalIterator, class StrictWeakOrdering>
bool
next_partial_permutation(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, StrictWeakOrdering comp);
template <class BidirectionalIterator>
bool
prev_partial_permutation(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template <class BidirectionalIterator, class StrictWeakOrdering>
bool
prev_partial_permutation(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, StrictWeakOrdering comp);
// Combinations (without repetitions)
template <class BidirectionalIterator>
bool
next_combination(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template <class BidirectionalIterator, class StrictWeakOrdering>
bool
next_combination(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, StrictWeakOrdering comp);
template <class BidirectionalIterator>
bool
prev_combination(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template <class BidirectionalIterator, class StrictWeakOrdering>
bool
prev_combination(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, StrictWeakOrdering comp);
// Mappings (permutations with repetitions)
template <class BidirectionalIterator, class T>
bool
next_mapping(BidirectionalIterator first,
BidirectionalIterator last,
T first_value, T last_value);
template <class BidirectionalIterator, class T, class Incrementor>
bool
next_mapping(BidirectionalIterator first,
BidirectionalIterator last,
T first_value, T last_value, Incrementor increment);
template <class BidirectionalIterator, class T>
bool
prev_mapping(BidirectionalIterator first,
BidirectionalIterator last,
T first_value, T last_value);
template <class BidirectionalIterator, class T, class Decrementor>
bool
prev_mapping(BidirectionalIterator first,
BidirectionalIterator last,
T first_value, T last_value, Decrementor decrement);
// Combination counts (combinations with repetitions)
template <class BidirectionalIterator>
bool
next_combination_counts(BidirectionalIterator first,
BidirectionalIterator last);
template <class BidirectionalIterator>
bool
prev_combination_counts(BidirectionalIterator first,
BidirectionalIterator last);
}
template <class BidirectionalIterator>
bool
next_partial_permutation(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template <class BidirectionalIterator, class StrictWeakOrdering>
bool
next_partial_permutation(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, StrictWeakOrdering comp);
Effects: next_partial_permutation takes a sequence defined by the range [first,last) and permutes it so that [first, middle) stores the next partial permutation of the same size from [first, last), i.e., a permutation of some subsequence of this size from [first, last), and [middle, last) is sorted. The next partial permutation is found by assuming that the set of all partial permutations of a given size from [first, last) is lexicographically sorted with respect to operator< or comp. If the next partial permutation does not exist, it transforms [first, middle) into the smallest partial permutation, leaving the entire range sorted.
Returns: true if the next partial permutation exists, false otherwise.
Requires: The type of first shall satisfy the Swappable requirements (Table 37). The range [middle, last) shall be sorted in ascending order.
Post-condition: is_sorted(middle, last) or is_sorted(middle, last, comp).
Complexity: At most (last - first) comparisons and (last - first) swaps.
Remarks: Upon returning false, [first, middle) is back to the smallest partial permutation, that is, the prefix of the ascendingly sorted range, and the requirements met for another application of next_partial_permutation.
[Note: in order to prepare the range [first, last) for an enumeration of all partial permutations in lexicographic order, simply sort(first, last) or sort(first, last, comp). For an enumeration in reverse lexicographic order, additionally std::reverse(first, last) followed by std::reverse(middle, last). -- End note]
template <class BidirectionalIterator>
bool
prev_partial_permutation(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template <class BidirectionalIterator, class StrictWeakOrdering>
bool
prev_partial_permutation(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, StrictWeakOrdering comp);
Effects: prev_partial_permutation takes a sequence defined by the range [first,last) and permutes it so that [first, middle) stores the previous partial permutation of the same size from [first, last), i.e., a permutation of some subsequence of this size from [first, last), and [middle, last) is sorted. The previous partial permutation is found by assuming that the set of all partial permutations of a given size from [first, last) is lexicographically sorted with respect to operator< or comp. If such a subsequence does not exist, it sorts the entire range in reverse order and then applies std::reverse(middle, last).
Returns: true if the previous partial permutation exists, false otherwise.
Requires: The type of first shall satisfy the Swappable requirements (Table 37). The range [middle, last) shall be sorted in ascending order.
Post-condition: is_sorted(middle, last) or is_sorted(middle, last, comp)
Complexity: At most (last - first) comparisons and (last - first) swaps.
Remarks: Upon returning false, [first, middle) is back to the largest partial permutation, that is, the prefix of the descendingly sorted range, and the requirements met for another application of prev_partial_permutation.
[Note: in order to prepare the range [first, last) for an enumeration of partial permutations in lexicographic order, simply sort(first, last) or sort(first, last, comp). For an enumeration in reverse lexicographic order, additionally std::reverse(first, last) followed by std::reverse(middle, last). -- End note]
template <class BidirectionalIterator>
bool
next_combination(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template <class BidirectionalIterator, class StrictWeakOrdering>
bool
next_combination(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, StrictWeakOrdering comp);
Effects: next_combination takes a sequence defined by the range [first,last) and permutes it so that [first, middle) stores the next combination (i.e., sorted subsequence) of the same size from [first, last), and [middle, last) is sorted. The next combination is found by assuming that the set of all combinations of a given size from [first, last) is lexicographically sorted with respect to operator< or comp. If the next combination does not exist, it transforms [first, middle) into the smallest combination, leaving the entire range sorted.
Returns: true if the next combination exists, false otherwise.
Requires: The type of *first shall satisfy the Swappable requirements (Table 37). The ranges [first, middle) and [middle, last) shall both be sorted in ascending order.
Post-condition: is_sorted(first, middle) && is_sorted(middle, last) or is_sorted(first, middle, comp) && is_sorted(middle, last, comp).
Complexity: At most (last - first) comparisons and (last - first) swaps.
Remarks: Upon returning false, [first, middle) is back to the smallest combination, that is, the prefix of the ascendingly sorted range, and the requirements met for another application of next_combination.
[Note: in order to prepare the range [first, last) for an enumeration in lexicographic order, simply sort(first, last) or sort(first, last, comp). For an enumeration in reverse lexicographic order, additionally std::reverse(first, last) followed by std::reverse(first, middle) and std::reverse(middle, last). -- End note]
template <class BidirectionalIterator>
bool
prev_combination(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template <class BidirectionalIterator, class StrictWeakOrdering>
bool
prev_combination(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, StrictWeakOrdering comp);
Effects: prev_combination takes a sequence defined by the range [first,last) and permutes it so that [first, middle) stores the previous combination of the same size from [first, last) and [middle, last) is sorted. The previous sorted subsequence is found by assuming that the set of all sorted subsequences of a given size is lexicographically sorted with respect to operator< or comp. If such a subsequence exists, it returns true. Otherwise, it transforms the sorted subsequence in the range [first, middle) into the largest sorted subsequence, leaving [middle, last) also sorted, and returns false.
Returns: true if the next combination exists, false otherwise.
Requires: The type of first shall satisfy the Swappable requirements (Table 37). The ranges [first, middle) and [middle, last) shall both be sorted.
Post-condition: is_sorted(first, middle) && is_sorted(middle, last) or is_sorted(first, middle, comp) && is_sorted(middle, last, comp).
Complexity: At most (last - first) comparisons and (last - first) swaps.
Remarks: upon returning false, the sorted subsequence is back to the largest sorted subsequence, and the requirements met for another application of next_combination.
[Note: in order to prepare the range [first, last) for an enumeration in lexicographic order, simply sort(first, last) or sort(first, last, comp). For an enumeration in reverse lexicographic order, additionally std::reverse(first, last) followed by std::reverse(first, middle) and std::reverse(middle, last). -- End note]
template <class BidirectionalIterator, class T>
bool
next_mapping(BidirectionalIterator first,
BidirectionalIterator last,
T first_value, T last_value);
template <class BidirectionalIterator, class T, class Incrementor>
bool
next_mapping(BidirectionalIterator first,
BidirectionalIterator last,
T first_value, T last_value, Incrementor increment);
Effects: next_mapping takes a sequence defined by the range [first,last), where each value in this range belongs to the range [first_value,last_value), and transforms this sequence into the next assignment of values (mapping). The next assignment of values is found by assuming that the set of all assignments is lexicographically sorted with respect to the values in the range [first_value, last_value). If such an assignment exists, it returns true. Otherwise, it transforms the assignment into the lexicographically smallest assignment, that is, each value in [first,last) equals first_value, and returns false.
Returns: true if the next assignment exists, false otherwise.
Requires: T shall meet the requirements of CopyConstructible (34) and Assignable (23.1) types. In the first from, T shall have an operator++; in the second form, Incrementor shall meet the requirements of CopyConstructible (34) types and last_value shall be reachable from first_value by a finite positive number of applications of Incrementor::operator(T&). In particular, the range [first_value,last_value) shall not be empty.
Complexity: At most (last - first) decrements of BidirectionalIterator and (last - first) increments of T.
template <class BidirectionalIterator, class T>
bool
prev_mapping(BidirectionalIterator first,
BidirectionalIterator last,
T first_value, T last_value);
template <class BidirectionalIterator, class T, class Decrementor>
bool
prev_mapping(BidirectionalIterator first,
BidirectionalIterator last,
T first_value, T last_value, Decrementor decrement);
Effects: prev_mapping takes a sequence defined by the range [first,last), where each value in this range belongs to the range [first_value, last_value), and transforms this sequence into the previous assignment of values (mapping). The previous assignment of values is found by assuming that the set of all assignments is lexicographically sorted with respect to the values in the range [first_value, last_value). If such an assignment does not exist, it transforms the assignment into the lexicographically largest assignment, that is, each value in [first, last) equals --last_value.
Returns: true if the previous mapping exists, false otherwise.
Requires: T shall meet the requirements of CopyConstructible (34) and Assignable (23.1) types. In the first from, T shall have an operator--; in the second form, Decrement shall meet the requirements of CopyConstructible (34) types, and first_value shall be reachable from last_value by a finite positive number of applications of decrement(last_value). In particular, the range [first_value, last_value) shall not be empty.
Complexity: At most (last - first) decrements of BidirectionalIterator and (last - first) decrements of T.
template <class BidirectionalIterator, class T>
bool
next_combination_counts(BidirectionalIterator first,
BidirectionalIterator last);
template <class BidirectionalIterator, class T>
bool
prev_combination_counts(BidirectionalIterator first,
BidirectionalIterator last);
Effects: next_combination_counts (resp., prev_combination_counts) takes a sequence defined by the range [first,last), where each value in this range is a multiplicity (count) of some integral type T (the type of *first) and the sum of these multiplicities equals total_size, and transforms this sequence of multiplicities into the next (resp., previous) assignment of multiplicities of the same total_size. The next (resp., previous) assignment of multiplicities is found by assuming that the set of all assignments of multiplicities whose sums equal total_size is lexicographically sorted with respect to operator< of T. If such an assignment exists, it returns true. Otherwise, it transforms the multiplicities into the lexicographically smallest (resp. largest) assignment of multiplicities, that is, 0 for everyone in the range [first, last) except total_size for the last (resp., first) position in that range (if any), and returns false.
Returns: true if the next (resp., previous) combination counts exist, false otherwise.
Requires: The value type of BidirectionalIterator shall be convertible to int, meet the requirements of CopyConstructible (34) and Assignable (23.1) types, and have both an operator++ and an operator--.
Complexity: At most (last - first) decrements of BidirectionalIterator, one increment and one decrement of T.
This example is included in the distribution in the examples section of the library under combination_ex.cpp.
Given a set { 0, 1, . . . n -1 } of size n, we wish to enumerate all the permutations of size r ≤ n that have no repetitions. We know before-hand that there are n! / (n-r)! such permutations. Enumerating them is easy using the next_partial_permutation algorithm:
const int r = 3;
const int n = 6;
std::vector<int> v(n);
for (int i = 0; i < n; ++i) v[i] = i;
int N = 0;
do {
++N;
if (N < 8 || N > 113) {
std::cout << "[ " << v[0];
for (int j = 1; j < r; ++j) { std::cout << ", " << v[j]; }
std::cout << " ]" << std::endl;
} else if (N == 8) {
std::cout << " . . ." << std::endl;
}
} while (next_partial_permutation(v.begin(), v.begin() + r, v.end()));
std::cout << "Found " << N << " permutations of size 3 without repetitions"
<< " from a set of size 5." << std::endl;
This code will print out:
[ 0, 1, 2 ] [ 0, 1, 3 ] [ 0, 1, 4 ] [ 0, 1, 5 ] [ 0, 2, 1 ] [ 0, 2, 3 ] [ 0, 2, 4 ] . . . [ 5, 3, 2 ] [ 5, 3, 4 ] [ 5, 4, 0 ] [ 5, 4, 1 ] [ 5, 4, 2 ] [ 5, 4, 3 ] Found 120 permutations of size 3 without repetitions from a set of size 5.
The situation is a bit more complex to understand when the original sequence has duplicate values, because the notion of permutation without repetitions in this case consists of the subsequences indexed by all collections of *distinct* r indices among the n indices, with identical such subsequences enumerated only once. Suppose for instance that v contains the sequence { 0, 1, 2, 0, 1, 3 }. In order to start the enumeration, the sequence must first be sorted into { 0, 0, 1, 1, 2, 3 }, then all the sequence of distinct three indices (permutations of size r of { 0, . . . n - 1 }) are applied to the above sequence, but notice for instance that the first two sequence of indices generate the same permutation [ 0, 0, 1 ] since the original sequence has the same element at indices 2 and 3. This subsequence is enumerated only once. Here is the code (identical, except for the initialization of v):
v[0] = 0; v[1] = 1; v[2] = 2; v[3] = 0; v[4] = 1; v[5] = 3;
std::sort(v.begin(), v.end());
N = 0; // note: r and n are still 3 and 6, respectively
do {
++N;
std::cout << "[ " << v[0];
for (int j = 1; j < r; ++j) { std::cout << ", " << v[j]; }
std::cout << " ]" << std::endl;
} while (next_partial_permutation(v.begin(), v.begin() + r, v.end()));
std::cout << "Found " << N << " permutations of size 3 without repetitions"
<< " from a (multi)set of size 5." << std::endl;
This time, the code outputs the much shorter:
[ 0, 0, 1 ] [ 0, 0, 2 ] [ 0, 0, 3 ] [ 0, 1, 0 ] [ 0, 1, 1 ] [ 0, 1, 2 ] [ 0, 1, 3 ] [ 0, 2, 0 ] [ 0, 2, 1 ] [ 0, 2, 3 ] [ 0, 3, 0 ] [ 0, 3, 1 ] [ 0, 3, 2 ] [ 1, 0, 0 ] [ 1, 0, 1 ] [ 1, 0, 2 ] [ 1, 0, 3 ] [ 1, 1, 0 ] [ 1, 1, 2 ] [ 1, 1, 3 ] [ 1, 2, 0 ] [ 1, 2, 1 ] [ 1, 2, 3 ] [ 1, 3, 0 ] [ 1, 3, 1 ] [ 1, 3, 2 ] [ 2, 0, 0 ] [ 2, 0, 1 ] [ 2, 0, 3 ] [ 2, 1, 0 ] [ 2, 1, 1 ] [ 2, 1, 3 ] [ 2, 3, 0 ] [ 2, 3, 1 ] [ 3, 0, 0 ] [ 3, 0, 1 ] [ 3, 0, 2 ] [ 3, 1, 0 ] [ 3, 1, 1 ] [ 3, 1, 2 ] [ 3, 2, 0 ] [ 3, 2, 1 ] Found 42 permutations of size 3 without repetitions of a (multi)set of size 5.Note that if we had wanted the permutations that had no repetitions of values (as opposed to repetitions of indices), we could simply have removed the duplicates from v, yielding a short sequence of m values, and enumerated the permutations of r elements taken from these m values without repetitions. Here m would be 4, and there would be four such permutations.
Given a set { 0, 1, . . . n -1 }, we wish to enumerate all the subsets of size r ≤ n. This is easy using the next_combination algorithm that takes three or four arguments:
const int r = 3;
const int n = 10;
std::vector<int> v_int(n);
for (int i = 0; i < n; ++i) { v_int[i] = i; }
int N = 0;
do {
++N;
if (N < 10 || N > 117) {
std::cout << "[ " << v_int[0];
for (int j = 1; j < r; ++j) { std::cout << ", " << v_int[j]; }
std::cout << " ]" << std::endl;
} else if (N == 10) {
std::cout << " . . ." << std::endl;
}
} while (next_combination(v_int.begin(), v_int.begin() + r, v_int.end()));
std::cout << "Found " << N << " combinations of size " << r << " without repetitions"
<< " from a set of " << n << " elements." << std::endl;
This code will print out:
[ 0, 1, 2 ] [ 0, 1, 3 ] [ 0, 1, 4 ] [ 0, 1, 5 ] [ 0, 1, 6 ] [ 0, 1, 7 ] [ 0, 1, 8 ] [ 0, 1, 9 ] [ 0, 2, 3 ] . . . [ 6, 7, 9 ] [ 6, 8, 9 ] [ 7, 8, 9 ] Found 120 combinations of size 3 without repetitions from a set of 10 elements.Had some elements been equal, e.g., v = { 0, 1, 2, 3, 1, 2, 3, 1, 2, 3 }, we would have had the following output instead (the discussion is the same as for permutations without repetitions, except that the sequences in the output must be sorted):
[ 0, 1, 1 ] [ 0, 1, 2 ] [ 0, 1, 3 ] [ 0, 2, 2 ] [ 0, 2, 3 ] [ 0, 3, 3 ] [ 1, 1, 1 ] [ 1, 1, 2 ] [ 1, 1, 3 ] [ 1, 2, 2 ] [ 1, 2, 3 ] [ 1, 3, 3 ] [ 2, 2, 2 ] [ 2, 2, 3 ] [ 2, 3, 3 ] [ 3, 3, 3 ] Found 16 combinations of size 3 without repetitions from a (multi)set of 10 elements.
Suppose we have a slightly different requirement, with a type that cannot be swapped, either because it isn't efficient, or because the sequence cannot be permuted (if it is passed const, for instance). For expository purposes, we use a non-modifiable vector of std::string. In this case we can apply the previous solution with an extra level of indirection, and apply next_combination to a vector that holds iterators into our non-modifiable vector of strings (note that the iterators are in sorted order):
const char *strings[] = {
"one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"
};
const int m = sizeof strings / sizeof *strings;
std::vector<std::string> V_strings(strings, strings + m);
const std::vector<std::string>& v_strings = V_strings;
std::vector<std::vector<std::string>::const_iterator> w(m);
for (int i = 0; i < m; ++i) { w[i] = v_strings.begin() + i; }
N = 0; // note: r and n are still 3 and 10, respectively
do {
++N;
if (N < 9 || N > 115) {
std::cout << "[ " << *w[0];
for (int j = 1; j < r; ++j) { std::cout << ", " << *w[j]; }
std::cout << " ]" << std::endl;
} else if (N == 9) {
std::cout << " . . ." << std::endl;
}
} while (next_combination(w.begin(), w.begin() + r, w.end()));
std::cout << "Found " << N << " combinations of size " << r << " without repetition"
<< " from a set of " << n << " elements." << std::endl;
This prints out, while never modifying the value of v:
[ one, two, three ] [ one, two, four ] [ one, two, four ] [ one, two, five ] [ one, two, seven ] [ one, two, eight ] [ one, two, nine ] [ one, two, ten ] [ one, three, four ] . . . [ seven, eight, nine ] [ seven, eight, ten ] [ seven, nine, ten ] [ eight, nine, ten ] Found 120 combinations of size 3 without repetitions from a set of 10 elements.
Given a set { 0, 1, . . . n -1 } of size n, we wish to enumerate all the permutations of size r that possibly have repetitions. (Note that r and n can be in any relation, larger or smaller.) We know before-hand that there are n^r such permutations. Each permutation with repetition is simply an assignment of r variables x[0] . . . x[r] into the set { 0, 1, . . . n -1 }. Enumerating them is easy using the next_mapping algorithm:
const int r = 5;
const int n = 3;
std::vector<int> v_int(r, 0);
int N = 0;
do {
++N;
if (N < 13 || N > 237) {
std::cout << "[ " << v_int[0];
for (int j = 1; j < r; ++j) { std::cout << ", " << v_int[j]; }
std::cout << " ]" << std::endl;
} else if (N == 13) {
std::cout << " . . ." << std::endl;
}
} while (next_mapping(v_int.begin(), v_int.end(), 0, n));
std::cout << "Found " << N << " mappings from " << n
<< " positions to a set of " << r << " elements." << std::endl;
This code will print out:
[ 0, 0, 0, 0, 0 ] [ 0, 0, 0, 0, 1 ] [ 0, 0, 0, 0, 2 ] [ 0, 0, 0, 1, 0 ] [ 0, 0, 0, 1, 1 ] [ 0, 0, 0, 1, 2 ] [ 0, 0, 0, 2, 0 ] [ 0, 0, 0, 2, 1 ] [ 0, 0, 0, 2, 2 ] [ 0, 0, 1, 0, 0 ] [ 0, 0, 1, 0, 1 ] [ 0, 0, 1, 0, 2 ] . . . . . [ 2, 2, 2, 1, 1 ] [ 2, 2, 2, 1, 2 ] [ 2, 2, 2, 2, 0 ] [ 2, 2, 2, 2, 1 ] [ 2, 2, 2, 2, 2 ] Found 243 mappings from 3 positions to a set of 5 elements.Note that this exactly enumerates the coordinates of a point in a r-dimensional cubical grid whose side has length n. Also note that there isn't any special treatment for the range values, they are simply consecutive values in the sense that one goes from one value to the next by using operator++.
Note that first_value is not necessarily an iterator, because there is no requirement on a dereferencing operator*. However, an iterator can be used. Note that the values pointed to by these iterators, or their orderings, are irrelevant. We demonstrate this here using instead of the range [0, r) a range [w.begin(), w.end()) into some vector of fruits.
const char *strings[] = {
"banana", "peach", "apple"
};
std::vector<std::string> W(strings, strings + n);
const std::vector<std::string>& w = W;
std::vector<std::vector<std::string>::const_iterator> v_iter(r, w.begin());
N = 0; // note: r and n are still 5 and 3, respectively
do {
++N;
if (N < 13 || N > 237) {
std::cout << "[ " << *v_iter[0];
for (int j = 1; j < r; ++j) { std::cout << ", " << *v_iter[j]; }
std::cout << " ]" << std::endl;
} else if (N == 13) {
std::cout << " . . ." << std::endl;
}
} while (next_mapping(v_iter.begin(), v_iter.end(), w.begin(), w.end()));
std::cout << "Found " << N << " mappings from " << n
<< " positions to a set of " << r << " fruits." << std::endl;
This code then outputs:
[ banana, banana, banana, banana, banana ] [ banana, banana, banana, banana, peach ] [ banana, banana, banana, banana, apple ] [ banana, banana, banana, peach, banana ] [ banana, banana, banana, peach, peach ] [ banana, banana, banana, peach, apple ] [ banana, banana, banana, apple, banana ] [ banana, banana, banana, apple, peach ] [ banana, banana, banana, apple, apple ] [ banana, banana, peach, banana, banana ] [ banana, banana, peach, banana, peach ] [ banana, banana, peach, banana, apple ] . . . . . [ apple, apple, apple, peach, peach ] [ apple, apple, apple, peach, apple ] [ apple, apple, apple, apple, banana ] [ apple, apple, apple, apple, peach ] [ apple, apple, apple, apple, apple ] Found 243 mappings from 5 positions to a set of 3 fruits.
Given a set { 0, 1, . . . n -1 }, we wish to enumerate all the combinations of size r of elements in the set, taken with repetitions. This is easy using the next_combination_counts algorithm that takes only two arguments. Instead of copying (possibly multiple repetitions of) elements into a range, we simply require a range holding the multiplicities of each instance in the original set. The lexicographically first assignment of multiplicities with a total multiplicity of size r is { 0, . . . 0, r }.
const int r = 5;
const int n = 3;
std::vector<int> multiplicities(n, 0);
multiplicities.back() = r;
int N = 0;
do {
++N;
std::cout << "[ " << multiplicities[0];
for (int j = 1; j < n; ++j) { std::cout << ", " << multiplicities[j]; }
std::cout << " ]" << std::endl;
} while (next_combination_counts(multiplicities.begin(), multiplicities.end()));
std::cout << "Found " << N << " combinations of size " << r
<< " with repetitions from a set of " << n << " elements." << std::endl;
This code will print out:
[ 0, 0, 5 ] [ 0, 1, 4 ] [ 0, 2, 3 ] [ 0, 3, 2 ] [ 0, 4, 0 ] [ 0, 5, 0 ] [ 1, 0, 4 ] [ 1, 1, 3 ] [ 1, 2, 2 ] [ 1, 3, 1 ] [ 1, 4, 0 ] [ 2, 0, 3 ] [ 2, 1, 2 ] [ 2, 2, 1 ] [ 2, 3, 0 ] [ 3, 0, 2 ] [ 3, 1, 1 ] [ 3, 2, 0 ] [ 4, 0, 1 ] [ 4, 1, 0 ] [ 5, 0, 0 ] Found 21 combinations.Note that it isn't hard to actually display the sequence itself. Given a value of multiplicities, e.g., { 1, 3, 1 }, we can copy into a container w the combination with repetition of a vector v.
const char *strings[] = {
"banana", "peach", "apple"
};
std::vector<std::string> V(strings, strings + n);
const std::vector<std::string>& v = V;
multiplicities[0] = 1;
multiplicities[1] = 3;
multiplicities[2] = 1;
assert(r == multiplicities[0] + multiplicities[1] + multiplicities[2]);
std::vector<std::string> w;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < multiplicities[i]; ++j) {
w.push_back(v[i]);
}
}
assert(r == w.size());
Printing the container holding the repeated values:
std::cout << "Printing banana/peach/apple with multiplicities [1, 3, 1]." << std::endl;
std::cout << "[ " << w[0];
for (int j = 1; j < r; ++j) { std::cout << ", " << w[j]; }
std::cout << " ]" << std::endl;
produces:
[ banana, peach, peach, peach, apple ]
That part was hard, given that the names ..._with_repetitions would just be too long for standardization. The permutations of size r < n are still called permutations, but we named the function with the (made up) idiom partial permutations because "partial" is already used in the C++ standard (partial_sort, with the same interface first,middle,last), and to avoid overloading ambiguities with the existing next_permutation algorithm for certain template parameters. We could have kept the same names for the versions with repetitions, except that the most useful interfaces did not manipulate these permutations or combinations with repetitions per se, but rather the mappings or combination counts, hence the naming.
We designed the interface to be most efficient. Requiring the range [middle, last) to be sorted is a good compromise because it does not force the algorithm to do it (iunnecessarily if this is already the case), it makes the algorithm very efficient and is maintained by the natural implementation of the algorithm, and it is easy enough for the user to precondition the range to meet the requirement (via standard algorithms). As far as the overloads with Increment/Decrement template parameters for nex/prev_mapping, we offer them in this library but probably would not propose them for C++ standardization .
© Copyright Hervé Brönnimann, Polytechnic University; Ben Bear, 2007. Use, modification, and distribution is subject to the Boost Software License, Version 1.0. (See accompanying file License_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)