# Heap’s algorithm for generating permutations

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, 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.