Using C++ to achieve the full permutation algorithm method
- 2020-04-01 23:43:33
- OfStack
<P> No matter which kind of total permutation generation algorithm, all follow the process of "original permutation" → "original mediation number" → "new mediation number" → "new permutation". </P><P> Among them, the number of mediations will go to the increasing carry number and decreasing carry number according to the difference of the algorithm. </P><P> We will not discuss the proof of the one-to-one correspondence between the permutation and the number of mediations. </P>
・ Increasing carry and decreasing carry Numbers
The so-called increasing carry and decreasing carry Numbers are Numbers whose bases increase or decrease with the number position. Usually we see fixed base Numbers, such as 2, 10, etc. M bits n Numbers can be represented by m by n Numbers. And m bit increment or decrement carry number can represent the number m! A. For example, an incrementally carried number, 4121, has 2, 3, 4, and 5 bases from right to left. The highest digit (the digit with the number four) is probably 4; The third highest is probably 3; The second highest is probably 2; The lowest place is going to be 1. If you add 4121 to 1, you get a 0, and you carry; If you add the 2 in the second place to the carry, you also get 0, and you carry; The third bit of 1 added to the carry is 2, no more carry. You end up with 4,200. It's the same with descending carry, except that the base is 9, 8, 7, 6 from right to left... , as opposed to the incremental carry system. Obviously, one of the greatest benefits of the descending carry system is that it is difficult to carry because it is larger in the last bits where the addition is most frequent (rightmost).
The next thing to understand is the relationship between increasing carry, decreasing carry Numbers and their serial Numbers. Increasing and decreasing carry Numbers can be considered as an ordered set of Numbers. If the ordinal number of 0 for incrementally carried and decrement carried Numbers is stated to be decimal 0, 987654321 for incrementally carried Numbers and 123456789 for decently carried Numbers correspond to decimal number 362880 (i.e. 9!). , a set of corresponding rules can be arranged. Where, the incremental carry number (a1) a2 a3 a4 The a5 a6 a7 a8 A9) as follows:
A1 * 9! + A2 * 8! + ... . + A8 * 2! + A9 * 1! = The serial number
For example, the increasing carry number of the serial number 100 is 4020, which is 4 times 4 factorial. + 0 * 3! + 2 * 2! + 0 * 1! = 100. To convert an ordinal number to its incremental carry number, you first need to find a maximum factorial number smaller than the ordinal number (i.e., 1, 2, 6, 24, 120, 720...). , divide it into integers to get the first part of the incremental carry system. Apply this method to the remainder of the division over and over again (and then, of course, choose the remainder of a smaller factorial) until the remainder is 0.
Decreasing carry number (a1) a2 a3 a4 The a5 a6 a7 a8 A9) as follows:
(((((((((a1 * 1 + A2) * 2 + A3) * 3 + ... + A7) * 8 + A8) * 9 + A9 = The serial number
For example, the descending carry of the serial number 100 is 131 (a7) a8 A9, Align from the back), i.e (1 * 8 + 3) * 9 + 1 = 100. To convert an ordinal number to its decrement carry number, you need to take the remainder of 9 on the ordinal number to get the lowest bit of the decrement carry system (this is the opposite of the highest bit of the increment carry system). Repeat the process by dividing the remaining integers (8, 7, 6, of course). Take the remainder) until the remainder is 0.
There are some important points to note about incremental and descending carry systems. The second is the conversion of serial Numbers and Numbers. In addition to 100, common conversions are: the increment of 999 is 121211, the decrement is 1670; The increment of 99 is 4011 and the decrement is 130. You can use this as a reference to see if you really understand how to calculate. The detailed calculation of incremental or descending carry is omitted below.
From now on we will introduce six permutation generation algorithms in detail. The specific theoretical introduction will be ignored, and the following focuses on how to map the arrangement to the number of mediations and how to reduce the number of mediations to the number of permutations.
I'm going to take the next 100 permutations of 839647521 for example.
・ Incremental carry permutation generation algorithm
Mapping method: from 9 to 2, check the number of Numbers to the right of the original order. This number right here is just one of the intermediary Numbers. For example, for the original permutation 839647521. There are 6 Numbers smaller than 9 to the right of 9, 7 Numbers smaller than 8 to the right of 8, and 3 Numbers smaller than 7 to the right of 7... There's one number to the right of two that's less than two. Finally, we get the number of the incrementing base number 67342221. (this number is added to the incrementing base number of 100, 4020, to get the new number, 67351311)
Restore method: we set the position Numbers of the new mediations to be 9, 8, 7, 6, 5, 4, 3, 2 from left to right. Before restoring, draw 9 Spaces. For each intermediate number y at position x, count y unused Spaces from the right to the left of the space. Fill in the unused space y+1 with the number x. This process is repeated until all the bits in the mediation number are counted. Finally, fill in 1 in the last space to complete the generation of the new permutation. Taking the number of new mediations 67351311 as an example, I give the detailed recovery steps. The red Numbers represent the new Numbers. The result is a new arrangement of 869427351.
void next_Permutations_by_increDecimal(int dataArr[],int size){
int i;
int *resultArr = new int[size];
int index = 0;
map<int,int>::iterator iter;
//The first step is to figure out the number of mediations
//From large to small, the number of Numbers smaller than the number to the right of the number I in the current array is obtained and recorded
map<int,int> agentMap;
for(i=0; i<size; ++i){
agentMap.insert(valType(dataArr[i],count(dataArr,i,size,dataArr[i])));
}
qsort(dataArr,0,size-1);
//The second step is to get the new number of mediations, on the basis of the old number of mediations, according to the incremental carry number method plus 1
while (true){
++countNum;
next_inter_num(dataArr,agentMap);
//The third step is to get a new permutation based on the new number of mediations
index = size -1;
//Empty the current array of records to hold the newly generated array
for(i=0; i<size; ++i){
resultArr[i] = 0;
}
while(true){
iter = agentMap.find(dataArr[index]);
valType value = *iter;
resultArr[getNextPosition(resultArr,size,value.second,0)] = dataArr[index];
--index;
if(index == 0) break;
}
//Make the last empty position the minimum number
i = 0;
while(true){
if(resultArr[i] != 0){
++i;
}else{
resultArr[i] = dataArr[index];
break;
}
}
print(resultArr,size);
bool flag = true;
for(i=1; i<size; ++i){
if(resultArr[i] > resultArr[i-1]){
flag = false;
break;
}
}
if(flag) break;
}
delete [] resultArr;
}
void next_inter_num(int dataArr[],map<int,int>& agentMap){
map<int,int>::iterator iter;
//The value of the current bit of temp needs to be increased. TmpResult is the sum of the value of temp and the current bit
int start = 2,temp=1,tmpResult;
int index = 1; //The smallest first digit in an array
while(true){
iter = agentMap.find(dataArr[index]);
valType value = *iter;
tmpResult = value.second + temp;
if(tmpResult < start){
//Carry is no longer generated
agentMap.erase(dataArr[index]);
agentMap.insert(valType(dataArr[index],tmpResult));
break;
}else{
agentMap.erase(dataArr[index]);
agentMap.insert(valType(dataArr[index],tmpResult % start));
temp = tmpResult / start;
++start;
}
++index;
}
}
・ Descending carry permutation generation algorithm
Mapping method: the mapping method of descending carry system is just the opposite of increasing carry system, that is, from 9 to 2, the number of smaller Numbers to the right of it in order. However, the order in which the number of mediations is generated is no longer from left to right, but from right to left. The generated decreasing base mediations are just the mirror image of the increasing carry permutation generation algorithm. For example, the descending base number of 839647521 is 12224376. (the new intermediate number is 12224527 after adding the base number of 100 decreasing to 131)
Reduction method: The reduction method of decreasing the number of carry mediations is also the opposite of increasing the number of carry mediations. An incremental carry reduction method fills in the Numbers from the highest number of mediations (left) to the lowest number (right). The position reduction method counts from the lowest position to the highest position. For example, for the new mediation number 12224527, I gave detailed restore steps. Red represents the space being filled. You end up with a new arrangement 397645821.
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201305/2013052415272616.png ">
C++ implementation code:
void next_Permutations_by_DecreDecimal(int dataArr[],int size){
//Creates an array of results to record an arrangement
int *resultArr = new int[size];
int i;
//The first step is to figure out the number of mediations
map<int,int> agentMap;
for(i=0; i<size; ++i){
int nums = count(dataArr,i,size,dataArr[i]);
agentMap.insert(valType(dataArr[i],nums));
}
//The second step is to find the new number of mediations where the lowest decimal point is the highest, so the carry is not frequent, and the performance should be better than the incremental carry
//The lowest base is 9, decreasing forward
int start = size,temp = 1;
int tmpResult;
int index = size-1;//The number smaller to the right of the largest number in a sequence of digits
map<int,int>::iterator iter;
qsort(dataArr,0,size-1);
while (true){
++countNum; //The global variable records the number of permutations
next_inter_num(dataArr,agentMap,size);
index = size -1;
//The third step is to get a new permutation based on the number of mediations produced
for(i=0; i<size; ++i){
resultArr[i] = 0;
}
while(true){
iter = agentMap.find(dataArr[index]);
valType value = *iter;
//Find the next fill space
resultArr[getNextPosition(resultArr,size,value.second,0)] = dataArr[index];
--index;
if(index == 0) break;
}
i = 0;
while(true){
if(resultArr[i] != 0){
++i;
}else{
resultArr[i] = dataArr[index];
break;
}
}
print(resultArr,size);
bool flag = true;
for(i=1; i<size; ++i){
if(resultArr[i] > resultArr[i-1]){
flag = false;
break;
}
}
if(flag) break;
}
delete [] resultArr;
}
void next_inter_num(int dataArr[],map<int,int> &agentMap,int size){
int start = size,temp = 1;
int tmpResult;
int index = size-1;//The number smaller to the right of the largest number in a sequence of digits
map<int,int>::iterator iter;
while(true){
iter = agentMap.find(dataArr[index]);
valType value = *iter;
tmpResult = value.second + temp;
if(tmpResult < start){
//Do not generate carry, directly overwrite the last value
agentMap.erase(dataArr[index]);
agentMap.insert(valType(dataArr[index],tmpResult));
break;
}else{
//Produce carry
agentMap.erase(dataArr[index]);
agentMap.insert(valType(dataArr[index],tmpResult % start));
tmpResult = tmpResult / start;
--start;
}
--index;
}
}
・ Dictionary permutation generation method
Mapping method: the original arrangement of Numbers from left to right (the end of the most ignore), in turn to see the number of Numbers on the right side of the number is smaller than its number, the number is the number of mediation. For example, for permutation 839647521. There are 7 Numbers on the right side of the highest 8, 2 Numbers on the right side of the second highest 3, and 6 Numbers on the right side of the third 9... There's one number to the right of 2 that's less than 2. The number of incrementing base mediations is 72642321. (the new intermediate number 72652011 is obtained after this intermediate number is added to the increasing decimal number 4020 of 100)
Reduction method:
The inverse process in which the restore method is a mapping method. You can start with the auxiliary number 1
2
3
4
5
6
7
8
9, and 9 empty Spaces to fill the new array. Then start from the highest digit of the new number of mediations. For example, if the highest digit of the new mediation is x, you can count up to x from the first unused digit of the auxiliary number. The x+1 digit should be the first digit of the vacancy. We label this number "used" and fill the first space from the left with it. Then, look at the second highest value of the new intermediate number, y, from the first unused number of the auxiliary number, count to one. The y plus 1 number is the number of the next vacancy. We label this number "used" and fill the second space from the left with it. And so on until the last number in the mediation number is counted. For example, for the new mediation number 72652011, we give the case of its auxiliary number and each step of vacancy. The red number represents "marking as used", and "used" Numbers are no longer counted in later counts. When all the Numbers in the new mediation number are counted, the only number left in the secondary number is filled into the final space. We end up with a new arrangement 839741562.
C + + implementation:
void next_Permutations_by_DicOrder(int dataArr[],int size){
int key = 0;
int index,temp,end,left,right;
int i;
bool flag ;
while(true){
++countNum;
print(dataArr,size);
flag = true;
index = 0,temp = 0,end=8,left = right = 0;
//Find the first drop forward from the end of the current array
for(i = size-1; i > 0; i--){
if(dataArr[i] > dataArr[i-1]){
key = i-1; //K records the point of descent
flag = false;
break;
}
}
//If it is already ordered from high to low, the operation completes
if(flag)
break;
index = key + 1;
//Find the smallest number in the suffix that is larger than the first drop
while(dataArr[key] < dataArr[index] && index < size){
++index;
}
index --;
//I'm going to swap the number that I found with the first point that went down
temp = dataArr[key];
dataArr[key] = dataArr[index];
dataArr[index] = temp;
left = key+1;
right = size - 1;
//Reverse the number after the point of descent
while(left < right){
temp = dataArr[left];
dataArr[left] = dataArr[right];
dataArr[right] = temp;
++left;
--right;
}
}
}
Backtracking method:
void next_Permutations_by_backtrack(int dataArr[],int size){
//Create an array of results
int *resultArr = new int[size+1];
backTrack(1,size+1,resultArr,dataArr);
delete [] resultArr;
}
//Pruning function
bool place(int k,int resultArr[])
{
for (int j = 1; j < k; j++) {
if (resultArr[j] == resultArr[k]) {
return false;
}
}
return true;
}
void backTrack(int t,int size,int resultArr[],int dataArr[])
{
if (t > size-1) {
++ countNum;
for(int i = 1; i < size; i++) {
cout << resultArr[i] << " ";
}
cout << endl;
} else {
for(int i = 1; i < size; i++) {
resultArr[t] = dataArr[i-1];
if (place(t,resultArr)) {
backTrack(t+1,size,resultArr,dataArr);
}
}
}
}