Heap's Algorithm for generating permutations

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: 

1. 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.
2. If n is odd, swap the first and last element and if n is even, then swap the i^th element (i is the counter starting from 0) and the last element and repeat the above algorithm till i is less than n.
3. In each iteration, the algorithm will produce all the permutations that end with the current last element.

Implementation:  

// C++ program to print all permutations using // Heap's algorithm #include <bits/stdc++.h> using namespace std; // Prints the array void printArr(int a[], int n) {  for (int i = 0; i < n; i++)  cout << a[i] << " ";  printf("\n"); } // 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);  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 code int main() {  int a[] = { 1, 2, 3 };  int n = sizeof a / sizeof a[0];  heapPermutation(a, n, n);  return 0; } 

// Java program to print all permutations using // Heap's algorithm import 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. 

# Python program to print all permutations using # Heap's algorithm # Generating permutation using Heap Algorithm def 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 code a = [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# program to print all permutations using // Heap's algorithm using 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*/ 

<script> // JavaScript program to print all permutations using // Heap's algorithm // Prints the array function printArr(a,n) {  document.write(a.join(" ")+"<br>");   } // Generating permutation using Heap Algorithm function 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 code let a=[1, 2, 3]; heapPermutation(a, a.length, a.length); // This code is contributed by rag2127 </script>   

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