Given two permutations arrays arr[] and brr[] of the first N Natural Numbers from 1 to N, the task is to find the absolute difference between the positions of their order in lexicographical order.
Examples:
Input: arr[] = {1, 3, 2}, brr[] = {3, 1, 2}
Output: 3
Explanation:
There are 6 possible permutations of the first N(= 3) natural numbers. They are {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}. The position of arr[] is 2 and the position of brr[] is 5. Therefore, the answer is |2 – 5| = 3.Input: arr[] = {1, 3, 2, 4}, brr[] = {1, 3, 2, 4}
Output: 0
Approach: The given problem can be solved by generating the next permutation of the first N natural numbers using the function Next Permutation STL. The idea is to consider arr[] as the base permutation and perform the next_permutation() until arr[] is not equal to brr[]. After this step, the count of steps required to convert arr[] to brr[] is the resultant value of the absolute difference between their positions in lexicographical order.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the distance between // two permutations array arr[] and brr[] // in lexicographical order int permutationDiff(vector< int > arr, vector< int > brr) { // Check if both permutations are // already equal or not if (arr == brr) { return 0; } // Stores the distance between the // two permutations arr[] and brr[] int count = 0; while (arr != brr) { // Increment the count count++; // call next_permutation next_permutation(brr.begin(), brr.end()); } // Return the total count return count; } // Driver Code int main() { vector< int > arr = { 1, 3, 2 }; vector< int > brr = { 3, 1, 2 }; cout << permutationDiff(arr, brr); return 0; } |
Java
// Java program for the above approach import java.util.*; public class GFG { // Utility function to find next permutation public static void next_permutation( int nums[]) { int mark = - 1 ; for ( int i = nums.length - 1 ; i > 0 ; i--) { if (nums[i] > nums[i - 1 ]) { mark = i - 1 ; break ; } } if (mark == - 1 ) { reverse(nums, 0 , nums.length - 1 ); return ; } int idx = nums.length- 1 ; for ( int i = nums.length- 1 ; i >= mark+ 1 ; i--) { if (nums[i] > nums[mark]) { idx = i; break ; } } swap(nums, mark, idx); reverse(nums, mark + 1 , nums.length - 1 ); } // Utility function to swap two elements in array public static void swap( int nums[], int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } // Utility function to reverse the array in a range public static void reverse( int nums[], int i, int j) { while (i < j) { swap(nums, i, j); i++; j--; } } // Function to find the distance between // two permutations array arr[] and brr[] // in lexicographical order public static int permutationDiff( int arr[], int brr[]) { // Check if both permutations are // already equal or not if (Arrays.equals(arr, brr)) { return 0 ; } // Stores the distance between the // two permutations arr[] and brr[] int count = 0 , flag = 0 ; while (!Arrays.equals(arr, brr)) { // Increment the count count++; // call next_permutation next_permutation(brr); } // Return the total count return count; } // Driver Code public static void main(String args[]) { int []arr = { 1 , 3 , 2 }; int []brr = { 3 , 1 , 2 }; System.out.println(permutationDiff(arr, brr)); } } // This code is contributed by Samim Hossain Mondal |
Python3
# Python program for the above approach # Function for next permutation def next_permutation(arr): # find the length of the array n = len (arr) # start from the right most digit and find the first # digit that is smaller than the digit next to it. k = n - 2 while k > = 0 : if arr[k] < arr[k + 1 ]: break k - = 1 # reverse the list if the digit that is smaller than the # digit next to it is not found. if k < 0 : arr = arr[:: - 1 ] else : # find the first greatest element than arr[k] from the # end of the list for l in range (n - 1 , k, - 1 ): if arr[l] > arr[k]: break # swap the elements at arr[k] and arr[l arr[l], arr[k] = arr[k], arr[l] # reverse the list from k + 1 to the end to find the # most nearest greater number to the given input number arr[k + 1 :] = reversed (arr[k + 1 :]) return arr # Function to find the distance between # two permutations array arr[] and brr[] # in lexicographical order def permutationDiff(arr, brr): # Check if both permutations are # already equal or not if (arr = = brr): return 0 # Stores the distance between the # two permutations arr[] and brr[] count = 0 while (arr ! = brr): # Increment the count count = count + 1 # call next_permutation brr = next_permutation(brr) # Return the total count return count arr = [ 1 , 3 , 2 ] brr = [ 3 , 1 , 2 ] print (permutationDiff(arr, brr)) # This code is contributed by Potta Lokesh |
C#
// C# program for the above approach using System; using System.Linq; class GFG { // Utility function to find next permutation static void next_permutation( int []nums) { int mark = -1; for ( int i = nums.Length - 1; i > 0; i--) { if (nums[i] > nums[i - 1]) { mark = i - 1; break ; } } if (mark == -1) { reverse(nums, 0, nums.Length - 1); return ; } int idx = nums.Length-1; for ( int i = nums.Length-1; i >= mark+1; i--) { if (nums[i] > nums[mark]) { idx = i; break ; } } swap(nums, mark, idx); reverse(nums, mark + 1, nums.Length - 1); } // Utility function to swap two elements in array static void swap( int []nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } // Utility function to reverse the array in a range public static void reverse( int []nums, int i, int j) { while (i < j) { swap(nums, i, j); i++; j--; } } // Function to find the distance between // two permutations array arr[] and brr[] // in lexicographical order public static int permutationDiff( int []arr, int []brr) { // Check if both permutations are // already equal or not if (arr.SequenceEqual(brr)) { return 0; } // Stores the distance between the // two permutations arr[] and brr[] int count = 0, flag = 0; while (!arr.SequenceEqual(brr)) { // Increment the count count++; // call next_permutation next_permutation(brr); } // Return the total count return count; } // Driver Code public static void Main() { int []arr = { 1, 3, 2 }; int []brr = { 3, 1, 2 }; Console.Write(permutationDiff(arr, brr)); } } // This code is contributed by Samim Hossain Mondal |
Javascript
<script> // JavaScript Program to implement // the above approach // Utility function to find next permutation function next_permutation(nums) { let mark = -1; for (let i = nums.length - 1; i > 0; i--) { if (nums[i] > nums[i - 1]) { mark = i - 1; break ; } } if (mark == -1) { reverse(nums, 0, nums.length - 1); return ; } let idx = nums.length-1; for (let i = nums.length-1; i >= mark+1; i--) { if (nums[i] > nums[mark]) { idx = i; break ; } } swap(nums, mark, idx); reverse(nums, mark + 1, nums.length - 1); } // Utility function to swap two elements in array function swap(nums, i, j) { let t = nums[i]; nums[i] = nums[j]; nums[j] = t; } // Utility function to reverse the array in a range function reverse(nums, i, j) { while (i < j) { swap(nums, i, j); i++; j--; } } function arraysEqual(a, b) { if (a === b) return true ; if (a == null || b == null ) return false ; if (a.length !== b.length) return false ; // If you don't care about the order of the elements inside // the array, you should sort both arrays here. // Please note that calling sort on an array will modify that array. // you might want to clone your array first. for ( var i = 0; i < a.length; ++i) { if (a[i] !== b[i]) return false ; } return true ; } // Function to find the distance between // two permutations array arr[] and brr[] // in lexicographical order function permutationDiff(arr, brr) { // Check if both permutations are // already equal or not if (arraysEqual(arr, brr)) { return 0; } // Stores the distance between the // two permutations arr[] and brr[] let count = 0, flag = 0; while (!arraysEqual(arr, brr)) { // Increment the count count++; // call next_permutation next_permutation(brr); } // Return the total count return count; } // Driver Code let arr = [ 1, 3, 2 ]; let brr = [ 3, 1, 2 ]; document.write(permutationDiff(arr, brr)); // This code is contributed by code_hunt. </script> |
3
Time Complexity: O(N2)
Auxiliary Space: O(1)