Generating permutations using recursion

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 ]
…

Program for generating permutations using recursion 

# 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 

#include<iostream>
#include<vector>

using namespace std;

// Generate permutations using recursion
void Generate (vector<int>& permutation, vector<int>& elements, vector<bool>& positions) {
    
   // Print the generated permutation
   if (permutation.size() == elements.size()) {

       for (auto& it : permutation)
           cout << it << " ";
       cout << endl;

   } else {

       for (int i=0; i<elements.size(); i++) {

           if (positions[i])
               continue;

           // Set the position (taken), add the element
           positions[i] = true;
           permutation.push_back(elements[i]);

           Generate (permutation, elements, positions);
    
           // Remove the element, reset the position (available), 
           permutation.pop_back();
           positions[i] = false;
      }   

   }   
}

int main() {

    int size, num;
    cout << "Size: ";
    cin >> size;
 
    vector<int> permutation;
    vector<int> elements;
    vector<bool> positions(size, false);

    for (int i=0; i<size; i++) {
        cout << "Element " << i << " : ";
        cin >> num;
        elements.push_back(num);
    }

    cout << "\nPermutations" << endl;

    Generate (permutation, elements, positions);

    return 0;
}

Output

Size: 4
Element 0 : 4
Element 1 : 8
Element 2 : 1
Element 3 : 3

Permutations
4 8 1 3 
4 8 3 1 
4 1 8 3 
4 1 3 8 
4 3 8 1 
4 3 1 8 
8 4 1 3 
8 4 3 1 
8 1 4 3 
8 1 3 4 
8 3 4 1 
8 3 1 4 
1 4 8 3 
1 4 3 8 
1 8 4 3 
1 8 3 4 
1 3 4 8 
1 3 8 4 
3 4 8 1 
3 4 1 8 
3 8 4 1 
3 8 1 4 
3 1 4 8 
3 1 8 4 

import java.util.*;

class Permutation {

    public static void Generate ( ArrayList<Integer> permutation, ArrayList<Integer> elements, Boolean[] positions ) {

        if ( permutation.size() == elements.size() ) {

            for ( int i = 0; i < elements.size(); i++ )
                System.out.print(permutation.get(i)+" ");
            System.out.println();

        } else {
            for (int i = 0; i < elements.size(); i++ ) {
                if ( positions[i] )
                    continue;

                positions[i] = Boolean.TRUE;
                permutation.add(elements.get(i));

                Generate( permutation, elements, positions );

                permutation.remove(permutation.size()-1);
                positions[i] = Boolean.FALSE;
            }
        }
    }

    public static void main (String[] args) {

        int size, num;

        Scanner sc = new Scanner ( System.in );

        System.out.print( "Size: " );
        size = sc.nextInt();

        ArrayList<Integer> permutation = new ArrayList<Integer>();
        ArrayList<Integer> elements = new ArrayList<Integer>();
        Boolean [] positions = new Boolean [size];

        Arrays.fill(positions, Boolean.FALSE);

        for (int i = 0; i < size ; i++ ) {
            System.out.print( "Element " + i + " : ");
            num = sc.nextInt();
            elements.add(num);
        }

        System.out.println( "\nPermutations" );
        Generate ( permutation, elements, positions );
    }
}

Output

Size: 4
Element 0 : 4
Element 1 : 8
Element 2 : 1
Element 3 : 3

Permutations
4 8 1 3 
4 8 3 1 
4 1 8 3 
4 1 3 8 
4 3 8 1 
4 3 1 8 
8 4 1 3 
8 4 3 1 
8 1 4 3 
8 1 3 4 
8 3 4 1 
8 3 1 4 
1 4 8 3 
1 4 3 8 
1 8 4 3 
1 8 3 4 
1 3 4 8 
1 3 8 4 
3 4 8 1 
3 4 1 8 
3 8 4 1 
3 8 1 4 
3 1 4 8 
3 1 8 4

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