Generate original permutation from given array of inversions

0 0 11 minutes read

Given an array arr[] of size N, where arr[i] denotes the number of elements on the left that are greater than the i^th element in the original permutation. The task is to find the original permutation of [1, N] for which given inversion array arr[] holds valid.

Examples:

Input: arr[] = {0, 1, 1, 0, 3}
Output: 4 1 3 5 2
Explanation:
The original permutation is ans[] = {4, 1, 3, 5, 2}
ans[0] = 4.
ans[1] = 1. Since {4} exists on its left, which exceeds 1, arr[1] = 1 holds valid.
ans[2] = 3. Since {4} exists on its left, which exceeds 3, arr[2] = 1 holds valid.
ans[3] = 5. Since no elements on its left exceeds 5, arr[3] = 0 holds valid.
ans[4] = 2. Since {4, 3, 5} exists on its left, which exceeds 2, arr[4] = 3 holds valid.

Input: arr[] = {0, 1, 2}
Output: 3 2 1

Naive Approach: The simplest approach is to generate all the permutations of N number and for each permutation, check if its elements satisfy the inversions given by the array arr[]. If such permutation is found, print it.

Time Complexity: O(N!)
Auxiliary Space: O(N)

Efficient Approach: To optimize the above approach, the idea is to use a Segment Tree. Follow the below steps to solve the problem:

Build a segment tree of size N and initialize all leaf nodes with value 1.
Traverse the given array from right to left. For example, if the current index is N – 1, i.e, none of the elements are visited. So, the arr[i] is the number of elements that should be greater than the element which has to be at this position. So, the answer for this element is the (N – arr[N – 1])^th element in the segment tree corresponds to that element. After that, mark that element as 0 to avoid its counting again.
Similarly, find (i + 1 – arr[i])^th element in the segment tree, for each i from (N – 1) to 0.
After finding the answer for arr[i], let it be temp, store it in some array ans[], and update the node having index temp with 0.
Finally, print the answer array ans[] in reversed order as the original permutation.

Below is the implementation of the above approach:

C++

// C++ program for the above approach 
  
#include <bits/stdc++.h> 
using namespace std; 
const int MAXX = 100; 
  
// Declaring segment tree 
int st[4 * MAXX]; 
  
// Function to initialize segment tree 
// with leaves filled with ones 
void build(int x, int lx, int rx) 
{ 
    // Base Case 
    if (rx - lx == 1) { 
        st[x] = 1; 
        return; 
    } 
  
    // Split into two halves 
    int m = (lx + rx) / 2; 
  
    // Build the left subtree 
    build(x * 2 + 1, lx, m); 
  
    // Build the right subtree 
    build(x * 2 + 2, m, rx); 
  
    // Combining both left and right 
    // subtree to parent node 
    st[x] = st[x * 2 + 1] 
            + st[x * 2 + 2]; 
  
    return; 
} 
  
// Function to make index x to 0 
// and then update segment tree 
void update(int i, int x, 
            int lx, int rx) 
{ 
    // Base Case 
    if (rx - lx == 1) { 
        st[x] = 0; 
        return; 
    } 
  
    // Split into two halves 
    int m = (lx + rx) / 2; 
  
    // Update Query 
    if (i < m) 
        update(i, x * 2 + 1, lx, m); 
    else
        update(i, x * 2 + 2, m, rx); 
  
    // Combining both left and right 
    // subtree to parent node 
    st[x] = st[x * 2 + 1] 
            + st[x * 2 + 2]; 
  
    return; 
} 
  
// Function to find the Kth element 
int getans(int x, int lx, int rx, 
           int k, int n) 
{ 
    // Base Condition 
    if (rx - lx == 1) { 
        if (st[x] == k) 
            return lx; 
        return n; 
    } 
  
    // Split into two halves 
    int m = (lx + rx) / 2; 
  
    // Check if kth one is in left subtree 
    // or right subtree of current node 
    if (st[x * 2 + 1] >= k) 
        return getans(x * 2 + 1, 
                      lx, m, k, n); 
    else
        return getans(x * 2 + 2, m, 
                      rx, k - st[x * 2 + 1], 
                      n); 
} 
  
// Function to generate the original 
// permutation 
void getPermutation(int inv[], int n) 
{ 
    // Build segment tree 
    build(0, 0, n); 
  
    // Stores the original permutation 
    vector<int> ans; 
  
    for (int i = n - 1; i >= 0; i--) { 
  
        // Find kth one 
        int temp = getans(0, 0, n, 
                          st[0] - inv[i], n); 
  
        // Answer for arr[i] 
        ans.push_back(temp + 1); 
  
        // Setting found value back to 0 
        update(max(0, temp), 0, 0, n); 
    } 
  
    // Print the permutation 
    for (int i = n - 1; i >= 0; i--) 
        cout << ans[i] << " "; 
  
    return; 
} 
  
// Driver Code 
int main() 
{ 
    // Given array 
    int inv[] = { 0, 1, 1, 0, 3 }; 
  
    // Length of the given array 
    int N = sizeof(inv) / sizeof(inv[0]); 
  
    // Function Call 
    getPermutation(inv, N); 
  
    return 0; 
} 

Java

// Java program for the above approach 
import java.util.*; 
  
class GFG{ 
   
static int MAXX = 100; 
  
// Declaring segment tree 
static int []st = new int[4 * MAXX]; 
  
// Function to initialize segment tree 
// with leaves filled with ones 
static void build(int x, int lx, int rx) 
{ 
      
    // Base Case 
    if (rx - lx == 1)  
    { 
        st[x] = 1; 
        return; 
    } 
  
    // Split into two halves 
    int m = (lx + rx) / 2; 
  
    // Build the left subtree 
    build(x * 2 + 1, lx, m); 
  
    // Build the right subtree 
    build(x * 2 + 2, m, rx); 
  
    // Combining both left and right 
    // subtree to parent node 
    st[x] = st[x * 2 + 1] + st[x * 2 + 2]; 
  
    return; 
} 
  
// Function to make index x to 0 
// and then update segment tree 
static void update(int i, int x, 
                   int lx, int rx) 
{ 
      
    // Base Case 
    if (rx - lx == 1) 
    { 
        st[x] = 0; 
        return; 
    } 
  
    // Split into two halves 
    int m = (lx + rx) / 2; 
  
    // Update Query 
    if (i < m) 
        update(i, x * 2 + 1, lx, m); 
    else
        update(i, x * 2 + 2, m, rx); 
  
    // Combining both left and right 
    // subtree to parent node 
    st[x] = st[x * 2 + 1] + st[x * 2 + 2]; 
  
    return; 
} 
  
// Function to find the Kth element 
static int getans(int x, int lx, int rx, 
                  int k, int n) 
{ 
      
    // Base Condition 
    if (rx - lx == 1) 
    { 
        if (st[x] == k) 
            return lx; 
              
        return n; 
    } 
  
    // Split into two halves 
    int m = (lx + rx) / 2; 
  
    // Check if kth one is in left subtree 
    // or right subtree of current node 
    if (st[x * 2 + 1] >= k) 
        return getans(x * 2 + 1, 
                      lx, m, k, n); 
    else
        return getans(x * 2 + 2, m, rx,  
               k - st[x * 2 + 1], n); 
} 
  
// Function to generate the original 
// permutation 
static void getPermutation(int inv[], int n) 
{ 
      
    // Build segment tree 
    build(0, 0, n); 
  
    // Stores the original permutation 
    Vector<Integer> ans = new Vector<Integer>(); 
  
    for(int i = n - 1; i >= 0; i--) 
    { 
          
        // Find kth one 
        int temp = getans(0, 0, n, 
                          st[0] - inv[i], n); 
  
        // Answer for arr[i] 
        ans.add(temp + 1); 
  
        // Setting found value back to 0 
        update(Math.max(0, temp), 0, 0, n); 
    } 
  
    // Print the permutation 
    for(int i = n - 1; i >= 0; i--) 
        System.out.print(ans.get(i) + " "); 
  
    return; 
} 
  
// Driver Code 
public static void main(String args[]) 
{ 
      
    // Given array 
    int inv[] = { 0, 1, 1, 0, 3 }; 
  
    // Length of the given array 
    int N = inv.length; 
  
    // Function Call 
    getPermutation(inv, N); 
} 
} 
  
// This code is contributed by SURENDRA_GANGWAR

Python3

# Python3 program for the above approach 
MAXX = 100
  
# Declaring segment tree 
st = [0] * (4 * MAXX) 
  
# Function to initialize segment tree 
# with leaves filled with ones 
def build(x, lx, rx): 
      
    # Base Case 
    if (rx - lx == 1): 
        st[x] = 1
        return
  
    # Split into two halves 
    m = (lx + rx) // 2
  
    # Build the left subtree 
    build(x * 2 + 1, lx, m) 
  
    # Build the right subtree 
    build(x * 2 + 2, m, rx) 
  
    # Combining both left and right 
    # subtree to parent node 
    st[x] = st[x * 2 + 1] + st[x * 2 + 2] 
  
    return
  
# Function to make index x to 0 
# and then update segment tree 
def update(i, x, lx, rx): 
      
    # Base Case 
    if (rx - lx == 1): 
        st[x] = 0
        return
  
    # Split into two halves 
    m = (lx + rx) // 2
  
    # Update Query 
    if (i < m): 
        update(i, x * 2 + 1, lx, m) 
    else: 
        update(i, x * 2 + 2, m, rx) 
  
    # Combining both left and right 
    # subtree to parent node 
    st[x] = st[x * 2 + 1] + st[x * 2 + 2] 
  
    return
  
# Function to find the Kth element 
def getans(x, lx, rx, k, n): 
      
    # Base Condition 
    if (rx - lx == 1): 
        if (st[x] == k): 
            return lx 
              
        return n 
  
    # Split into two halves 
    m = (lx + rx) // 2
  
    # Check if kth one is in left subtree 
    # or right subtree of current node 
    if (st[x * 2 + 1] >= k): 
        return getans(x * 2 + 1, lx, m, k, n) 
    else: 
        return getans(x * 2 + 2, m, rx,  
               k - st[x * 2 + 1], n) 
  
# Function to generate the original 
# permutation 
def getPermutation(inv, n): 
      
    # Build segment tree 
    build(0, 0, n) 
  
    # Stores the original permutation 
    ans = [] 
  
    for i in range(n - 1, -1, -1): 
          
        # Find kth one 
        temp = getans(0, 0, n, st[0] - inv[i], n) 
  
        # Answer for arr[i] 
        ans.append(temp + 1) 
  
        # Setting found value back to 0 
        update(max(0, temp), 0, 0, n) 
  
    # Print the permutation 
    for i in range(n - 1, -1, -1): 
        print(ans[i], end = " ") 
  
    return
  
# Driver Code 
if __name__ == '__main__': 
      
    # Given array 
    inv = [ 0, 1, 1, 0, 3 ] 
  
    # Length of the given array 
    N = len(inv) 
  
    # Function Call 
    getPermutation(inv, N) 
  
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach 
using System; 
using System.Collections.Generic; 
  
class GFG{ 
   
static int MAXX = 100; 
  
// Declaring segment tree 
static int []st = new int[4 * MAXX]; 
  
// Function to initialize segment tree 
// with leaves filled with ones 
static void build(int x, int lx, int rx) 
{ 
      
    // Base Case 
    if (rx - lx == 1)  
    { 
        st[x] = 1; 
        return; 
    } 
  
    // Split into two halves 
    int m = (lx + rx) / 2; 
  
    // Build the left subtree 
    build(x * 2 + 1, lx, m); 
  
    // Build the right subtree 
    build(x * 2 + 2, m, rx); 
  
    // Combining both left and right 
    // subtree to parent node 
    st[x] = st[x * 2 + 1] + st[x * 2 + 2]; 
  
    return; 
} 
  
// Function to make index x to 0 
// and then update segment tree 
static void update(int i, int x, 
                   int lx, int rx) 
{ 
      
    // Base Case 
    if (rx - lx == 1) 
    { 
        st[x] = 0; 
        return; 
    } 
  
    // Split into two halves 
    int m = (lx + rx) / 2; 
  
    // Update Query 
    if (i < m) 
        update(i, x * 2 + 1, lx, m); 
    else
        update(i, x * 2 + 2, m, rx); 
  
    // Combining both left and right 
    // subtree to parent node 
    st[x] = st[x * 2 + 1] + st[x * 2 + 2]; 
  
    return; 
} 
  
// Function to find the Kth element 
static int getans(int x, int lx, int rx, 
                  int k, int n) 
{ 
      
    // Base Condition 
    if (rx - lx == 1) 
    { 
        if (st[x] == k) 
            return lx; 
              
        return n; 
    } 
  
    // Split into two halves 
    int m = (lx + rx) / 2; 
  
    // Check if kth one is in left subtree 
    // or right subtree of current node 
    if (st[x * 2 + 1] >= k) 
        return getans(x * 2 + 1, 
                      lx, m, k, n); 
    else
        return getans(x * 2 + 2, m, rx,  
               k - st[x * 2 + 1], n); 
} 
  
// Function to generate the original 
// permutation 
static void getPermutation(int []inv, int n) 
{ 
      
    // Build segment tree 
    build(0, 0, n); 
  
    // Stores the original permutation 
    List<int> ans = new List<int>(); 
  
    for(int i = n - 1; i >= 0; i--) 
    { 
          
        // Find kth one 
        int temp = getans(0, 0, n, 
                          st[0] - inv[i], n); 
  
        // Answer for arr[i] 
        ans.Add(temp + 1); 
  
        // Setting found value back to 0 
        update(Math.Max(0, temp), 0, 0, n); 
    } 
  
    // Print the permutation 
    for(int i = n - 1; i >= 0; i--) 
        Console.Write(ans[i] + " "); 
  
    return; 
} 
  
// Driver Code 
public static void Main(String []args) 
{ 
      
    // Given array 
    int []inv = { 0, 1, 1, 0, 3 }; 
  
    // Length of the given array 
    int N = inv.Length; 
  
    // Function Call 
    getPermutation(inv, N); 
} 
} 
  
// This code is contributed by Amit Katiyar

Javascript

<script> 
  
// Javascript program for the above approach 
let MAXX = 100; 
  
// Declaring segment tree 
let st = new Array(4 * MAXX); 
  
// Function to initialize segment tree 
// with leaves filled with ones 
function build(x, lx, rx) 
{ 
      
    // Base Case 
    if (rx - lx == 1) 
    { 
        st[x] = 1; 
        return; 
    } 
  
    // Split into two halves 
    let m = parseInt((lx + rx) / 2, 10); 
  
    // Build the left subtree 
    build(x * 2 + 1, lx, m); 
  
    // Build the right subtree 
    build(x * 2 + 2, m, rx); 
  
    // Combining both left and right 
    // subtree to parent node 
    st[x] = st[x * 2 + 1] + st[x * 2 + 2]; 
  
    return; 
} 
  
// Function to make index x to 0 
// and then update segment tree 
function update(i, x, lx, rx) 
{ 
      
    // Base Case 
    if (rx - lx == 1) 
    { 
        st[x] = 0; 
        return; 
    } 
  
    // Split into two halves 
    let m = parseInt((lx + rx) / 2, 10); 
  
    // Update Query 
    if (i < m) 
        update(i, x * 2 + 1, lx, m); 
    else
        update(i, x * 2 + 2, m, rx); 
  
    // Combining both left and right 
    // subtree to parent node 
    st[x] = st[x * 2 + 1] + st[x * 2 + 2]; 
  
    return; 
} 
  
// Function to find the Kth element 
function getans(x, lx, rx, k, n) 
{ 
      
    // Base Condition 
    if (rx - lx == 1) 
    { 
        if (st[x] == k) 
            return lx; 
  
        return n; 
    } 
  
    // Split into two halves 
    let m = parseInt((lx + rx) / 2, 10); 
  
    // Check if kth one is in left subtree 
    // or right subtree of current node 
    if (st[x * 2 + 1] >= k) 
        return getans(x * 2 + 1, lx, m, k, n); 
    else
        return getans(x * 2 + 2, m, rx, 
               k - st[x * 2 + 1], n); 
} 
  
// Function to generate the original 
// permutation 
function getPermutation(inv, n) 
{ 
      
    // Build segment tree 
    build(0, 0, n); 
  
    // Stores the original permutation 
    let ans = []; 
  
    for(let i = n - 1; i >= 0; i--) 
    { 
  
        // Find kth one 
        let temp = getans(0, 0, n,  
                          st[0] - inv[i], n); 
  
        // Answer for arr[i] 
        ans.push(temp + 1); 
  
        // Setting found value back to 0 
        update(Math.max(0, temp), 0, 0, n); 
    } 
  
    // Print the permutation 
    for(let i = n - 1; i >= 0; i--) 
        document.write(ans[i] + " "); 
  
    return; 
} 
  
// Driver code 
  
// Given array 
let inv = [ 0, 1, 1, 0, 3 ]; 
  
// Length of the given array 
let N = inv.length; 
  
// Function Call 
getPermutation(inv, N); 
  
// This code is contributed by suresh07 
  
</script>