Reorder Vector Using a Vector of Indices

Reorder vector using a vector of indices

This algorithm is based on chmike's, but the vector of reorder indices is const. This function agrees with his for all 11! permutations of [0..10]. The complexity is O(N^2), taking N as the size of the input, or more precisely, the size of the largest orbit.

See below for an optimized O(N) solution which modifies the input.

template< class T >
void reorder(vector<T> &v, vector<size_t> const &order )  {   
    for ( int s = 1, d; s < order.size(); ++ s ) {
        for ( d = order[s]; d < s; d = order[d] ) ;
        if ( d == s ) while ( d = order[d], d != s ) swap( v[s], v[d] );
    }
}

Here's an STL style version which I put a bit more effort into. It's about 47% faster (that is, almost twice as fast over [0..10]!) because it does all the swaps as early as possible and then returns. The reorder vector consists of a number of orbits, and each orbit is reordered upon reaching its first member. It's faster when the last few elements do not contain an orbit.

template< typename order_iterator, typename value_iterator >
void reorder( order_iterator order_begin, order_iterator order_end, value_iterator v )  {   
    typedef typename std::iterator_traits< value_iterator >::value_type value_t;
    typedef typename std::iterator_traits< order_iterator >::value_type index_t;
    typedef typename std::iterator_traits< order_iterator >::difference_type diff_t;
    
    diff_t remaining = order_end - 1 - order_begin;
    for ( index_t s = index_t(), d; remaining > 0; ++ s ) {
        for ( d = order_begin[s]; d > s; d = order_begin[d] ) ;
        if ( d == s ) {
            -- remaining;
            value_t temp = v[s];
            while ( d = order_begin[d], d != s ) {
                swap( temp, v[d] );
                -- remaining;
            }
            v[s] = temp;
        }
    }
}

---

And finally, just to answer the question once and for all, a variant which does destroy the reorder vector (filling it with -1's). For permutations of [0..10], It's about 16% faster than the preceding version. Because overwriting the input enables dynamic programming, it is O(N), asymptotically faster for some cases with longer sequences.

template< typename order_iterator, typename value_iterator >
void reorder_destructive( order_iterator order_begin, order_iterator order_end, value_iterator v )  {
    typedef typename std::iterator_traits< value_iterator >::value_type value_t;
    typedef typename std::iterator_traits< order_iterator >::value_type index_t;
    typedef typename std::iterator_traits< order_iterator >::difference_type diff_t;
    
    diff_t remaining = order_end - 1 - order_begin;
    for ( index_t s = index_t(); remaining > 0; ++ s ) {
        index_t d = order_begin[s];
        if ( d == (diff_t) -1 ) continue;
        -- remaining;
        value_t temp = v[s];
        for ( index_t d2; d != s; d = d2 ) {
            swap( temp, v[d] );
            swap( order_begin[d], d2 = (diff_t) -1 );
            -- remaining;
        }
        v[s] = temp;
    }
}

Reorder vector according to a vector of indices - update

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

How to sort R vector according to a vector in indices

hi try this with your later vectors v and ind

v[order(ind)]

C++ Sort vector by index

You don't want std::sort, you want std::rotate.

    std::vector<int> v = {20, 21, 22, 23, 24, 25,
                          26, 27, 28, 29, 30, 31};
    auto b = std::next(std::begin(v), 3); // skip first three elements
    auto const re = std::end(v);  // keep track of the actual end
    auto e = std::next(b, 6);  // the end of our current block
    while(e < re) {
        auto mid = std::next(b, 3);
        std::rotate(b, mid, e);
        b = e;
        std::advance(e, 6);
    }
    // print the results
    std::copy(std::begin(v), std::end(v), std::ostream_iterator<int>(std::cout, " "));

This code assumes you always do two groups of 3 for each rotation, but you could obviously work with whichever arbitrary ranges you wanted.

The output looks like what you'd want:

20 21 22 26 27 28 23 24 25 29 30 31

Update: @Blastfurnace pointed out that std::swap_ranges would work as well. The rotate call can be replaced with the following line:

std::swap_ranges(b, mid, mid);  // passing mid twice on purpose

How to do in-place sorting a list according to a given index in C++

What you are looking for is called "applying a permutation" and is considered a solved problem (lucky you).

Raymond has an interesting discussion about it on his blog with an in-place solution given https://devblogs.microsoft.com/oldnewthing/20170102-00/?p=95095

I've taken the liberty to adjust his solution for arrays. You can find the original version working on vectors in his blog.

#include <iostream>

template<typename T, size_t N>
void apply_permutation(T * v, size_t * indices)
{
    using std::swap; // to permit Koenig lookup
    for (size_t i = 0; i < N; i++) {
        auto current = i;
        while (i != indices[current]) {
            auto next = indices[current];
            swap(v[current], v[next]);
            indices[current] = current;
            current = next;
        }
        indices[current] = current;
    }
}

int main(){
    const int N = 5; 
    std::string data[N] = {"a5","a4","a8","a1","a3"};
    size_t idx[N] = {3,0,4,1,2};
    apply_permutation<std::string,N>(data, idx);

    for(auto & s : data){
        std::cout << s << std::endl;
    }
}

Output:

g++ test2.cpp && ./a.exe
a1
a5
a3
a4
a8

How do I sort a std::vector by the values of a different std::vector?

friol's approach is good when coupled with yours. First, build a vector consisting of the numbers 1…n, along with the elements from the vector dictating the sorting order:

typedef vector<int>::const_iterator myiter;

vector<pair<size_t, myiter> > order(Index.size());

size_t n = 0;
for (myiter it = Index.begin(); it != Index.end(); ++it, ++n)
    order[n] = make_pair(n, it);

Now you can sort this array using a custom sorter:

struct ordering {
    bool operator ()(pair<size_t, myiter> const& a, pair<size_t, myiter> const& b) {
        return *(a.second) < *(b.second);
    }
};

sort(order.begin(), order.end(), ordering());

Now you've captured the order of rearrangement inside order (more precisely, in the first component of the items). You can now use this ordering to sort your other vectors. There's probably a very clever in-place variant running in the same time, but until someone else comes up with it, here's one variant that isn't in-place. It uses order as a look-up table for the new index of each element.

template <typename T>
vector<T> sort_from_ref(
    vector<T> const& in,
    vector<pair<size_t, myiter> > const& reference
) {
    vector<T> ret(in.size());

    size_t const size = in.size();
    for (size_t i = 0; i < size; ++i)
        ret[i] = in[reference[i].first];

    return ret;
}

Sort a 3D std::vector based on values in a 1D std::vector

If your goal is to sort the scores and maintain the sorted scores with their relative position in the 3D vector, as the comment suggested and based on this answer, you can sort an array of indices that are based on the score criteria.

After sorting the indices, you use the indices to "point to" each sorted item in the 3D vector.

Here is an example:

#include <algorithm>
#include <vector>
#include <numeric>

int main()
{
    std::vector<std::vector<std::vector<char>>> children;
    std::vector<int> score;
    //...
    // Assume score and children have values
    //...
    // Sort the 3D vector based on the scores     
    // Set up the index vector
    std::vector<int> index(score.size());
    std::iota(index.begin(), index.end(), 0);
    //...
    // sort the indices based on the scores
    std::sort(index.begin(), index.end(), [&](int n1, int n2)
    { return score[n1] < score[n2]; });
    //...
    // Do something with the "sorted" 3D vector
    // The first sorted child is children[index[0]], the second is children[index[1]], etc.
}

Note that the linked answer has a thorough explanation of why and when this technique is used.

---

Related Topics