Jun 142012
 

This question is a variation of a question which I posted earlier “Print Permutations of an Array or String“. The code which I had written there will not work if we have repetitions in the array. Today’s post is to write the code to print all permutations and takes care of the case if there is any duplication in the array.

For example: If the array is {1, 2, 3} then the result should be

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

But if the array is {1, 2, 2} then the output should be

1 2 2
2 1 2
2 2 1

Solution:

We will take forward from this post only. When there is no duplicates, The code to compute permutations is as below :

    /** Recursive function to print all permutations of an Integer array.
     * arr: Array of integers.
     * n: Number of elements in the array.
     * x: at any given point where we are.
     **/
    Void permutation (int * arr, int n, int x) 
    {
        if(x == n-1)
        {
            prinArray(arr, n); 
        }

        for (int i=x; i<n; i++)
        {
            swap( &arr[i], &arr[x] );
            permutation ( arr, n , x+1);
            swap( &arr[i], &arr[x] );
        }
    }

If we have duplicates, then we just need to keep a check of not to swap two elements if they are same. so just one extra check in the for loop:

    /** Recursive function to print all permutations of an Integer array.
     * arr: Array of integers.
     * n: Number of elements in the array.
     * x: at any given point where we are.
     **/
    Void permutation (int * arr, int n, int x) 
    {
        if(x == n-1)
        {
            prinArray(arr, n); 
        }

        for (int i=x; i<n; i++)
        {
            if(arr[i] == arr[x]) 
                continue;

            swap( &arr[i], &arr[x] );
            permutation ( arr, n , x+1);
            swap( &arr[i], &arr[x] );
        }
    }

 

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)