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.
This is a companion discussion topic for the original entry at http://iq.opengenus.org/heaps-algorithm-for-generating-permutations/