Iterate array elements in specific order

I could not see an understandable answer so far and therefore I will add one and also with very easy understandable and step by step code.

Code without comments and explanations has basically no meaning.

This problem at hand can be solved by using integer and modulo division and might be a training task for that. It is important to understand that we will of course need to calculate indices. Therefore, as a first abstraction, I show an example picture, but here using mainly indices. Please note: In C++ indices start with 0.

What you want to have, is groups, with indices as shown on the left side. The right side simple shows indices as per the source data given. We just have a new line or new row after all horizontal groups have been drawn.

The important properties are:

• group width,
• group height,
• number of groups in horzontal direction
• number of groups in vertical direction

From these basic given source properties we can calculate additionally and simply:

• number of elements per group -> group width * group heigth
• number of overall elements -> group width * group heigth * number of groups in horzontal direction * number of groups in vertical direction

There are more values that are important and can be calculated easily: For example

• offfset in next row -> group width * number of groups in horzontal direction
• offset in next vertical group -> offset in next row * group height
• number of resulting groups -> number of groups in horzontal direction * number of groups in vertical direction

Everything here is straightforward and easy understandable. Let us look at the example now.

Having a group width of 2 and a group height of 4, we have 8 elements per group.

Having 3 groups in horizontal direction, we observe that the index of an element in a next row is always: group width * number of groups in horizontal direction = 2 * 3 = 6 greater, than in the line above.

If we want to know the row offset in one group (with the height 4) for any row, regardless of the group, then we can first calculate index % group height, so, index % 4. which will result in a numbering sequence: 0,1,2,3,0,1,2,3,0,1,2,3 . . .

If we multiply this with the 6 above, we get: 0,6,12,18,0,6,12,18,0,6,12,18,...

Please look at the picture. If we go one row down in one group, we go 6 indices down. Lets call this as the row offset.

Next we need to check the columns. If we look at the columns, then we see that the first 4 elements of the target are in column 0, the next 4 elements are in column 1 and so on. So, we can simply calculate the columns by the integer division: index / group height. We get a sequence of: 0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,...

This offset needs to be limited to the maximum column per row, which we do again with a modulo division by the previously calculated row width, in our example 6. Result is then 0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0,0,0,0,1,1,1,1,2,2,2,2,...

This we will call the column offset.

If we add the column offset with the row offset (with the above multiplied by 6 values), then we get already 0,6,12,18,1,7,13,19,2,8,14,20,3,9,15,21, . . .

So, this works already for the first horizontal groups.

The vertical group offset is simple. Basically the offset is: Index-Offset-To-Next-Vertical-Group = Index-Offset-To-Next-Row * GroupHeight = 6 * 4 = 24.

And, if we want to have the group-row-offset, then we simply make an integer division by the above calculated value (index / 24) and multiply that again with 24. This results in a sequence: 0....0,24....24,48....48,72....72,96....96,...

Lets call this thing vertical group offset.

If we add all offsets together, then we get the index in the source data by one simple calculation. Please note: For the ease of understanding, I splitted this in the below shown software into the described 3 parts.

Next come the target offsets. We need to calculate the group number: It is simply the index / number of elements per group, easy to understand. For a running source index this is 0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,.....

And the target index in the group is also simple. It is index % number of elements per group, so: 0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0,1,2,.....

Now, we splitted the one big problem into many smaller problems that could be solved by far more easier.

Basically, the whole copy loop can be done with a one liner, if we put all the calculated values directly in the assignment and omit the temporary constants.

Please see now the full and easy to understand and well commented code example.

#include <iostream>
#include <vector>
#include <array>

int main() {

    // This you may change --------------------------------------------------------------------------------------

    // Source data
    std::vector values{1, 5, 9, 13, 17, 21, 2, 6, 10, 14, 18, 22, 3, 7, 11, 15, 19, 23, 4, 8, 12, 16, 20, 24, 25, 29, 33, 37, 41, 45, 26, 30, 34, 38, 42, 46, 27, 31, 35, 39, 43, 47, 28, 32, 36, 40, 44, 48};

    // Define the dimension of one group
    constexpr unsigned int GroupWidth =  2;
    constexpr unsigned int GroupHeight = 4;

    // Define, how many groups we have in horizontal and vertical direction
    constexpr unsigned int NumberOfGroupsHorizontal = 3;
    constexpr unsigned int NumberOfGroupsVertical   = 2;

    // Calculated values ---------------------------------------------------------------------------

    // Resulting capacity values
    constexpr unsigned int NumberOfElementsPerGroup = GroupWidth * GroupHeight;
    constexpr unsigned int NumberOfOverallElements = GroupWidth * GroupHeight * NumberOfGroupsHorizontal * NumberOfGroupsVertical;

    // Resulting offset values for indices
    constexpr unsigned int IndexOffsetToNextRow = GroupWidth * NumberOfGroupsHorizontal;
    constexpr unsigned int IndexOffsetToNextVerticalGroup = IndexOffsetToNextRow * GroupHeight;

    // How many groups do we have overall
    constexpr unsigned int NumberOfResultingGroups = NumberOfGroupsHorizontal * NumberOfGroupsVertical;

    // First make a sanity check, if parameters are ok. Handles also 0-values
    if (values.size() == NumberOfOverallElements) {

        // Copy algorithm ------------------------------------------------------------------------------

        // Here, we will store the result
        std::array<std::array<int, NumberOfElementsPerGroup>, NumberOfResultingGroups> result{};

        // Iterate over all source data
        for (unsigned int index = 0; index < NumberOfOverallElements; ++index) {


            // Calculate index in array of source data -------------------------------------------------
            // Row offset per group
            const unsigned int  o1 = (index % GroupHeight) * IndexOffsetToNextRow; 
            // Column offset
            const unsigned int  o2 = (index / GroupHeight) % IndexOffsetToNextRow; 
            // Vertical group offset
            const unsigned int  o3 = (index / IndexOffsetToNextVerticalGroup) * IndexOffsetToNextVerticalGroup; 

            // Overall calculated index / offset. (Above three lines could be put here as a one liner)
            const unsigned int sourceDataIndex = o1 + o2 + o3;

            // The target group index ------------------------------------------------------------------
            const unsigned int targetGroupIndex = index / NumberOfElementsPerGroup;

            // The index in the target group
            const unsigned int indexInTargetGroup = index % NumberOfElementsPerGroup;


            // Copy resulting value --------------------------------------------------------------------
            result[targetGroupIndex][indexInTargetGroup] = values[sourceDataIndex];
        }

        // Show result to the user
        for (const auto& a : result) {
            for (const int i : a) std::cout << i << ' ';
            std::cout << '\n';
        }
    }
    else {
        // Some problem occured
        std::cerr << "\n*** Error: Wrong source data size or parameters\n";
    }
    return 0;
}

And with the above know how, you can now build one simple function:

std::vector<std::vector<int>> split(const std::vector<int>& v, const size_t ngh, const size_t ngv, const size_t gw=2U, const size_t gh=4U) {

    // Define resulting 2d vector
    std::vector<std::vector<int>> result(ngh * ngv, std::vector<int>(gw * gh,0));

    // Sanity check. Will also handle parameters being 0
    if (v.size() == gw*gh*ngv*ngh)
        // Copy values in simple for loop
        for (size_t i = 0U; i < v.size(); ++i)
            result[i/(gw*gh)][i%(gw*gh)] = v[((i%gh)*gw*ngh) + ((i/gh)%(gw*ngh)) + ((i/(gh*gw*ngh))*(gh*gw*ngh))] ;

    return result;
}

I suppose this will do the job:

Edit: I added this explanation since some people could not understand this solution so far although it just contains some simple linear index calculation, and since I did not see any non-TL;DR but complete solution : We iterate through the input data front to back. We always calculate the indices of where the value we read belongs to. We store the value to the appropriate indices. Groups are quadratic blocks. We use group_position_x to store our horizontal position inside each group. Analoguously we use group_position_y for the vertical position inside a group, starting from the left upper corner. We use col to state we are in the colth group in a row. Analoguously we use row to state we are in the rowth group in a column. We then can easily calculate where the value read from input has to be stored. The group is the col + [col-size] * rowth group of all. In a similar way we use the x and y corrdinates inside the group to see at which index inside the group the value just read has to be stored. Note that indices start at 0. Also, see the comments in the code below. The new values for col, row and the coordinates inside the groups are so to say incremented in each step. Of course, we talk about increment modulo some integer in each case. In some cases the "+1" happens if some overflow conditions of other indices are met.

using data_type = int // change type to correctly group data not being integers
using group = std::vector<data_type>; // reprensents the values of one group
const data_type DEFAULT{ -1 };

/**
@param data_begin begin iterator of the input data
@param data_end end iterator of the input data
@return a vector of all groups from top to bottom, from left to right.
*/
template<class _Const_Iterator>
std::vector<group> grouping(int grid_width, int grid_height, int group_width, int group_height, _Const_Iterator data_begin, _Const_Iterator data_end){
 const int GROUPS_PER_ROW{ grid_width / group_width };
 const int GROUPS_PER_COL{ grid_height / group_height };
 const int NUMBER_GROUPS{ GROUPS_PER_ROW * GROUPS_PER_COL };
 const int GROUP_SIZE{ group_width * group_height };
 std::vector<group> result(NUMBER_GROUPS, group(GROUP_SIZE, DEFAULT)); // create empty result vector with correct size.
 std::size_t group_index{ 0 }; // id of the current group
 std::size_t group_position_y{ 0 }; // currrent vertical position inside a group block
 std::size_t group_position_x{ 0 }; // current horizontal position inside a group block
 std::size_t row{ 0 }; // current row with respect to the groups
 std::size_t col{ 0 }; // current column with respect to the groups

 // iterate through all input data, copy data cell to target structur (result), calculate the correct indices for the next input data cell
 for (_Const_Iterator it{data_begin}; it != data_end; ++it){
  result[group_index][group_position_y + group_height * group_position_x] = *it;

  group_position_x = (group_position_x + 1) % group_width; // new horizontal position inside group
  auto old_col{ col };
  col = (col + (group_position_x == 0)) % GROUPS_PER_ROW; // new column with respect to the groups
  auto old_group_position_y{ group_position_y };
  group_position_y = (group_position_y  + (col == 0 && col != old_col)) % group_height; // new vertical position inside group
  row = (row + (group_position_y == 0 && group_position_y != old_group_position_y)) % GROUPS_PER_COL ; // new row with respect to the groups
  group_index = col + GROUPS_PER_ROW * row; 
 }
 return result;
}

In my personal opinion, it is better to not use too many nested loops and to do index calculation instead.

is this solution simple enough? you can find a working demo here: https://wandbox.org/permlink/5Qv9HKzpaU9ec6gF

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

constexpr int rowSize        = 8;
constexpr int columnSize     = 6;
constexpr int subGroupWidth  = 2;
constexpr int subGroupHeigth = 4;

void calculate(const vector<vector<int>>& arr, vector<vector<int>>& res)
{
    int index = 0;
    for (int i = 0; i < rowSize; i+=subGroupHeigth)
    {
        for (int j = 0; j < columnSize; j+=subGroupWidth)
        {
            // This represents a sub-group!
            res[index].push_back(arr[i][j]);
            res[index].push_back(arr[i+1][j]);
            res[index].push_back(arr[i+2][j]);
            res[index].push_back(arr[i+3][j]);
            res[index].push_back(arr[i][j+1]);
            res[index].push_back(arr[i+1][j+1]);
            res[index].push_back(arr[i+2][j+1]);
            res[index].push_back(arr[i+3][j+1]);
            ++index;
        }
    }
}

int main()
{
    vector<int> vec {1, 5, 9, 13, 17, 21, 2, 6, 10, 14, 18, 22, 3, 7, 11, 15, 19, 23, 4, 8, 12, 16, 20, 24, 25, 29, 33, 37, 41, 45, 26, 30, 34, 38, 42, 46, 27, 31, 35, 39, 43, 47, 28, 32, 36, 40, 44, 48};

    // Convert the vector to 2D array
    vector<vector<int>> arr (rowSize, std::vector<int>(columnSize));
    int row = -1;
    for (size_t i = 0; i < vec.size(); ++i)
    {
        if (i%columnSize == 0) ++row;
        arr[row][i%columnSize] = vec[i];
    }

    vector<vector<int>> result (columnSize);   // reserve the space for 6 arrays
    calculate(arr, result);                    // extract the 6 sub-groups in terms of arrays

    // Print the results
    for_each (begin(result), end(result), [](vector<int> &row){
        for (auto e : row) cout << e << " ";
        cout << endl;
    });
    return 0;
}