** Updated on 9/14: The implementation example taught in the comment section is posted at the end of this article. (C ++, Python) **
I wanted to make a combination that allows duplication in C ++, which I'm not used to, so I searched a lot, but I couldn't find it easily. There is a "permutation" that allows duplication, and a formula that calculates the total number of duplicate combinations ($ \ small_n H_r $ that I learned in junior high school), but the code that can enumerate duplicate combinations has not been rolled.
When I looked it up, it seems that ʻitertoolsnormally contains a function calledcombination_with_replacement ()` in Python, so that code (https://docs.python.org/ja/3/library/itertools.html) ), And re-implemented it in C ++.
If you have any mistakes or improvements, please let us know.
First, as an example, consider a combination enumeration when extracting $ 2 $ elements from the set $ \ left \ {1, 2, 3 \ right \} $, allowing duplication. The flow itself is simple and looks like this:
In other words, in general, if you want to allow duplication from the set $ \ Omega $ and extract $ n $ elements, you can duplicate $ \ Omega $ to $ n $ and extract a unique combination from their Cartesian product. It will be.
First, implement it by generating the Cartesian product. It seems that there is also a function called product () of ʻitertools` in Python, but I could not catch up with the double list comprehension notation in the source code, so I implemented the Cartesian product in Golang. I referred to the code of the person who is (https://qiita.com/tesujiro/items/2e41e1159948dc90c3d9). This person generally writes the code to find the Cartesian product between multiple sets of $ \ Omega_1, \ Omega_2, \ Omega_3, \ ldots $.
In my implementation this time, "Allow duplicates from $ \ Omega $ and extract $ n $ pieces", so in general Cartesian product $ \ Omega_1 = \ Omega, \ Omega_2 = \ Omega, \ Omega_3 = Equivalent to \ Omega, \ ldots, \ Omega_n = \ Omega $. As the value of $ n $ increases, it becomes troublesome to duplicate $ \ Omega $ by the number of $ n $ and assign it to the argument, so $ n $ is counted with the argument repeat. I will. First of all, the code is posted below.
python
#include <bits/stdc++.h>
using namespace std;
template<typename T>
vector<vector<T>> productRecurse(vector<T>, int, vector<vector<T>>);
//Cartesian product
template<typename T>
vector<vector<T>> product(vector<T> choices, int repeat) {
vector<vector<T>> emptyResult(1, vector<T>());//Empty list to store combinations
return productRecurse(choices, repeat, emptyResult);
}
template<typename T>
vector<vector<T>> productRecurse(vector<T> choices, int repeat, vector<vector<T>> result) {
if (repeat == 0) {return result;}//Return the answer when the Cartesian product is completed
vector<vector<T>> provisionalResult;//Cartesian product in the process of creation
for (vector<T> re: result) {
for (T c: choices) {
vector<T> temp = re;
temp.push_back(c);
provisionalResult.push_back(temp);
}
}
return productRecurse(choices, repeat - 1, provisionalResult);
}
In explaining the above code, let's consider again as an example to create a Cartesian product by duplicating the set $ \ left \ {1, 2, 3 \ right \} $ into $ 2 $. The flow when calling product (choices = {1, 2, 3}, repeat = 2) is as follows.
product (choices = {1, 2, 3}, repeat = 2).productRecurse (choices = {1, 2, 3}, repeat = 2, result = {{}}) is called.provisionalResult = {{1}, {2}, {3}}.productRecurse (choices = {1, 2, 3}, repeat = 1, result = {{1}, {2}, {3}}) is called.provisionalResult = {{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3 , 2}, {3, 3}} .productRecurse (choices = {1, 2, 3}, repeat = 0, result = {{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2 }, {2, 3}, {3, 1}, {3, 2}, {3, 3}}) is called.repeat == 0, the argument result is the final Cartesian product.In Python, the part that requires list comprehension is recursively repeated. Let's actually run it.
python
int main(){
vector<int> choices = {1, 2, 3};
int repeat = 2;
vector<vector<int>> answer = product(choices, repeat);
for (int i = 0; i < answer.size(); i++) {
cout << answer[i][0] << " " << answer[i][1] << endl;
}
}
You can see that the Cartesian product is listed correctly, as calculated manually.
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
Well, once you get here, the rest is easy. Extract a unique combination from the Cartesian product. The point is, for example, when extracting $ (1, 2) $, it is sufficient to exclude $ (2, 1) $, so for a certain combination comb, only those withcomb == sort (comb)are extracted. To do.
python
template<typename T>
vector<vector<T>> combWithReplace(vector<T> choices, int n) {
vector<vector<T>> answer;
for (vector<T> comb: product(choices, n)) {
vector<T> toSorted = comb;
sort(toSorted.begin(), toSorted.end());
if (comb == toSorted) {
answer.push_back(comb);
}
}
return answer;
}
Now, the program to enumerate the duplicate combinations is completed. Finally, again, try a combination enumeration to allow duplicates from the set $ \ left \ {1, 2, 3 \ right \} $ and extract $ 2 $ elements.
python
int main(){
vector<int> choices = {1, 2, 3};
int n = 2;
vector<vector<int>> answer = combWithReplace(choices, n);
for (int i = 0; i < answer.size(); i++) {
cout << answer[i][0] << " " << answer[i][1] << endl;
}
}
The result is as follows. You can see that the same result as the manual calculation is obtained. You can also see that each combination is also sorted.
1 1
1 2
1 3
2 2
2 3
3 3
Looking at the source code for Pythonʻitertools`, I never thought that implementing c ++ would be so tedious. There was a reason why list comprehensions existed even though they were less readable. $ \ Ldots $. If you have any mistakes, please let us know. Thank you for reading to the end.
The following is an implementation example taught by @Nabetani. Please see the comment section for performance etc.
My implementation is in line
{{}}
⇒{{1}, {2}, {3}}
⇒{{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}}
While the corresponding items were extracted after completing the Cartesian product, in this implementation, each combination is used.
{} ⇒ {1} ⇒ {1, 1} ⇒ Add to answer
⇒ {1, 2} ⇒ Add to answer
⇒ {1, 3} ⇒ Add to answer
{} ⇒ {2} ⇒ {2, 2} ⇒ Add to answer
⇒ {2, 3} ⇒ Add to answer $ \ cdots $
It seems that it is completed in the form of and added to the answer. (ʻAppend ()` function in the structure) This may be easier to understand because it is similar to the operation for enumerating duplicate combinations by hand calculation.
c++14
#include <iterator>
#include <vector>
template <typename container_type>
std::vector<std::vector<typename container_type::value_type>>
combWithReplace(container_type const &choices, size_t n) {
using value_type = typename container_type::value_type;
using selected_t = std::vector<value_type>;
using itor_t = typename container_type::const_iterator;
struct impl { //Recursion is troublesome with lambda, so make it a class
std::vector<std::vector<value_type>> &r_; //Have a reference to avoid copying
impl(std::vector<std::vector<value_type>> &r) : r_(r) {}
void append(selected_t &s, itor_t b, itor_t e, size_t n) {
if (n == 0) {
r_.push_back(s);
} else {
for (auto it = b; it != e; ++it) {
s.push_back(*it);
append(s, it, e, n - 1);
s.pop_back();
}
}
};
};
std::vector<std::vector<value_type>> r;
impl o{r};
selected_t e;
e.reserve(n);
o.append(e, std::cbegin(choices), std::cend(choices), n);
return r;
}
python3.8
def comb_with_replace(a, n):
r = []
def append(e, b, add_count):
"""Enumerate the elements of duplicate combinations using recursion and add the found combinations to r
Parameters
----------
e : list
Duplicate combinations in the middle of assembly
b : int
Index at the beginning of available elements
add_count : int
Number of elements to add to e
"""
if add_count == 0:
r.append(e)
else:
for ix in range(b, len(a)):
append(e+[a[ix]], ix, add_count-1)
append([], 0, n)
return r
def main():
choices = [1, 2, 3]
for e in comb_with_replace(choices, 2):
print(e)
main()
Recommended Posts