Absolute difference between given permutations of N natural numbers - Coding

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>

Output:

Time Complexity: O(N²)
Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Arrays

Related
PHP Program For Counting Inversions In An Array - Set 1 (Using Merge Sort)
Maximize subarray sum by inverting sign of elements of any subarray at most twice
Find the sum between given cells of a 3D Array
Maximize remainder difference between two pairs in given Array
Minimize swaps required to make all prime-indexed elements as prime

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	10