// 1,3,5,7…2,4,6,8… will become 1,2,3,4,5,6,7,8 // for T == int, positive

shuffle.cpp

// 1,3,5,7…2,4,6,8… will become 1,2,3,4,5,6,7,8
// for T == int, positive

#include <iostream>
#include <vector>
#include <string>

using namespace std;

template <typename T>
auto& operator <<(typeof(cout)& ostream, vector<T> const& a) {
    const size_t n = a.size()/2;

    size_t cnt=0;
    for (size_t i=0; i<a.size(); i++) {
        if (a[i]==i) cnt++;
        ostream << abs(a[i]) << (a[i+1] == i+1 ? "_" : " ");
    };
    ostream << " " << cnt << (cnt == a.size() ? "!" : "");
    return ostream;
}

vector<int> gen_i(int n) {
    vector<int> v(2*n);
    for (size_t i=0; i<n; i++) {
        v[i] = -i*2;
        v[n+i] = -(i*2+1);
    }
    v[2*n-1] = -v[2*n-1];
    return v;
}

int addr_of(int k, int n) {
    if (k%2) {
        return n/2+k/2;
    }
    else {
        return k/2;
    }
}

template <typename T>
int shuffle(vector<T> a) {

    static bool d = true;
    if (d) cout << 0 << " _" << a << endl;

    int cnt = 0;
    for (int i = 1; i < a.size(); i++) {
//        cnt++;
        if (a[i] > 0)
            continue;

        T buf = -a[i];
        int k = i;

        while (true) {
            cnt++;
            int q = addr_of(k, a.size());
            if (q == i)
                break;
            a[k] = -a[q];
            if (d) cout << cnt % 10 << " _" << a << " " << q << "->" << k << endl;
            k = q;
        }
        a[k] = buf;
        if (d) cout << cnt << " _" << a << " " << i << "->" << k << endl;
    }
//    cout << cnt << " _" << a << endl;
    return cnt;
}

template <typename T>
int transpose(vector<T> m)
{
    int w=m.size()/2, h=2;
    int cnt = 0;
    int start, next, i;
    T tmp;

    for (start = 0; start <= w * h - 1; start++) {
        next = start;
        i = 0;
        do {
//            cnt++;
            i++;
            next = (next % h) * w + next / h;
        } while (next > start);
        if (next < start || i == 1) continue;

        tmp = m[next = start];
        do {
            cnt++;
            i = (next % h) * w + next / h;
            m[next] = (i == start) ? tmp : m[i];
            next = i;
        } while (next > start);
    }
    return cnt;
}

int main() {
    vector<int> nums(20);
    for (size_t n=4; n<nums.size(); n++)
    {
        nums[n] = shuffle(gen_i(n));
//        nums[n] = transpose(gen_i(n));
    }
    for (auto num: nums) {
        if (num)  cout << num << " ";
    }
    cout << endl;
}