Generating permutations using recursion

Generating permutations using recursion.

The idea behind generating permutations using recursion is quite simple. Positions vector keeps track of the elements already present in the permutations vector. Each function call tries to add a new element to the permutations list / vector if an empty position is found. If the size of the permutations vector equals the size of the set containing the elements, a permutation has been found.

Below recursion stack explains how the algorithm works.

Step Call stack Current position in function call Operations Permutations
1 Function call 1 0 Push 1
Mark position 0 as filled.
[ 1 ]
2 Function call 2 0 ( Filled ) -> 1 Push 2
Mark position 1 as filled.
[ 1, 2 ]
3 Function call 3 0 , 1 ( Filled ) -> 2 Push 3
Mark position 2 as filled.
[ 1, 2, 3 ]
4 Function call 4 Size of permutation array equals the size of the array. Print
Return
[ 1, 2, 3 ]
5 Function call 3 2 Mark position 2 as empty.
Pop 3
2 -> 3
Position limit reached.
Return
[ 1, 2 ]
6 Function call 2 1 Mark position 1 as empty.
Pop 2
1 -> 2
Push 3
Mark position 2 as filled.
[ 1, 3 ]
7 Function call 5 0 ( Filled ) -> 1 Mark 1 as filled.
Push 2
[ 1, 3, 2 ]
8 Function call 6 Size of permutation array equals the size of the array Print
Return
[ 1, 3, 2 ]

C++ : Implementation of generating permutations using recursion in C++11

Python : Implementation of generating permutations using recursion in Python3

#!/usr/bin/python3

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

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

   else:

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

           if (positions[i]):
               continue

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

           Generate (permutations, elements, positions);
 
           # Reset the position, remove the element
           positions[i] = False;
           permutations.pop();

elements = []
permutations = []
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(permutations, 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-2020, Algotree.org.
All rights reserved.