Introduction
Given {1, 2, 3, , , n}, its full permutations number n!, which is the most basic high school combinatorics knowledge. Taking n=4 as an example, all of its permutations are shown in the figure below (presented in the form of a lexicographic-order tree): It’s easy to think of using recursion to find all of its full permutations. Look carefully at the figure above: starting with 1, followed by the full permutations of {2, 3, 4}; starting with 2, followed by the full permutations of {1, 3, 4}; starting with 3, followed by the full permutations of {1, 2, 4}; starting with 4, followed by the full permutations of {1, 2, 3}. The code is as follows:
/* author : 刘毅（Limer） date : 2017-05-31 mode : C++ / #include
#include using namespacestd; voidFullPermutation(intarray[],intleft,intright) { if(left == right) { for(inti = 0;i < 4;i++) cout << array[i] << “ “; cout << endl; } else { for(inti = left;i <= right;i++) { swap(array[i],array[left]); FullPermutation(array,left + 1,right); swap(array[i],array[left]); } } } intmain() { intarray[4] = {1,2,3,4}; FullPermutation(array,0,3); return0; }
The run is as follows: 
Huh~ the full permutation written with recursion is a bit imperfect — it doesn’t strictly follow lexicographic order. But friends familiar with C++ surely know another, simpler and more perfect way to do full permutations. Two algorithm functions defined in the file
/* author : 刘毅（Limer） date : 2017-05-31 mode : C++ / #include
#include using namespacestd; voidFullPermutation(intarray[]) { do { for(inti = 0;i < 4;i++) cout << array[i] << “ “; cout << endl; }while(next_permutation(array,array + 4)); } intmain() { intarray[4] = {1,2,3,4}; FullPermutation(array); return0; }
The run screenshot is omitted. The output happens to match lexicographic order. So how is this “wheel” built? (Excerpted from Hou Jie’s 《STL 源码剖析》 (STL Source Code Analysis)) 1. next_permutation: first, starting from the very end and going backwards, look for two adjacent elements, letting the first element be i and the second be ii, satisfying i < ii. After finding such a pair of adjacent elements, examine from the very end going backwards again and find the first element greater than i, let it be j. Swap the elements i and j, then reverse the arrangement of all the elements after ii — that is the “next” permutation sought. 2. prev_permutation: first, starting from the very end and going backwards, look for two adjacent elements, letting the first element be i and the second be ii, satisfying i > ii. After finding such a pair of adjacent elements, examine from the very end going backwards again and find the first element smaller than i, let it be j. Swap the elements i and j, then reverse the arrangement of all the elements after ii — that is the “previous” permutation sought. The code is as follows:
boolnextpermutation(int first,int last) { if(first == last)returnfalse;// empty range int i = first; ++i; if(i == last)returnfalse;// only one element i = last; –i; for(;;) { int ii = i; –i; if(_i < ii) { int j = last; while(!(_i < –j))// search from the tail backwards until an element greater than i is found ; swap(_i, _j); reverse(ii,last); returntrue; } } if(i == first)// the current permutation is the last permutation in lexicographic order { reverse(first,last);// reverse everything, giving ascending order returnfalse; } } boolprev_premutation(int first,int last) { if(first == last)returnfalse;// empty range int i = first; ++i; if(i == last)returnfalse;// only one element i = last; –i; for(;;) { int ii = i; –i; if(_i > _ii) { int j = last; while(!(i > –j))// search from the tail backwards until an element greater than i is found ; swap(_i, j); reverse(ii,last); returntrue; } } if(i == first)// the current permutation is the first permutation in lexicographic order { reverse(first,last);// reverse everything, giving descending order returnfalse; } }
Closing remarks This article mainly introduces two methods for solving the full permutation problem of a sequence without duplicates: recursion and the lexicographic-order method.
