Heaps algorithms are used to generate all the possible permutations of n-decimals of a number. This algorithm minimizes the movements, basically, it generates each permutation from the previous one by interchanging a single element while other elements are not disturbed.
For n numbers, it takes O(n!) time complexity as there are n! Permutations.
For example:
Let n = 789
Possible permutations are:
789, 798, 879, 897, 987, 978
So, here we have 6 total permutations i.e N! (3!(3 decimal digits) = 6)
Algorithm:
- Calculate all the possible permutations of the first n-1 digits adjoining the last element to each of these permutations.
- Iterate the digits, and check if n is an odd number then swap the first digit with the last digit and if n is an even number then swap the ith element with the last element.
- After repeating the above steps, Algorithm produces all the permutations of N.
Code Implementation
#include <bits/stdc++.h>
using namespace std;
void printArr(int a[], int n)
{
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout<<endl;
}
void heapPermutation(int a[], int size, int n)
{
if (size == 1) {
printArr(a, n);
return;
}
for (int i = 0; i < size; i++) {
heapPermutation(a, size - 1, n);
if (size % 2 == 1)
swap(a[0], a[size - 1]);
else
swap(a[i], a[size - 1]);
}
}
int main()
{
int a[] = { 7, 8, 9 };
int n = sizeof a / sizeof a[0];
heapPermutation(a, n, n);
return 0;
}
class HeapAlgo {
void printArr(int a[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(a[i] + " ");
System.out.println();
}
void heapPermutation(int a[], int size, int n)
{
if (size == 1)
printArr(a, n);
for (int i = 0; i < size; i++) {
heapPermutation(a, size - 1, n);
if (size % 2 == 1) {
int temp = a[0];
a[0] = a[size - 1];
a[size - 1] = temp;
}
else {
int temp = a[i];
a[i] = a[size - 1];
a[size - 1] = temp;
}
}
}
public static void main(String args[])
{
HeapAlgo obj = new HeapAlgo();
int a[] = { 1, 2, 3 };
obj.heapPermutation(a, a.length, a.length);
}
}
def heapPermutation(a, size):
if size == 1:
print(a)
return
for i in range(size):
heapPermutation(a, size-1)
if size & 1:
a[0], a[size-1] = a[size-1], a[0]
else:
a[i], a[size-1] = a[size-1], a[i]
a = [1, 2, 3]
n = len(a)
heapPermutation(a, n)
This article tried to discuss the How to Implement Heap Algorithm for Generating Permutations. Hope this blog helps you understand the concept. To practice problems on Heap you can check out MYCODE | Competitive Programming – Heaps.