Approach & Description:
Generation in lexicographic order
There are many ways to systematically generate all permutations of a
given sequence. One classical algorithm, which is both simple and
flexible, is based on finding the next permutation in lexicographic ordering,
if it exists. It can handle repeated values, for which case it
generates the distinct multiset permutations each once. Even for
ordinary permutations it is significantly more efficient than generating
values for the Lehmer code in lexicographic order (possibly using the factorial number system) and converting those to permutations. To use it, one starts by sorting the sequence in (weakly) increasing
order (which gives its lexicographically minimal permutation), and then
repeats advancing to the next permutation as long as one is found.
The following algorithm generates the next permutation
lexicographically after a given permutation. It changes the given
permutation in-place.
- Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
- Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
- Swap a[k] with a[l].
- Reverse the sequence from a[k + 1] up to and including the final element a[n].
After step 1, one knows that all of the elements strictly after position k
form a weakly decreasing sequence, so no permutation of these elements
will make it advance in lexicographic order; to advance one must
increase a[k]. Step 2 finds the smallest value a[l] to replace a[k] by, and swapping them in step 3 leaves the sequence after position k
in weakly decreasing order. Reversing this sequence in step 4 then
produces its lexicographically minimal permutation, and the
lexicographic successor of the initial state for the whole sequence.
Final Algorithm:
1) From the end, keep decrementing till A[i] < A[i+1]..
2) Now, find the closest element , greater than equal, to A[i] in
2) Now, find the closest element , greater than equal, to A[i] in
A[i+1 ... n]. Say, the index of the found element is "j".
3) Swap (A[i], A[j])
4) Reverse array A[i+1 .. n]
3) Swap (A[i], A[j])
4) Reverse array A[i+1 .. n]
Example:
Input 14532
output 15234..
1) 4 is the value where A[i] < A[i+1] when scanned from the end.
2) The closest element grater than equal to 4 in the subarray 532 is 5.
3) Swap (4,5) : 14532 -> 15432
4) Now, as we have identified in step 1 the index of i, we need to
reverse the array from A[i+1, n] i.e. in 15(432) (432) needs to be
reversed and hence we will get 15234...
2) The closest element grater than equal to 4 in the subarray 532 is 5.
3) Swap (4,5) : 14532 -> 15432
4) Now, as we have identified in step 1 the index of i, we need to
reverse the array from A[i+1, n] i.e. in 15(432) (432) needs to be
reversed and hence we will get 15234...
Working Code
#include < iostream>#include < algorithm>#include < time.h>using namespace std; // Swap functiontemplate < class T>void swap(T *i, T *j){ T temp = *i; *i = *j; *j = temp;} // function to reverse a range of valuestemplate < class T>void reverse(T *start, T *end){ while(start < end) { swap(start,end); start++; end--; }}// array_end does not point to a valid element of the array// it is beyond the last elementtemplate < class T>bool permute(T* array_start,T* array_end){ // array does not contain any element if(array_start == array_end) return false; // array contains only 1 element if(array_start+1 == array_end) return false; T *i,*i1,*j; // Make the pointers point to last and the second last elements i = array_end - 2; i1 = array_end - 1; // find two elements a,b such that a < b and index of a // is less than the index of b while(true) { // If such a pair is found, find an element c such that // c > a, then swap them and reverse the list from b till // the end if(*i < *i1) { j = array_end -1; // worst case is that j == i1 while(!(*i < *j)) j--; // This step implements the lexicographic order by // bringing the larger element in the front swap(i,j); // Reverse the list so that we have a weak decreasing // order in the remainder of the list reverse(i1,array_end-1); return true; } // Now the list is in strictly decreasing order // no more permutations are possible, return the // list as it was originally received if(i == array_start) { reverse(array_start,array_end-1); return false; } // decrement the two pointers i--; i1--; } }template< class T>void display(T *array,T *end){ T* i = array; while(i < end) { cout << *i << "-"; i++; } cout << endl;} int main(){ srand(time(NULL)); // You can declare any type here of any size int size = 4; char array[size]; cout << "Enter four numbers" << endl; for(int i=0;i < size;i++) cin>>array[i]; // C++ sort function so that the permutation // function receives the elements in the sorted order // in order to create a lexicographic order sort(array,array+4); // First permutation display(array,array+4); int count=1; // Call the function while you get valid permutations while(permute(array,array+4)) { count++; display(array,array+4); } cout << "Total permutations are " << count << endl; system("pause"); return 0;}
http://en.wikipedia.org/wiki/Permutation
http://marknelson.us/2002/03/01/next-permutation/
http://marknelson.us/2002/03/01/next-permutation/
