Heap’s algorithm is used to generate all permutations of n objects. The idea is to generate each permutation from the previous permutation by choosing a pair of elements to interchange, without disturbing the other n-2 elements.
Following is the illustration of generating all the permutations of n given numbers.
Example:
Input: 1 2 3
Output: 1 2 3
2 1 3
3 1 2
1 3 2
2 3 1
3 2 1
Algorithm:
- The algorithm generates (n-1)! permutations of the first n-1 elements, adjoining the last element to each of these. This will generate all of the permutations that end with the last element.
- If n is odd, swap the first and last element and if n is even, then swap the ith element (i is the counter starting from 0) and the last element and repeat the above algorithm till i is less than n.
- In each iteration, the algorithm will produce all the permutations that end with the current last element.
Implementation:
C++
// C++ program to print all permutations using// Heap's algorithm#include <bits/stdc++.h>using namespace std;// Prints the arrayvoid printArr(int a[], int n){ for (int i = 0; i < n; i++) cout << a[i] << " "; printf("\n");}// Generating permutation using Heap Algorithmvoid heapPermutation(int a[], int size, int n){ // if size becomes 1 then prints the obtained // permutation if (size == 1) { printArr(a, n); return; } for (int i = 0; i < size; i++) { heapPermutation(a, size - 1, n); // if size is odd, swap 0th i.e (first) and // (size-1)th i.e (last) element if (size % 2 == 1) swap(a[0], a[size - 1]); // If size is even, swap ith and // (size-1)th i.e (last) element else swap(a[i], a[size - 1]); }}// Driver codeint main(){ int a[] = { 1, 2, 3 }; int n = sizeof a / sizeof a[0]; heapPermutation(a, n, n); return 0;} |
Java
// Java program to print all permutations using// Heap's algorithmimport java.io.*;class HeapAlgo { // Prints the array void printArr(int a[], int n) { for (int i = 0; i < n; i++) System.out.print(a[i] + " "); System.out.println(); } // Generating permutation using Heap Algorithm void heapPermutation(int a[], int size, int n) { // if size becomes 1 then prints the obtained // permutation if (size == 1) printArr(a, n); for (int i = 0; i < size; i++) { heapPermutation(a, size - 1, n); // if size is odd, swap 0th i.e (first) and // (size-1)th i.e (last) element if (size % 2 == 1) { int temp = a[0]; a[0] = a[size - 1]; a[size - 1] = temp; } // If size is even, swap ith // and (size-1)th i.e last element else { int temp = a[i]; a[i] = a[size - 1]; a[size - 1] = temp; } } } // Driver code public static void main(String args[]) { HeapAlgo obj = new HeapAlgo(); int a[] = { 1, 2, 3 }; obj.heapPermutation(a, a.length, a.length); }}// This code has been contributed by Amit Khandelwal. |
Python3
# Python program to print all permutations using# Heap's algorithm# Generating permutation using Heap Algorithmdef heapPermutation(a, size): # if size becomes 1 then prints the obtained # permutation if size == 1: print(a) return for i in range(size): heapPermutation(a, size-1) # if size is odd, swap 0th i.e (first) # and (size-1)th i.e (last) element # else If size is even, swap ith # and (size-1)th i.e (last) element if size & 1: a[0], a[size-1] = a[size-1], a[0] else: a[i], a[size-1] = a[size-1], a[i]# Driver codea = [1, 2, 3]n = len(a)heapPermutation(a, n)# This code is contributed by ankush_953# This code was cleaned up to by more pythonic by glubs9 |
C#
// C# program to print all permutations using// Heap's algorithmusing System;public class GFG { // Prints the array static void printArr(int[] a, int n) { for (int i = 0; i < n; i++) Console.Write(a[i] + " "); Console.WriteLine(); } // Generating permutation using Heap Algorithm static void heapPermutation(int[] a, int size, int n) { // if size becomes 1 then prints the obtained // permutation if (size == 1) printArr(a, n); for (int i = 0; i < size; i++) { heapPermutation(a, size - 1, n); // if size is odd, swap 0th i.e (first) and // (size-1)th i.e (last) element if (size % 2 == 1) { int temp = a[0]; a[0] = a[size - 1]; a[size - 1] = temp; } // If size is even, swap ith and // (size-1)th i.e (last) element else { int temp = a[i]; a[i] = a[size - 1]; a[size - 1] = temp; } } } // Driver code public static void Main() { int[] a = { 1, 2, 3 }; heapPermutation(a, a.Length, a.Length); }}/* This Java code is contributed by 29AjayKumar*/ |
Javascript
<script>// JavaScript program to print all permutations using// Heap's algorithm// Prints the arrayfunction printArr(a,n){ document.write(a.join(" ")+"<br>"); }// Generating permutation using Heap Algorithmfunction heapPermutation(a,size,n){ // if size becomes 1 then prints the obtained // permutation if (size == 1) printArr(a, n); for (let i = 0; i < size; i++) { heapPermutation(a, size - 1, n); // if size is odd, swap 0th i.e (first) and // (size-1)th i.e (last) element if (size % 2 == 1) { let temp = a[0]; a[0] = a[size - 1]; a[size - 1] = temp; } // If size is even, swap ith // and (size-1)th i.e last element else { let temp = a[i]; a[i] = a[size - 1]; a[size - 1] = temp; } }}// Driver codelet a=[1, 2, 3];heapPermutation(a, a.length, a.length);// This code is contributed by rag2127</script> |
Output
1 2 3 2 1 3 3 1 2 1 3 2 2 3 1 3 2 1
Time Complexity: O(N*N!), where N is the size of the given array.
Auxiliary Space: O(N), for recursive stack space of size N.
References:
1. “https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
This article is contributed by Rahul Agrawal .If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
