Generating permutations using recursion

Permutations generation.

Permutations
Permutations are the ways of arranging items in a given set such that each arrangement of the items is unique.
If ‘n’ is the number of distinct items in a set, the number of permutations is n * (n-1) * (n-2) * … * 1.

In the given example there are 6 ways of arranging 3 distinct numbers.
i.e If n = 3, the number of permutations is 3 * 2 * 1 = 6.

The idea behind generating permutations using recursion is as below.

  • Positions is a vector / list that keeps track of the elements in the set that are included while generating permutation. The size of Positions is same as the size of the set containing numbers for generating permutations.
  • Permutation is a vector / list that stores the actual permutation.


Each function call tries to append a new element to the permutation if an element at position within the set has not been included. If the size of the permutations vector equals the size of the set containing the elements, a permutation has been found.


Algorithm: Generate_Permutation ( Permutation, Array, Positions )

  1. If the length of Permutation equals the length of Array
        Permutation Found.
  2. Else
        For each position ‘p’ from 0 till the length of Array
            If element at position ‘p’ has been taken
                Continue to check for next position.
            Mark position ‘p’ as Taken.
            Append the element at position ‘p’ to the Permutation.
            Generate_Permutation ( Permutation, Array, Positions )
            Remove the element at position ‘p’ from the Permutation.
            Mark position ‘p’ as Available.

Below recursion stack explains how the algorithm works.

Step Call stack Current position in function call Operations Permutations
1 Generate Permutations call 1 Position 0 is Available Push number 1 at position 0.
Mark position 0 as Taken.
[ 1 ]
2 Generate Permutations call 2 Position 0 ( Taken ), Position 1 ( Available ) Push number 2 at position 1.
Mark position 1 as Taken.
[ 1, 2 ]
3 Generate Permutations call 3 Position 0 and 1 ( Taken ), Position 2 ( Available ) Push number 3 at position 2.
Mark position 2 as Taken.
[ 1, 2, 3 ]
4 Generate Permutations call 4 Size of permutation array equals the size of the array. Print
Return
[ 1, 2, 3 ]
5 Return in
Generate Permutations call 3
Reverse the operations
Position 0, 1 and 2 ( Taken ) Pop 3
Mark position 2 as Available.
For Loop: Position limit reached.
Return
[ 1, 2 ]
6 Return in
Generate Permutations call 2
Reverse the operations
Position 0 and 1 ( Taken ), Position 2 ( Available ) Pop 2
Mark position 1 as Available.
For Loop: Go to position 2
Push 3
Mark position 2 as Taken.
[ 1, 3 ]
7 Generate Permutations call 5 Position 0 and 2 ( Taken ), Position 1 ( Available ) Mark position 1 as Taken.
Push 2
[ 1, 3, 2 ]
8 Generate Permutations call 6 Size of permutation array equals the size of the array Print
Return
[ 1, 3, 2 ]


Java

Generating permutations using recursion in Java.


C++

Generating permutations using recursion in C++.


Generating permutations using recursion in Python.

#!/usr/bin/python3

# Generate permutations using recursion
def Generate(permutation, elements, positions):
    
   if( len(permutation) == len(elements) ):

       for it in permutation:
          print(it, end=' ')
       print('\n')

   else:

       for i in range (0, len(elements)):

           if (positions[i]):
               continue

           # Set the position (taken), append the element
           positions[i] = True;
           permutation.append(elements[i]);

           Generate (permutation, elements, positions);
 
           # Remove the element, reset the position (available), 
           permutation.pop();
           positions[i] = False;
           

elements = []
permutation = []
size = input("Size : ")
for i in range(0, int(size)):
   x = input("Element " + str(i) + " : ")
   elements.append(x)

positions = [False] * int(size)

print("\nPermutations\n")
Generate(permutation, elements, positions);

Output

Size : 3
Element 0 : 1
Element 1 : 2
Element 2 : 3

Permutations

1 2 3 

1 3 2 

2 1 3 

2 3 1 

3 1 2 

3 2 1 

Copyright (c) 2019-2021, Algotree.org.
All rights reserved.