How to obtain the index permutation after the sorting

algorithm, c++

Solution

Create an array of indexes, fill it with numbers 0..N-1, and sort it using a custom comparator. The comparator should compare items from the original array at indexes `lhs` and `rhs`. Sorting the array of indexes this way reorders them as a permutation:

vector<int> data = {5, 16, 4, 7};   
vector<int> index(data.size(), 0);
for (int i = 0 ; i != index.size() ; i++) {
    index[i] = i;
}
sort(index.begin(), index.end(),
    [&](const int& a, const int& b) {
        return (data[a] < data[b]);
    }
);
for (int i = 0 ; i != index.size() ; i++) {
    cout << index[i] << endl;
}

This prints `2, 0, 3, 1`

Here is a demo on ideone.

Note: you can use `index` to retrieve the `data` in sorted order:

for (int i = 0 ; i != index.size() ; i++) {
    cout << data[index[i]] << endl;
}

Problem

Given an array `arr = {5, 16, 4, 7}`, we can sort it through `sort(arr, arr+sizeof(arr)/sizeof(arr[0]))`. so now the array `arr = {4, 5, 7, 16}` and the permutation index for the sorted array is `{2, 0, 3, 1}`. In other words, the `arr[2]` in the original array is now the smallest element in the sorted array in position `0`. Is there an efficient way so that we can get the permutation index?

Original source