How to obtain the index permutation after the sorting

Question

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?

Answer 1

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

Answer 2

Why not put some satellite data? Instead of sorting the numbers, just sort pairs of numbers and their indices. Since the sorting is first done on the first element of the pair, this shouldn't disrupt a stable sorting algorithm.

For unstable algorithms, this will change it to a stable one.

But note that if you try sorting this way it generates the index while sorting, not after.

Also, since knowing the permutation index would lead to a O(n) sorting algorithm, so you cannot do it faster than O(nlogn).

Answer 3

Well in c++ we can use pair datatype to do this easily. Sample code below;

arr = {5, 16, 4, 7};
vector<pair<int,int> >V;
for(int i=0;i<4;i++){
    pair<int,int>P=make_pair(arr[i],i);
    V.push_back(P);
}

sort(V.begin(),V.end());

So V[i].first is the ith value and V[i].second is the ith index. So to print the index in the sorted array.

for(int i=0;i<4;i++)cout<<V[i].second<<endl;

Note that while sorting an array (or vector) of pair items, array is first sorted based on the first values. If two pair have same first value then they are sorted based on their second value.

Answer 4

For those who are looking into a C++17 like interface of @Sergey Kalinichenko's solution, follwoing snippet might be usefull.

template <class ExecutionPolicy, typename RandomIt>
auto sort_permutation(ExecutionPolicy&& policy, RandomIt cbegin, RandomIt cend) {
    auto len = std::distance(cbegin, cend);
    std::vector<size_t> perm(len);
    std::iota(perm.begin(), perm.end(), 0U);
    std::sort(policy, perm.begin(), perm.end(),
          [&](const size_t& a, const size_t& b)
    {
        return *(cbegin+a) < *(cbegin+b);
    });
    return perm;
}

And you can use this like:

std::vector<int> a {2, 3, 1, 2, 3, 6, 8, 5};
auto r = sort_permutation(std::execution::par, a.cbegin()+1, a.cend()-1);

Remove execution policy arguement if you don't want to link with tbb.

Answer 5

Multimap can come to the rescue

template<typename TIn, typename TOut>
sortindex(const TIn &first, const TIn &last, TOut &out) {
    using ValT = typename std::decay<decltype(*first)>::type;
    std::multimap<ValT, size_t> sindex;

    for(auto p=first; p != last; p++)
        sindex.emplace(*p, std::distance(first, p));

    for(auto &&p: sindex)
        *out++ = p.second;
}

which can be used like this:

std::vector<size_t> a{32, 22, 45, 9, 12, 15};
std::vector<size_t> indexes;

sortindex(a.begin(), a.end(), std::back_inserter(indexes));

If a coupling between the sorted values and the index would be need, then the multimap can be directly returned, rather than writing the indexes to the output iterator.

template<typename TIn>
auto
sortindex(const TIn &first, const TIn &last)
    --> std::multimap<typename std::decay<decltype(*first)>::type, size_t> 
{  // return value can be commented out in C++14
    using ValT = typename std::decay<decltype(*first)>::type;
    std::multimap<ValT, size_t> sindex;

    for(auto p=first; p != last; p++)
        sindex.emplace(*p, std::distance(first, p));

    return sindex;
}

Answer 6

Yes, there is one with O(NlogN) time.Since the sorting takes O(NlogN) time anyway, this will not affect overall time complexity.
Time Complexity: O(NlogN)
Space Complexity:O(N)
where N=number of elements in input array

Algorithm:

1. Make copy of input array(P) call it Q.
2. Sort input array P.
3. For each number in Q, do binary search to find index of that element in P.

Answer 7

I recently had to solve a similar problem in PHP. You create a local compare function to be used by PHP's UASORT sorting algorithm. Call array_keys() on the sorted array, and that should spit out your permutation array.

// test array

$tArray = array('2', '10', '1', '23', '8', '3');

// sort array; to maintain index association, use uasort; else use usort, etc

uasort($tArray, 'compareSize');

// the resulting keys are your permutation indexes (if uasort used in previous step)

$Keys = array_keys($tArray);

// local compare function

function compareSize($a, $b) {

if($a == $b) { return 0; } else { return ($a < $b) ? -1 : 1; }

}

======================================================================= Results:

sorted =: Array ( [2] => 1 [0] => 2 [5] => 3 [4] => 8 [1] => 10 [3] => 23 )

keys =: Array ( [0] => 2 [1] => 0 [2] => 5 [3] => 4 [4] => 1 [5] => 3 )

Answer 8

I think we can solve this problem without using vector. I'm newbie, to be honest, i don't understand what you wrote above, and all of you used vector which i will study later :))) ( i'm lazy) Here's my way :

// First, copy array a[] to array b[]

   void copyarray(double b[],double a[],int n){
     for(int i=0;i<n;i++)b[i]=a[i];
    }

// Second, sort array a[] ( decrease )

/*Third, " sorter " array a[], that means: in array a[],if there exists same values, they will merge into one ! i will set array o[] is "the sorted array a[] " */

 void sorter(double o[],double a[],int n,int &dem){   
     int i;
     o[0]=a[0];
     for(i=1;i<n;i++){
        if(a[i]!=a[i-1]){
          dem++; o[dem]=a[i];
         }
      }
      dem++;
 }

/* 4th, our main goal: get the index: i will put the index into array c[] */

void index_sort(double o[],double b[], double c[], int dem, int n){
    int i,j,chiso=0;
    for(j=0;j<dem;j++){
       for(i=0;i<n;i++){
          if(b[i]==o[j]){
             c[chiso]=i;
             chiso++;
           }
        }
     }
 }

  // DONE!
 int main(){
        int n,dem=0;
         double a[100],b[100],c[100],o[100];
         cin>>n;
         input(a,n);
         copyarray(b,a,n);
         copyarray(c,a,n);
         sort(a,n);
         sorter(o,a,n,dem); 
         index_sort(o,b,c,dem,n); 
         for(int i=0;i<n;i++) cout<<c[i]<<" ";
   }