# Recovering permutation from its image sequence

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.

• This is exactly the same problem as the bookshelf problem that you asked about earlier. Compare your second solution to the solution you had for the bookshelf problem. If you work from the back of the inversion sequence to the front, each number of the inversion sequence is like a book you remove from the shelf, except from the right end. For example, 3 = remove third remaining book from the right. You can use a Binary Indexed Tree to solve this. – JS1 Oct 24 '16 at 17:42
• Yep , thats why I was asking for the explanation :P – hellozee Oct 24 '16 at 18:02
• And another note , to practice the problems in the Iarcs server I httracked their page and but need judge to check the results with time taken , can you help me a bit? – hellozee Oct 24 '16 at 18:05

### 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;
}

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.

• aka John Smythe, do you have any active account on any social networking site or instant messaging app? Cause you dont seem to reply to chats and you are a wonderful person to learn from, :P – hellozee Oct 25 '16 at 17:37
• @KuntalMajumder No I'm not on any social media anywhere. Did you try to open a chat with me on this site? I didn't see it. – JS1 Oct 25 '16 at 19:12
• sent an invitation and not in any social media? thats something interesting.. – hellozee Oct 26 '16 at 8:25
• forgot me? I have some questions pending – hellozee Oct 30 '16 at 11:43