BlogsDope image BlogsDope

Generating permutations of all elements of an array

Oct. 26, 2017 RECURSION FUNCTION C PYTHON C++ ARRAY 18178

This post is about printing all the permutations of an array with the use of recursion. This is also a very common question of computer programming.

Writing the code for a problem is not a big deal if you know how to solve the problem practically or understand the logic of solving the problem in reality. So before going into the coding part, let's first understand the logic of making the permutations in reality and then we will code that logic.

Let's make permutations of 1,2,3. One way I am going to make the permutation is: I will start by keeping the first number, i.e. 1, fixed, and will make the permutations of the other numbers. Thus the numbers obtained by keeping 1 fixed are:

123
132

Now, we have all the numbers which can be made by keeping 1 at the first position. So, let's keep 2 at the first position this time and make the permutations.

213
231

Similarly, keeping 3 at the first position, the numbers are:

312
321

So, now we have all our permutations which can be made by the digits 1, 2 and 3. And of course, making permutations of only 3 digits is quite easy. So, let's use this logic to make the permutations of the digits 1, 2, 3 and 4. We will start by keeping 1 at the first position. Thus, we are left with the digits 2, 3 and 4. And we have to make all the permutations of the digits 2, 3 and 4. So, we will make the permutations of 2, 3 and 4 by keeping 2 fixed. Thus the numbers obtained are:

1234
1243

Now, we will fix 3 out of 2, 3 and 4.

1324
1342

Again, keeping 4 fixed out of 2, 3 and 4.

1423
1432

Now, we have all the numbers which can be made by keeping 1 at the first position. Similarly, we will keep all other digits at the first position and get the corresponding permutations. You can see that we are breaking the problem into smaller problems and then making the permutations of these smaller ones. After having all the permutations of the smaller number, we are just replacing one of the digits of this new number with the last digit which was fixed and again making permutations of the newer number. For example, After making all the permutations of 34 (34 and 43) and getting the numbers 1234 and 1243, we replaced 2 with 3 (2 was the last fixed digit in the number). Now, the last two digits are 2 and 4. Now, we made the permutation of these digits and got 1324 and 1342.

Similarly, after having the permutation of last three digits, we will replace the first digit and will again get all the permutations of the last three digits.

So, you have understood the logic of making the permutations. Now, let's the code for the same.

It can be easily noticed that for the number 1234, we are first making permutations of 234 first and for 234, permutations of 34 and so on. Thus, we are recurring to make permutations here. So, recursion seems to be the most generic way to solve the problem. So, let's make a permutation function to do this.

array = [1, 2, 3, 4]
function permutation(start, end):
#i will go from start to end
    for i -> (start, end+1):
        permutation(start+1,end)

Here, we have just implemented the above-stated logic. To make the permutations of 1234, we have to make the permutations of 234 first and this will be done in the first iteration (i will be 0). For this, permutation(1,3) will be called. Now in this permutation (where elements are 2, 3 and 4), we need to make the permutations of 3 and 4 first. And thus, permutation(2,3) will be called to do so. Similarly, permutation(3,3) will be called at the end. At this point, we have to make the permutations of only one digit with the index 3 and it has only one permutation i.e., itself. So, we can now print this permutation as no further recursion is now need.

array = [1, 2, 3, 4]
    function permutation(start, end):
        if end==start:
            print array
            return for i -> (start, end+1):
    for i -> (start, end+1):
        permutation(start+1,end)

Now, 1234 will be printed as it is the first permutation of the number 1, 2, 3 and 4. Till now, we are able to implement the logic of recursion. But we still have to write the code where the swapping of the numbers will take place. For example, after printing of 1234, we will get out of the permutation(3,3) function to the permutation(2,3) function. In the permutation(2,3) function, the loop will increase the value of 'i' and will point to the element with index 3 in the array. Also, the variable 'start' is 2 and to continue further, we need to swap these two elements as we were doing above. You can also say that the element with the index 2 was the last fixed element. So, we need to swap it with the next element. Hence, after the increment of 'i', there should be a swap function.

swap(array[start],array[i])
permutation(start+1,end)

This time as well, start is equal to end and thus, 1243 will be printed this time. We are done with the digits 3 and 4. Now, we will do the swapping with the second last fixed digit i.e., 2. But our array has been changed now and is [1, 2, 4, 3] and not [1, 2, 3, 4]. So, let's first restore the array.

swap(array[start],array[i])
permutation(start+1,end)
swap(array[start],array[i])

We simply did this by reswapping the digits. Thus, our function to write all the permutations of an array is complete now.

array = [1, 2, 3, 4]
function permutation(start, end):
    if end==start:
        print array
        return
    for i -> (start, end+1):
        swap(array[start],array[i])
        permutation(start+1,end)
        swap(array[start],array[i])

Codes to generate the permutations


Python

print "Enter the numbers"
a = raw_input()
#converting all elements of array to integer
a = (map(int,a.split()))

def permutation(start, end):
    if end==start:
        print a
        return
    for i in range(start, end+1):
        #swapping
        a[i],a[start] = a[start],a[i]
        #calling permutation function
        #by keeping the element at the index start fixed
        permutation(start+1, end)
        #restoring the array
        a[i],a[start] = a[start],a[i]
permutation(0,len(a)-1)

C

#include <stdio.h>

//function to print the array
void printarray(int arr[], int size)
{
    int i,j;
    for(i=0; i<size; i++)
    {
        printf("%d\t",arr[i]);
    }
    printf("\n");
}

//function to swap the variables
void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

//permutation function
void permutation(int *arr, int start, int end)
{
    if(start==end)
    {
        printarray(arr, end+1);
        return;
    }
    int i;
    for(i=start;i<=end;i++)
    {
        //swapping numbers
        swap((arr+i), (arr+start));
        //fixing one first digit
        //and calling permutation on
        //the rest of the digits
        permutation(arr, start+1, end);
        swap((arr+i), (arr+start));
    }
}

int main()
{
    //taking input to the array
    int size;
    printf("Enter the size of array\n");
    scanf("%d",&size);
    int i;
    int arr[size];
    for(i=0;i<size;i++)
        scanf("%d",&arr[i]);
    //calling permutation function
    permutation(arr, 0, size-1);
    return 0;
}

Liked the post?
Developer and founder of CodesDope.
Editor's Picks
3 COMMENTS

Please login to view or add comment(s).