/// 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;
}