# Heap’s algorithm for generating permutations

Get this book -> Problems on Array: For Interviews and Competitive Programming

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. 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**2 3 1**.**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 areand 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**1 2 3**.**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.