Given an array arr[] of size N, the task is to generate and print all permutations of the given array. Examples:
Input: arr[] = {1, 2} Output: 1 2 2 1 Input: {0, 1, 2} Output: 0 1 2 1 0 2 0 2 1 2 0 1 1 2 0 2 1 0
Approach: The recursive methods to solve the above problems are discussed here and here. In this post, an iterative method to output all permutations for a given array will be discussed. The iterative method acts as a state machine. When the machine is called, it outputs a permutation and move to the next one. To begin, we need an integer array Indexes to store all the indexes of the input array, and values in array Indexes are initialized to be 0 to n – 1. What we need to do is to permute the Indexes array. During the iteration, we find the smallest index Increase in the Indexes array such that Indexes[Increase] < Indexes[Increase + 1], which is the first “value increase”. Then, we have Indexes[0] > Indexes[1] > Indexes[2] > … > Indexes[Increase], which is a tract of decreasing values from index[0]. The next steps will be:
- Find the index mid such that Indexes[mid] is the greatest with the constraints that 0 ? mid ? Increase and Indexes[mid] < Indexes[Increase + 1]; since array Indexes is reversely sorted from 0 to Increase, this step can use binary search.
- Swap Indexes[Increase + 1] and Indexes[mid].
- Reverse Indexes[0] to Indexes[Increase].
When the values in Indexes become n – 1 to 0, there is no “value increase”, and the algorithm terminates. To output the combination, we loop through the index array and the values of the integer array are the indexes of the input array. The following image illustrates the iteration in the algorithm. 
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;template <typename T>class AllPermutation {private: // The input array for permutation const T* Arr; // Length of the input array const int Length; // Index array to store indexes of input array int* Indexes; // The index of the first "increase" // in the Index array which is the smallest // i such that Indexes[i] < Indexes[i + 1] int Increase;public: // Constructor AllPermutation(T* arr, int length) : Arr(arr), Length(length) { this->Indexes = nullptr; this->Increase = -1; } // Destructor ~AllPermutation() { if (this->Indexes != nullptr) { delete[] this->Indexes; } } // Initialize and output // the first permutation void GetFirst() { // Allocate memory for Indexes array this->Indexes = new int[this->Length]; // Initialize the values in Index array // from 0 to n - 1 for (int i = 0; i < this->Length; ++i) { this->Indexes[i] = i; } // Set the Increase to 0 // since Indexes[0] = 0 < Indexes[1] = 1 this->Increase = 0; // Output the first permutation this->Output(); } // Function that returns true if it is // possible to generate the next permutation bool HasNext() { // When Increase is in the end of the array, // it is not possible to have next one return this->Increase != (this->Length - 1); } // Output the next permutation void GetNext() { // Increase is at the very beginning if (this->Increase == 0) { // Swap Index[0] and Index[1] this->Swap(this->Increase, this->Increase + 1); // Update Increase this->Increase += 1; while (this->Increase < this->Length - 1 && this->Indexes[this->Increase] > this->Indexes[this->Increase + 1]) { ++this->Increase; } } else { // Value at Indexes[Increase + 1] is greater than Indexes[0] // no need for binary search, // just swap Indexes[Increase + 1] and Indexes[0] if (this->Indexes[this->Increase + 1] > this->Indexes[0]) { this->Swap(this->Increase + 1, 0); } else { // Binary search to find the greatest value // which is less than Indexes[Increase + 1] int start = 0; int end = this->Increase; int mid = (start + end) / 2; int tVal = this->Indexes[this->Increase + 1]; while (!(this->Indexes[mid] < tVal && this->Indexes[mid - 1] > tVal)) { if (this->Indexes[mid] < tVal) { end = mid - 1; } else { start = mid + 1; } mid = (start + end) / 2; } // Swap this->Swap(this->Increase + 1, mid); } // Invert 0 to Increase for (int i = 0; i <= this->Increase / 2; ++i) { this->Swap(i, this->Increase - i); } // Reset Increase this->Increase = 0; } this->Output(); }private: // Function to output the input array void Output() { for (int i = 0; i < this->Length; ++i) { // Indexes of the input array // are at the Indexes array cout << (this->Arr[this->Indexes[i]]) << " "; } cout << endl; } // Swap two values in the Indexes array void Swap(int p, int q) { int tmp = this->Indexes[p]; this->Indexes[p] = this->Indexes[q]; this->Indexes[q] = tmp; }};// Driver codeint main(){ int arr[] = { 0, 1, 2 }; AllPermutation<int> perm(arr, sizeof(arr) / sizeof(int)); perm.GetFirst(); while (perm.HasNext()) { perm.GetNext(); } return 0;} |
Java
// Java implementation of the approachclass AllPermutation { // The input array for permutation private final int Arr[]; // Index array to store indexes of input array private int Indexes[]; // The index of the first "increase" // in the Index array which is the smallest // i such that Indexes[i] < Indexes[i + 1] private int Increase; // Constructor public AllPermutation(int arr[]) { this.Arr = arr; this.Increase = -1; this.Indexes = new int[this.Arr.length]; } // Initialize and output // the first permutation public void GetFirst() { // Allocate memory for Indexes array this.Indexes = new int[this.Arr.length]; // Initialize the values in Index array // from 0 to n - 1 for (int i = 0; i < Indexes.length; ++i) { this.Indexes[i] = i; } // Set the Increase to 0 // since Indexes[0] = 0 < Indexes[1] = 1 this.Increase = 0; // Output the first permutation this.Output(); } // Function that returns true if it is // possible to generate the next permutation public boolean HasNext() { // When Increase is in the end of the array, // it is not possible to have next one return this.Increase != (this.Indexes.length - 1); } // Output the next permutation public void GetNext() { // Increase is at the very beginning if (this.Increase == 0) { // Swap Index[0] and Index[1] this.Swap(this.Increase, this.Increase + 1); // Update Increase this.Increase += 1; while (this.Increase < this.Indexes.length - 1 && this.Indexes[this.Increase] > this.Indexes[this.Increase + 1]) { ++this.Increase; } } else { // Value at Indexes[Increase + 1] is greater than Indexes[0] // no need for binary search, // just swap Indexes[Increase + 1] and Indexes[0] if (this.Indexes[this.Increase + 1] > this.Indexes[0]) { this.Swap(this.Increase + 1, 0); } else { // Binary search to find the greatest value // which is less than Indexes[Increase + 1] int start = 0; int end = this.Increase; int mid = (start + end) / 2; int tVal = this.Indexes[this.Increase + 1]; while (!(this.Indexes[mid]<tVal&& this.Indexes[mid - 1]> tVal)) { if (this.Indexes[mid] < tVal) { end = mid - 1; } else { start = mid + 1; } mid = (start + end) / 2; } // Swap this.Swap(this.Increase + 1, mid); } // Invert 0 to Increase for (int i = 0; i <= this.Increase / 2; ++i) { this.Swap(i, this.Increase - i); } // Reset Increase this.Increase = 0; } this.Output(); } // Function to output the input array private void Output() { for (int i = 0; i < this.Indexes.length; ++i) { // Indexes of the input array // are at the Indexes array System.out.print(this.Arr[this.Indexes[i]]); System.out.print(" "); } System.out.println(); } // Swap two values in the Indexes array private void Swap(int p, int q) { int tmp = this.Indexes[p]; this.Indexes[p] = this.Indexes[q]; this.Indexes[q] = tmp; }}// Driver codeclass AppDriver { public static void main(String args[]) { int[] arr = { 0, 1, 2 }; AllPermutation perm = new AllPermutation(arr); perm.GetFirst(); while (perm.HasNext()) { perm.GetNext(); } }}// This code is contributed by ghanshyampandey |
C#
// C# implementation of the approachusing System;namespace Permutation {class AllPermutation<T> { // The input array for permutation private readonly T[] Arr; // Index array to store indexes of input array private int[] Indexes; // The index of the first "increase" // in the Index array which is the smallest // i such that Indexes[i] < Indexes[i + 1] private int Increase; // Constructor public AllPermutation(T[] arr) { this.Arr = arr; this.Increase = -1; } // Initialize and output // the first permutation public void GetFirst() { // Allocate memory for Indexes array this.Indexes = new int[this.Arr.Length]; // Initialize the values in Index array // from 0 to n - 1 for (int i = 0; i < Indexes.Length; ++i) { this.Indexes[i] = i; } // Set the Increase to 0 // since Indexes[0] = 0 < Indexes[1] = 1 this.Increase = 0; // Output the first permutation this.Output(); } // Function that returns true if it is // possible to generate the next permutation public bool HasNext() { // When Increase is in the end of the array, // it is not possible to have next one return this.Increase != (this.Indexes.Length - 1); } // Output the next permutation public void GetNext() { // Increase is at the very beginning if (this.Increase == 0) { // Swap Index[0] and Index[1] this.Swap(this.Increase, this.Increase + 1); // Update Increase this.Increase += 1; while (this.Increase < this.Indexes.Length - 1 && this.Indexes[this.Increase] > this.Indexes[this.Increase + 1]) { ++this.Increase; } } else { // Value at Indexes[Increase + 1] is greater than Indexes[0] // no need for binary search, // just swap Indexes[Increase + 1] and Indexes[0] if (this.Indexes[this.Increase + 1] > this.Indexes[0]) { this.Swap(this.Increase + 1, 0); } else { // Binary search to find the greatest value // which is less than Indexes[Increase + 1] int start = 0; int end = this.Increase; int mid = (start + end) / 2; int tVal = this.Indexes[this.Increase + 1]; while (!(this.Indexes[mid]<tVal&& this.Indexes[mid - 1]> tVal)) { if (this.Indexes[mid] < tVal) { end = mid - 1; } else { start = mid + 1; } mid = (start + end) / 2; } // Swap this.Swap(this.Increase + 1, mid); } // Invert 0 to Increase for (int i = 0; i <= this.Increase / 2; ++i) { this.Swap(i, this.Increase - i); } // Reset Increase this.Increase = 0; } this.Output(); } // Function to output the input array private void Output() { for (int i = 0; i < this.Indexes.Length; ++i) { // Indexes of the input array // are at the Indexes array Console.Write(this.Arr[this.Indexes[i]]); Console.Write(" "); } Console.WriteLine(); } // Swap two values in the Indexes array private void Swap(int p, int q) { int tmp = this.Indexes[p]; this.Indexes[p] = this.Indexes[q]; this.Indexes[q] = tmp; }}// Driver codeclass AppDriver { static void Main() { int[] arr = { 0, 1, 2 }; AllPermutation<int> perm = new AllPermutation<int>(arr); perm.GetFirst(); while (perm.HasNext()) { perm.GetNext(); } }}} |
Python3
# Python 3 implementation of the approachclass AllPermutation : # The input array for permutation Arr = None # Index array to store indexes of input array Indexes = None # The index of the first "increase" # in the Index array which is the smallest # i such that Indexes[i] < Indexes[i + 1] Increase = 0 # Constructor def __init__(self, arr) : self.Arr = arr self.Increase = -1 self.Indexes = [0] * (len(self.Arr)) # Initialize and output # the first permutation def GetFirst(self) : # Allocate memory for Indexes array self.Indexes = [0] * (len(self.Arr)) # Initialize the values in Index array # from 0 to n - 1 i = 0 while (i < len(self.Indexes)) : self.Indexes[i] = i i += 1 # Set the Increase to 0 # since Indexes[0] = 0 < Indexes[1] = 1 self.Increase = 0 # Output the first permutation self.Output() # Function that returns true if it is # possible to generate the next permutation def HasNext(self) : # When Increase is in the end of the array, # it is not possible to have next one return self.Increase != (len(self.Indexes) - 1) # Output the next permutation def GetNext(self) : # Increase is at the very beginning if (self.Increase == 0) : # Swap Index[0] and Index[1] self.Swap(self.Increase, self.Increase + 1) # Update Increase self.Increase += 1 while (self.Increase < len(self.Indexes) - 1 and self.Indexes[self.Increase] > self.Indexes[self.Increase + 1]) : self.Increase += 1 else : # Value at Indexes[Increase + 1] is greater than Indexes[0] # no need for binary search, # just swap Indexes[Increase + 1] and Indexes[0] if (self.Indexes[self.Increase + 1] > self.Indexes[0]) : self.Swap(self.Increase + 1, 0) else : # Binary search to find the greatest value # which is less than Indexes[Increase + 1] start = 0 end = self.Increase mid = int((start + end) / 2) tVal = self.Indexes[self.Increase + 1] while (not (self.Indexes[mid] < tVal and self.Indexes[mid - 1] > tVal)) : if (self.Indexes[mid] < tVal) : end = mid - 1 else : start = mid + 1 mid = int((start + end) / 2) # Swap self.Swap(self.Increase + 1, mid) # Invert 0 to Increase i = 0 while (i <= int(self.Increase / 2)) : self.Swap(i, self.Increase - i) i += 1 # Reset Increase self.Increase = 0 self.Output() # Function to output the input array def Output(self) : i = 0 while (i < len(self.Indexes)) : # Indexes of the input array # are at the Indexes array print(self.Arr[self.Indexes[i]], end ="") print(" ", end ="") i += 1 print() # Swap two values in the Indexes array def Swap(self, p, q) : tmp = self.Indexes[p] self.Indexes[p] = self.Indexes[q] self.Indexes[q] = tmp # Driver codeclass AppDriver : @staticmethod def main( args) : arr = [0, 1, 2] perm = AllPermutation(arr) perm.GetFirst() while (perm.HasNext()) : perm.GetNext() if __name__=="__main__": AppDriver.main([]) # This code is contributed by aadityaburujwale. |
Javascript
// JavaScript implementation of the approachclass AllPermutation { // The input array for permutation constructor(arr) { this.Arr = arr; this.Increase = -1; this.Indexes = new Array(this.Arr.length); } // Initialize and output the first permutation GetFirst() { // Allocate memory for Indexes array this.Indexes = new Array(this.Arr.length); // Initialize the values in Index array from 0 to n - 1 for (let i = 0; i < this.Indexes.length; i++) { this.Indexes[i] = i; } // Set the Increase to 0 // since Indexes[0] = 0 < Indexes[1] = 1 this.Increase = 0; // Output the first permutation this.Output(); } // Function that returns true if it is possible to generate the next permutation HasNext() { // When Increase is in the end of the array, it is not possible to have next one return this.Increase !== this.Indexes.length - 1; } // Output the next permutation GetNext() { // Increase is at the very beginning if (this.Increase === 0) { // Swap Index[0] and Index[1] this.Swap(this.Increase, this.Increase + 1); // Update Increase this.Increase++; while ( this.Increase < this.Indexes.length - 1 && this.Indexes[this.Increase] > this.Indexes[this.Increase + 1] ) { this.Increase++; } } else { // Value at Indexes[Increase + 1] is greater than Indexes[0] // no need for binary search, just swap Indexes[Increase + 1] and Indexes[0] if (this.Indexes[this.Increase + 1] > this.Indexes[0]) { this.Swap(this.Increase + 1, 0); } else { // Binary search to find the greatest value which is less than Indexes[Increase + 1] let start = 0; let end = this.Increase; let mid = Math.floor((start + end) / 2); let tVal = this.Indexes[this.Increase + 1]; while (!(this.Indexes[mid] < tVal && this.Indexes[mid - 1] > tVal)) { if (this.Indexes[mid] < tVal) { end = mid - 1; } else { start = mid + 1; } mid = Math.floor((start + end) / 2); } // Swap this.Swap(this.Increase + 1, mid); } // Invert 0 to Increase for (let i = 0; i <= this.Increase / 2; i++) { this.Swap(i, this.Increase - i); } // Reset Increase this.Increase = 0; } this.Output(); } Output() { let temp = ""; for (var i = 0; i < this.Indexes.length; i++) { temp += this.Indexes[i]+" "; //console.log(this.Arr[this.Indexes[i]] + " "); } console.log(temp);}Swap(p, q) { var tmp = this.Indexes[p]; this.Indexes[p] = this.Indexes[q]; this.Indexes[q] = tmp;}}let arr = [0, 1, 2];let perm = new AllPermutation(arr);perm.GetFirst();while (perm.HasNext()) { perm.GetNext();}// This code is contributed by abn95knd1. |
Output:
0 1 2 1 0 2 0 2 1 2 0 1 1 2 0 2 1 0
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!
