Reorder vector according to a vector of indices - update

Question

This is an update to a previous question about reordering in place There was some confusion about the vector of indices. Calling the vector to be reordered vA, and the vector of indices vI, then vA should be reordered in this order, vA[vI[0]], vA[vI[1]], vA[vI[2], ... . An example usage would be to initialize vI as a set of vA.size() indices, 0 to vA.size()-1, then sort vI according to vA (compare using vA[vI[...]]). Then the reorder function could be used to sort vA according to vI.

Consider the initial vA as a permutation of a sorted vA. After sorting vI according to vA, then reordering vA according to vI "unpermutes" vA back to the sorted permutation. With the example functions shown below, reordering vA also reorders vI back to it's initialized state (0 to vA.size()-1).

I think you are trying to do 'gather' function. If you want it's already implemented in the boost library (boost/algorithm/gather.hpp) http://www.boost.org/doc/libs/1_41_0/doc/html/boost/mpi/gather.html — MoonBun, Mar 06 '14 at 10:43
The goal here is to reorder in place. Making an ordered copy is easy: for(i = 0; i < vA.size(); i++) vCopy[i] = vA[vI[i]]; — rcgldr, Mar 06 '14 at 10:55
I updated this question to include a link to the previous question. — rcgldr, Mar 06 '14 at 11:12

rcgldr · Answer 1 · 2014-03-06T12:07:42.223

The example below shows a non-working version of reorder called reorderfail() followed by a working version called reorder(). Both functions return vI to it's original state of 0 to vA.size()-1, but reorderfail() fails to reorder vA properly because it's missing a level of indirection needed to "unpermute" vA.

#include <algorithm>
#include <vector>

using namespace std;

template <class T>
void reorderfail(vector<T>& vA, vector<size_t>& vI)  
{   
size_t i, j;
    for(i = 0; i < vA.size(); i++ ){ 
        while(i != (j = vI[i])){
            swap(vA[i], vA[j]);
            swap(vI[i], vI[j]);
        }
    }
}

template <class T>
void reorder(vector<T>& vA, vector<size_t>& vI)  
{
size_t i, j, k;
    for(i = 0; i < vA.size(); i++){ 
        while(i != (j = vI[i])){
            k = vI[j];
            swap(vA[j], vA[k]);
            swap(vI[i], vI[j]);
        }
    }
}

int main( )
{
char A[]   = { 'b', 'c', 'a' };
size_t I[] = {  2 ,  0 ,  1  };  // order should be A[2] A[0] A[1]
size_t size = sizeof(A) / sizeof(*A);

    vector<char>   vA(size);
    vector<size_t> vI(size);

    vA.assign(A, A + size);
    vI.assign(I, I + size);
    reorderfail(vA, vI);    // returns vA = {'c', 'a', 'b'};

    vA.assign(A, A + size);
    vI.assign(I, I + size);
    reorder(vA, vI);        // returns vA = {'a', 'b', 'c'};

    return(0);
}

rcgldr · Accepted Answer · 2014-03-06T14:52:08.567

A version of a working reorder that moves data instead of swapping it. This example may be easier to explain. Every permutation is a set of "cycles". reorder works by undoing the cycles. Assume that there are 8 elements, and vI contains the desired order. I placed the index i above vI:

i :     {  0 ,  1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7  }

vI[i] = {  5 ,  7 ,  0 ,  3 ,  6 ,  2 ,  4 ,  1  }

Cycle 1: vI[0] == 5, vI[5] == 2, vI[2] == 0.

Cycle 2: vi[1] == 7, vi[7] == 1.

Cycle 3: vI[3] == 3.

Cycle 4: vI[4] == 6, vi[6] == 4.

undo cycle 1, t = vA[0], vA[0] = vA[5], vA[5] = vA[2], vA[2] = t.

undo cycle 2, t = vA[1], vA[1] = vA[7], vA[7] = t.

undo cycle 3, no correction needed

undo cycle 4, t = vA[4], vA[4] = vA[6], vA[6] = t.

Each time a value is stored in vA[k], vI[k] is set to k to indicate vA[k] is ordered.

template <class T>
void reorder(vector<T>& vA, vector<size_t>& vI)  
{
size_t i, j, k;
T t;
    for(i = 0; i < vA.size(); i++){
        if(i != vI[i]){
            t = vA[i];
            k = i;
            while(i != (j = vI[k])){
            // every move places a value in it's final location
                vA[k] = vA[j];
                vI[k] = k;
                k = j;
            }
            vA[k] = t;
            vI[k] = k;
        }
    }
}

Reorder vector according to a vector of indices - update

2 Answers2