Heap Algorithm for Generating Permutations

Last Updated on November 28, 2023 by Ankit Kochar

Heaps algorithms are employed for generating all conceivable permutations of n-decimals within a number. This algorithm minimizes the need for extensive rearrangements, essentially constructing each permutation from its predecessor by swapping a single element while leaving the remaining elements undisturbed.

How to use Heap algorithm for Generating Permutations?

The Heap’s algorithm is a well-known method for generating all permutations of a set. It efficiently produces all permutations of a given sequence in a specific order without recursion. The algorithm minimizes memory usage and executes in a way that it generates each permutation by only swapping elements in the sequence.

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)

Conclusion
In conclusion, the Heap Algorithm stands out as a powerful tool for efficiently generating permutations of elements. By minimizing movements and strategically interchanging single elements while keeping others undisturbed, this algorithm provides an effective means of exploring all possible arrangements. Whether you’re dealing with numbers, characters, or any other elements, Heap’s Algorithm proves to be a versatile solution for permutation generation, offering optimization and simplicity in the process.

FAQs (Frequently Asked Questions) related to Heap Algorithm for Generating Permutations:

Here are some FAQs related to Heap Algorithm for Generating Permutations:

Q1: What is the Heap Algorithm used for?
A1: The Heap Algorithm is primarily used for generating permutations of elements. It efficiently explores all possible arrangements by minimizing movements and interchanging elements strategically.

Q2: How does the Heap Algorithm minimize movements during permutation generation?
A2: The Heap Algorithm achieves minimal movements by generating each permutation from the previous one through the interchange of a single element while leaving the remaining elements undisturbed. This strategic approach contributes to efficiency in the generation process.

Q3: Can the Heap Algorithm be applied to different types of elements, such as numbers or characters?
A3: Yes, the Heap Algorithm is versatile and can be applied to various types of elements, including numbers, characters, or any other data types. Its flexibility makes it a useful tool in diverse programming scenarios.

Q4: Are there situations where the Heap Algorithm may not be the most efficient choice for permutation generation?
A4: While the Heap Algorithm is efficient, it may not be the optimal choice for very large datasets due to its recursive nature. In such cases, alternative algorithms or optimizations may be considered for improved performance.

Q5: How is the Heap Algorithm implemented in programming languages like C++ or Python?
A5: The implementation of the Heap Algorithm varies depending on the programming language. In general, it involves recursive functions or iterative approaches to generate permutations. Specific syntax and details may differ based on the language being used.

Q6: Can the Heap Algorithm handle permutations with repetitions?
A6: The classic Heap Algorithm is designed for generating unique permutations. If permutations with repetitions are required, additional modifications or considerations may be needed in the implementation to accommodate such scenarios.