Jun 122012
 

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;
    }
vliegen123.nl

  One Response to “Permutations of a String or Array”

 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)