Minimum path sum in a matrix
June 12, 2012
Number of nodes in a binary tree of height h
June 12, 2012

Permutations of a String or Array

Print all possible permutations of an Array or a String. For Example: If the array is arr={1, 2, 3}. Then the possible permutations are:

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

Solution:

There is an easy solution to the above problem, if we think recursively.

Suppose we are given a 5-element array {1, 2, 3, 4, 5}.

We’ll start by picking one of the 5 values. Let’s pick 3.

We remove 3 from the original array, and place it in the first position of our new array (3 is going to be the first value of the permutation string). So now we have “3? by itself and four values in the Array- “1245?.

This 4-value array can now be passed to the same recursive function to get the permutation of four values and we will append ‘3’ in front of all those permutations.

Function Logic:

permutation ( {1,2,3,4,5} )
{
     permutation ( {2,3,4,5} ) and put ‘1‘ in front of each.
     permutation ( {1,3,4,5} ) and put ‘2‘ in front of them.
     permutation ( {1,2,4,5} ) and put ‘3‘ in front of them.
     permutation ( {1,2,3,5} ) and put ‘4‘ in front of them.
     permutation ( {1,2,3,4} ) and put ‘5‘ in front of them.
}

for finding the permutations of the 4-element array we rely on the same algorithm. Function Code:

    /** 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] );
        }
    }

We are calling the swap function again twice (again after calling permutation function), because we don’t want to disturb the order of elements in the array for the calling function (Calling function is also the same function because of recursion). Otherwise the result will get distorted.

Sample Program:

    #include
    /* Helper function to print the array */
    void printArray(int * arr, int n)
    {
        printf(“\n”);
        for(int i=0; i<n; i++)
            printf(“%d “, arr[i]);
    }
    /* Helper function to swap two variables */
    void swap(int *a, int *b)
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    /* Recursive Algorithm to print all permutations */
    void permutation(int * arr, int n, int l)
    {
        if(l==n-1)
        {
            printArray(arr, n);
        }
        for(int i=l; i<n; i++)
        {
            swap(&arr[i], &arr[l]);
            permutation (arr, n, l+1);
            swap(&arr[i], &arr[l]);
        }
    }
    /* Main function */
    int main()
    {
        int a[] = {1,2,3};
        permutation(a, 3, 0);
        return 0;
    }

1 Comment

  1. […] with repeated values 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. […]

Leave a Reply

Your email address will not be published. Required fields are marked *