Heap’s algorithm for generating permutations

Reading time: 30 minutes | Coding time: 10 minutes

Heap's Algorithm is used to generate all the possible permutation of n-decimals of a number.The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 elements are not disturbed. For N numbers, it takes O(N!) time complexity as there are N! permutations. N! is the factorial of N that is 1 * 2 * ... * (N-1) * N

Example : Number : 798
Question : What are the possible permutation of '798' number having three-decimals ?
Possible Perutation's :

1] 789
2] 798
3] 879
4] 897
5] 978
6] 987

Hence we have 6 total permutation's(including the given number) i.e : n! (3! = 6)

Note:

• Heap's algorithm can be used for sets having distinct elements only
• It can be extended to handle duplicate elements as well

Algorithm

• Step 1 : First we will calculate the all possible permutation of first n - 1 decimal's adjoining the last element to each of these permutations.
• Step 2 : Iterate the loop starting from 0 till i is less than n, if n is odd swap the first and last element, and if n is even then swap the i'th element and the last element.
• Step 3 : In above every iteration the algorithm will produce all the permutations of n decimal's that end with the current last element.

Explanation

Example: Calculate all possible permutations of given series -> 3 1 2

• Step 1 : According to step-1 of Algorithm, from a given series of decimal's/ integers, the first n - 1 i.e in above case n is 3 hence (n - 1 = 2) integer's are taken into consideration.
• Step 2 : Further stack frames will be loaded with 3, 2, 1 on the top, and stack will unwind for value 1-will get poped from the memory heap and will lead to first permutation 3 1 2.
• Step 3 : Next vaule 2 will get poped from memory stack as size contains value 2 which is even thus for i = 0 , index with 0 and 1 will get swapped in this iteration and we will get the next permutation 1 3 2.
• Step 4 : Similarly now memory stack contatins only value 3 hence 3 also get poped out and for value 3 the inner for loop get iterated starting with i = 0, again recusively call is undertaken and a size (3 - 1 = 2) is passed on to the function and we get the next permutation 2 3 1. After getting this permutation inner size value is 2 which is even hence index 0 and (2 - 1 = 1) is swapped and we get permutation as 3 2 1.
• Step 5 : Further for size = 3 we get an index 0 and 2 to be swapped when memory stack is unwinded for last value hence the permutations are 1 2 3 and lastly inner size value is 2 getting index as 0 and 1 to be swapped from previous permutation, hence the last permutation we are getting is 2 1 3.

Implementation

#include <iostream>
void displayPermutation(unsigned int arr[], unsigned int n)
{
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";

    std::cout << "\n";
}

void heapsAlgorithm(unsigned int arr[], unsigned int size, unsigned int n)
{
    // permutation will be displayed when size becomes 1.
    if (size == 1)
    {
        displayPermutation(arr, n);
        return;
    }

    for (int i = 0; i < size; i++)
    {
        heapsAlgorithm(arr, size - 1, n);

        //size is odd, swap first and last element
        if (size % 2 == 1)
            std::swap(arr[0], arr[size - 1]);

        //  size is even, swap ith and last element
        else
            std::swap(arr[i], arr[size - 1]);
    }
}

int main()
{
    unsigned int n;
    std::cout << "\nEnter the value of n(number of decimal's : )";
    std::cin >> n;
    unsigned int arr[n];
    std::cout << "\nEnter the " << n << " decimal's : ";
    for (int i = 0; i < n; ++i)
    {
        std::cin >> arr[i];
    }

    heapsAlgorithm(arr, n, n);
}

Complexity

• Average case time complexity: Θ(n!)
• Space complexity: Θ(n)

where N is the number of decimal's in number.

Further reading

• Lexicographical (Next)Permutation Algorithm.