Algorithm to Generate the permutations of the array containing number in lexicographical order.

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.

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. 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.
3. Swap a[k] with a[l].
4. 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 

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]

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...

Working Code

#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;

}

Run Here http://ideone.com/sK8JH
The complexity of the approach is O(n*n!)

http://en.wikipedia.org/wiki/Permutation
http://marknelson.us/2002/03/01/next-permutation/