In the D problem of AtCoder073 explained in this article, the problem of generating n! (N <= 8) permutations and performing operations on each of them. had. Permutation generation is often done with AtCoder, but it is easy to forget how to write it, so I will summarize it here.
Use permutations in the itertools module. Here, let's consider generating all permutations in which the order is rearranged for an array containing 0 to 3.
>>> import itertools
>>> t=[i for i in range(4)]
>>> itertools.permutations(t)
<itertools.permutations object at 0x104dc0af0>
>>> list(itertools.permutations(t))
[(0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2), (0, 3, 2, 1), (1, 0, 2, 3), (1, 0, 3, 2), (1, 2, 0, 3), (1, 2, 3, 0), (1, 3, 0, 2), (1, 3, 2, 0), (2, 0, 1, 3), (2, 0, 3, 1), (2, 1, 0, 3), (2, 1, 3, 0), (2, 3, 0, 1), (2, 3, 1, 0), (3, 0, 1, 2), (3, 0, 2, 1), (3, 1, 0, 2), (3, 1, 2, 0), (3, 2, 0, 1), (3, 2, 1, 0)]
>>> list(itertools.permutations(t,2))
[(3, 2), (3, 1), (3, 0), (2, 3), (2, 1), (2, 0), (1, 3), (1, 2), (1, 0), (0, 3), (0, 2), (0, 1)]
As mentioned above, you can see that the order of the array that is an iterable object (the first argument of permutations is an iterable object) is rearranged and the entire ** permutation stored in the tuple is generated. .. Also, in the second argument of permutations, you can specify r in the expression of $ _n P _r $ (default is r = n, where $ _n P _2 $ is obtained from r = 2).
Use next_permutation in the algorithm library. Here, too, consider generating all permutations in which the order of the array containing 0 to 3 is rearranged. In Python, I was thinking of generating all permutations, but in C ++, by applying the next_permutation function with the ascending permutations as the first permutation, ** the next permutation ** is generated. Then, if the permutation to which the next_permutation function is applied is the last permutation (descending sort), it returns to the first permutation. At this time, false is returned if the permutation to which the next_permutation function is applied is not the last permutation, and true is returned if it is the last permutation. Therefore, by using the do-while statement using the return value, all permutations can be used. You can do some operation. Furthermore, when using the do-while statement, all permutations cannot be operated unless you start from the first permutation, but if you calculate in advance how many permutations there are, you can apply the next_permutation function for that number of times. You can do something with all permutations.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n=4;
vector<int> v(n);
//Function that can be stored in 1 increments, convenient
iota(v.begin(), v.end(), 0);
do{
//v is in the following permutation
for(int i=0;i<n;i++){
//Some operation
}
}while(next_permutation(v.begin(),v.end()));
}
Finally, I would like to summarize the important points regarding permutation generation in Python and C ++.
① For Python **-Use the permutations of the itertools module -Generate all permutations with tuples (non-destructive) -Access each permutation with a for statement **
② For C ++ **-Use next_permutation of algorithm library -Replace with the following permutations (destructive) -When starting from a permutation sorted in ascending order, access with a do_while statement When starting from other permutations, calculate the number of permutations and access in for minutes **
Recommended Posts