Inplace Permutation

inplace.hpp

#ifndef INPLACE_ALGORITHMS
#define INPLACE_ALGORITHMS

template<
    class value_t,
    class index_t> 
void permute(
    value_t * data,
    index_t * perm,
    index_t length) {

    for (index_t i = 0; i < length; i++) {
        if (perm[i] >= length) {
            
            // unmark
            perm[i] -= length;
            continue;
        }
        
        auto v = data[i];
        auto j = perm[i];

        while (j != i) {

            // swap
            auto tmp = data[j]; data[j] = v; v = tmp;

            // hop and mark as visited
            perm[j] += length;
            j = perm[j]-length;
        }

        data[i] = v;
    }
}

#endif