Permutations of an Array in lexicographical order.
Given an array arr[] of distinct integers, the task is to print all the possible permutations in lexicographical order.
Examples:
Input: arr = [1, 2, 3]
Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]Input: arr = [1, 2]
Output: [[1, 2], [2, 1]]Input: arr = [1]
Output: [[1]]
Approach: To solve the problem follow the below idea:
- In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting.
- This problem can be solved using Backtracking. We swap the ith index with all indexes after ith index and this way recursively we can generate all the permutaions.
Steps to solve the problem:
- Sort the input array initially.
- We define a recursive function with parameters as the ith index at which we have to take decisions and a given array.
- Here we have two options: not to Right rotate from the ith index to another index after i and to Rotate it with other indexes after i.
- Run a loop from (i+1,n) denoted by j and Right rotate the segment arr[i…j] and make the recursive call for (i + 1)th index then Left rotate the segment arr[i…j] to undo the changes of the Right rotate to restore the array to the original configuration.
- Base case: if we are at the end of the array then we can print the array and return.
Why rotation of elements works to generate permutations in lexicographical order:
Consider arr = [1, 2, 3],
- If we swap arr[0] with arr[2] it becomes [3, 2, 1] :
- Now we are taking a decision for arr[1] element, we have two choices:
- If we do not swap arr[1] with arr[2] then arr = [3, 2, 1]
- If we swap arr[1] with arr[2] then arr = [3, 1, 2]
- We observed here is [3, 2, 1] appears before [3, 1, 2] which is not the case of lexicographical order. But, if we Right rotate arr[0…2] then arr becomes [3, 1, 2], by rotating sorted order of elements remained conserved and with this elements get swapped automatically:
- Now we are taking a decision for arr[1] element, we have two choices:
- If we do not swap arr[1] with arr[2] then arr = [3, 1, 2]
- If we swap arr[1] with arr[2] then arr = [3, 2, 1]
- Now [3, 1, 2] appears before [3, 2, 1], this is lexicographical order.
Below is the code for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to right rotate the segement // arr[i....j] of arr void RightRotate( int arr[], int i, int j) { int temp = arr[j]; for ( int k = j; k > i; k--) { arr[k] = arr[k - 1]; } arr[i] = temp; } // Function to Left rotate the segement // arr[i....j] of arr void LeftRotate( int arr[], int i, int j) { int temp = arr[i]; for ( int k = i; k < j; k++) { arr[k] = arr[k + 1]; } arr[j] = temp; } void PrintPermutations( int arr[], int i, int n) { // Base case if i reaches end of the // array and there is no element // to swap with if (i == n - 1) { for ( int i = 0; i < n; i++) { cout << arr[i] << " " ; } cout << endl; return ; } // If do not rotate any segement // starting from i+1th index PrintPermutations(arr, i + 1, n); // If we rotate segement then we can have // rotation of segement arr[i....j] for ( int j = i + 1; j < n; j++) { RightRotate(arr, i, j); PrintPermutations(arr, i + 1, n); LeftRotate(arr, i, j); } } /// Drivers code int main() { int arr[] = { 2, 1, 3 }; int N = sizeof (arr) / sizeof (arr[0]); sort(arr, arr + N); // Function Call cout << "Permutations are below" << endl; PrintPermutations(arr, 0, N); return 0; } |
Java
// Java code for the above approach import java.util.Arrays; class GFG { // Function to right rotate the segement // arr[i....j] of arr static void RightRotate( int arr[], int i, int j) { int temp = arr[j]; for ( int k = j; k > i; k--) { arr[k] = arr[k - 1 ]; } arr[i] = temp; } // Function to Left rotate the segement // arr[i....j] of arr static void LeftRotate( int arr[], int i, int j) { int temp = arr[i]; for ( int k = i; k < j; k++) { arr[k] = arr[k + 1 ]; } arr[j] = temp; } static void PrintPermutations( int arr[], int i, int n) { // Base case if i reaches end of the // array and there is no element // to swap with if (i == n - 1 ) { for ( int k = 0 ; k < n; k++) { System.out.print(arr[k] + " " ); } System.out.println(); return ; } // If do not rotate any segement // starting from i+1th index PrintPermutations(arr, i + 1 , n); // If we rotate segement then we can have // rotation of segement arr[i....j] for ( int j = i + 1 ; j < n; j++) { RightRotate(arr, i, j); PrintPermutations(arr, i + 1 , n); LeftRotate(arr, i, j); } } // Drivers code public static void main(String[] args) { int arr[] = { 2 , 1 , 3 }; int N = arr.length; Arrays.sort(arr); // Function Call System.out.println( "Permutations are below" ); PrintPermutations(arr, 0 , N); } } // This code is contributed by Sakshi |
Python3
# Python code for the above approach def right_rotate(arr, i, j): temp = arr[j] for k in range (j, i, - 1 ): arr[k] = arr[k - 1 ] arr[i] = temp def left_rotate(arr, i, j): temp = arr[i] for k in range (i, j): arr[k] = arr[k + 1 ] arr[j] = temp def print_permutations(arr, i, n): # Base case: if i reaches the end of the array # and there is no element to swap with if i = = n - 1 : print ( * arr) return # If we do not rotate any segment starting from the (i+1)th index print_permutations(arr, i + 1 , n) # If we rotate a segment, then we can have rotation of segment arr[i....j] for j in range (i + 1 , n): right_rotate(arr, i, j) print_permutations(arr, i + 1 , n) left_rotate(arr, i, j) # Driver code if __name__ = = "__main__" : arr = [ 2 , 1 , 3 ] N = len (arr) arr.sort() # Function Call print ( "Permutations are below:" ) print_permutations(arr, 0 , N) #This Code is Contributed by chinmaya121221 |
C#
using System; class Program { // Function to right rotate the segment arr[i....j] of arr static void RightRotate( int [] arr, int i, int j) { int temp = arr[j]; for ( int k = j; k > i; k--) { arr[k] = arr[k - 1]; } arr[i] = temp; } // Function to left rotate the segment arr[i....j] of arr static void LeftRotate( int [] arr, int i, int j) { int temp = arr[i]; for ( int k = i; k < j; k++) { arr[k] = arr[k + 1]; } arr[j] = temp; } // Function to print permutations of the array static void PrintPermutations( int [] arr, int i, int n) { // Base case: if i reaches the end of the array and there are no elements to swap with if (i == n - 1) { foreach ( int num in arr) { Console.Write(num + " " ); } Console.WriteLine(); return ; } // If we do not rotate any segment starting from the i+1th index PrintPermutations(arr, i + 1, n); // If we rotate a segment, we can have rotations of the segment arr[i....j] for ( int j = i + 1; j < n; j++) { RightRotate(arr, i, j); PrintPermutations(arr, i + 1, n); LeftRotate(arr, i, j); } } // Driver code static void Main() { int [] arr = { 2, 1, 3 }; int N = arr.Length; // Sort the array Array.Sort(arr); // Function Call Console.WriteLine( "Permutations are below:" ); PrintPermutations(arr, 0, N); } } |
Javascript
// Function to right rotate the segment arr[i....j] of arr function rightRotate(arr, i, j) { const temp = arr[j]; for (let k = j; k > i; k--) { arr[k] = arr[k - 1]; } arr[i] = temp; } // Function to left rotate the segment arr[i....j] of arr function leftRotate(arr, i, j) { const temp = arr[i]; for (let k = i; k < j; k++) { arr[k] = arr[k + 1]; } arr[j] = temp; } // Function to print permutations of the array function printPermutations(arr, i, n) { // Base case: if i reaches the end of the array and there are no elements to swap with if (i === n - 1) { console.log(arr.join( " " )); return ; } // If we do not rotate any segment starting from the i+1th index printPermutations(arr, i + 1, n); // If we rotate a segment, we can have rotations of the segment arr[i....j] for (let j = i + 1; j < n; j++) { rightRotate(arr, i, j); printPermutations(arr, i + 1, n); leftRotate(arr, i, j); } } // Driver code function main() { const arr = [2, 1, 3]; const N = arr.length; // Sort the array arr.sort((a, b) => a - b); // Function Call console.log( "Permutations are below:" ); printPermutations(arr, 0, N); } // Call the main function main(); |
Output
Permutations are below 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
Time Complexity: O(N*N!)
Auxillary space: O(N), where N is the number of elements in the array.