/// The complexity of the approach is O(n*n!)
/// It finds a valid permutation in linear time
/// and in a lexicographic order, it also handles the case where there
/// are duplicates present, because it implements am increasing order
// hence duplicates are never used twice to generate permutations
#include<iostream>
#include<algorithm>
#include<time.h>
using namespace std;
// Swap function
template < class T>
void swap(T *i, T *j)
{
T temp = *i;
*i = *j;
*j = temp;
}
// function to reverse a range of values
template < 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 element
template < 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;
}