Recovering permutation from its image sequence

Question

Recently while practicing I came across this problem , here is an excerpt from it,

A permutation of the numbers 1, ..., N is a rearrangment of these numbers. For example

2 4 5 1 7 6 3 8

is a permutation of 1,2, ..., 8. Of course,

1 2 3 4 5 6 7 8

is also a permutation of 1, 2, ..., 8.

Associated with each permutation of N is a special sequence of positive integers of length N called its inversion sequence. The ith element of this sequence is the number of numbers j that are strictly less than i and appear to the right of i in this permutation. For the permutation

2 4 5 1 7 6 3 8

the inversion sequence is

0 1 0 2 2 1 2 0

The 2nd element is 1 because 1 is strictly less than 2 and it appears to the right of 2 in this permutation. Similarly, the 5th element is 2 since 1 and 3 are strictly less than 5 but appear to the right of 5 in this permutation and so on.

As another example, the inversion sequence of the permutation

8 7 6 5 4 3 2 1

is

0 1 2 3 4 5 6 7

In this problem, you will be given the inversion sequence of some permutation. Your task is to reconstruct the permutation from this sequence.

I cooked up two solutions but both fail to deliver the result in time for the last three testcases,

here is the code,

Solution 1

#include <iostream>
#include <vector>

int main(){
    int n;
    std::cin >> n;
    std::vector<int>nums(n);
    int key;

    for( int k = 0; k < n; k++ ){
        std::cin >> key;
        int value = k+1;
        int i = 0;
        for(i = 0; i < key; i++){
            int j = k - i;
            nums[j] = nums[j - 1];
        }
        nums[k - i] = value;
    }

    for(int i = 0;i < n;i ++){
        std::cout << nums[i] << " ";
    }

    std::cout << std::endl;

return 0;
}

Simple and easy to understand , get the key and shift the integers to right to accommodate the new integer.

Solution 2

#include <iostream>
#include <vector>

int main(){
    int n;
    std::cin >> n;
    std::vector<int>nums(n,0);
    std::vector<int>inverse(n);

    for(int k = 0; k < n; k++ ){
        std::cin >> inverse[k];
    }

    for(int i=n-1;i>=0;i--){
        int onRight = inverse[i];
        int pos = i;
        for(int j=n-1;j>=0;j--){
            if(nums[j] == 0){
                pos = j;
                break;
            }
        }
        while(onRight){
            if(nums[pos] == 0){
                onRight--;
            }
            pos--;
        }
        if(nums[pos] != 0){
            for(int j=pos;j>=0;j--){
                if(nums[j] == 0){
                    pos = j;
                    break;
                }
            }
        }
        nums[pos] = i+1;
    }

    for(int i = 0;i < n;i ++){
        std::cout << nums[i] << " ";
    }

    std::cout << std::endl;

return 0;
}

This one is a little bit complicated in code but it follows a simple concept that push the integer from back , if the block is empty then decrement the number small of integers right of it , if not skip it to the next block and fill the array.

Both the solutions take almost same time , is there any better approach for it available?

Here are the testcases.

Answer 1

Exactly like the bookshelf problem

This problem is exactly the same problem as the bookshelf problem that I previously reviewed. If you work from the end of the inversion sequence, each number is like a book that you remove from the right end of the shelf. For example, if the inversion sequence were:

Inversion sequence = 0 1 0 2 2 1 2 0

Then starting with the last entry 0, this means that book #8 is the rightmost book on the shelf. So we can place it there:

Original sequence = ? ? ? ? ? ? ? 8

Next in the inversion sequence is 2. This means that we book #7 is the 3rd remaining book from the right of the shelf (3rd because 0, 1, 2).

Original sequence = ? ? ? ? 7 ? ? 8

Next is 1, so book #6 is the 2nd from the right:

Original sequence = ? ? ? ? 7 6 ? 8

And you keep going until you fill in the full sequence: 2 4 5 1 7 6 3 8.

\$O(\log ^2(n))\$ solution

Just like with the bookshelf problem, this can be done in \$O(\log ^2*(n))\$ time using a binary indexed tree and a binary search of that tree. I took the exact code I wrote for the bookshelf problem and adapted it to this one:

#include <iostream>
#include <vector>

static inline int BIT_GET(const std::vector<int> &BIT, int i)
{
    int ret = 0;
    i++;
    while (i > 0) {
        ret += BIT[i-1];
        i -= (i & -i);
    }
    return ret;
}

static inline void BIT_ADD(std::vector<int> &BIT, int i, int val)
{
    int max = BIT.size();
    i++;
    while (i < max)
    {
        BIT[i-1] += val;
        i += (i & -i);
    }
}

int bsearch(const std::vector<int> &BIT, int index)
{
    int low  = 0;
    int high = BIT.size()-1;

    while (low <= high) {
        int mid    = low + ((high-low)>>1);
        int midVal = mid + BIT_GET(BIT, mid);

        if (midVal >= index)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}

int main(void)
{
    int n;
    std::cin >> n;
    std::vector<int>inv(n);
    std::vector<int>original(n);
    std::vector<int>BIT(n);

    for (int i=0;i<n;i++)
        std::cin >> inv[i];

    for (int i=n-1;i>=0;i--) {
        int index = bsearch(BIT, inv[i]);
        original[n - 1 - index] = i + 1;
        BIT_ADD(BIT, index, -1);
    }

    for (int i=0;i<n;i++)
        std::cout << original[i] << " ";

    return 0;
}

As you can see, only main() changed. The only tricky thing is that the BIT can only track books being removed and the books on the right shifting left by one. The problem calls for removing books from the right and the books on the left shifting to the right by one. So the BIT actually tracks the bookshelf in reverse order. That is why we when we retrieve index from the BIT, we reverse it to n - 1 - index in order to determine where to place the current value in the original array.