Array Transformation

Introduction

Suppose that you have an array of sorted integers that are numbered from 12 laid out horizontally. A transformation NI. be performed on this array where it is split in half vertically, and the leftmost values are placed on top of the rightmost values. This stacking transformation Miff be repeated on the result of the previous transformation until the resulting array is a single column of values.

Problem

Write a function that returns the array in the appropriate order after the stacking transformation takes place. The input to this function is an array of sequential integers, numbered from 1 to 2^n.

EXAMPLE 
The stacking transformation on an array of size 23. or 8: 
Step 1: 1 2 3 4 | 5 6 7 8 

Step 2 : 1 2 | 3 4  
         5 6 | 7 8 

Step 3: 
        1 | 2
        5 | 6
        3 | 4
        7 | 8

Result:

        1
        5
        3
        7
        2
        6
        4
        8

• Approach:

  • There are plenty of way of going about this problem. I wouldnt doubt if there is a sequence that generates this recursive-like problem.

  • Properties: 2^n is always even, the sequence generated is symetric.

  • I decided to use iterators to continuously split the arrays untill they are of size 1.

template<typename T>
auto get_center_iter(vector<T> &main, unsigned add) {
    return main.begin() + add;
}

vector<vector<unsigned int>> split_stack_num(unsigned num) {

    vector<unsigned> orig(num);
    for (unsigned i = 1; i <= num; i++) orig[i - 1] = i;

    unsigned count = 0;
    vector<vector<unsigned>> vert;
    vert.push_back(orig);

    unsigned max_divide = log2(num);
    while (max_divide > 0) {
        int cur_size = vert.size();
        unsigned add = vert.at(cur_size - 1).size() / 2; // latest added vector
        for (int i = 0; i < cur_size; i++) {
            auto iter_center = get_center_iter(vert.at(i), add);
            vector<unsigned> temp(iter_center, vert.at(i).end());
            vert.push_back(temp);
        }
        max_divide--;
    }

    return vert;
}

int main() {
    print2d(split_stack_num(pow(2, 4)));
    pause();
}