Iterate array elements in specific order

Question

I am trying to iterate a 1D-array/vector of integers in a specific order, but I can't wrap my head around it, to get the loop conditions right.

The input data is a one-dimensional vector of integers:

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

This input data is essentially a one dimensional representation of a 2D array/grid with subgroups:

+----+----+----+----+----+----+
| 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 |
+----+----+----+----+----+----+

This table is is grouped into multiple 2x4 subgroups:

I want to iterate this 1D input vector/array in the order that is indicated by the numbers. (Essentially going through every 2x4 subgroup, one after another). Inside of the loop, I want to load the 8 elements of the currently processed subgroup in a vector/int for further processing. So in the end I should process 6 subgroups, the first one holding the numbers 1 to 8, the second one 9 to 16 and so fourth .. The groups should be processed from left to right.

Note: The numbers in the input data just serve as an example, to make clear in which order the data should be processed. The input data could contain totally random values. The order of the values in each group should be kept. There should be no sorting/reordering inside a group. What is important are the constraints for the subgroup/array dimensions etc.

Together with the 1D array/vector I do know the dimensions of the grid and the size of the subgroups:

int grid_width = 6; // Variable, but will always be a multiple of 2, to match subgroup width
int grid_height = 8;  // Variable, but will always be a multiple of 4, to match subgroup height
const int group_width = 2; // Constant, subgroup width is always 2.
const int group_height = 4; // Constant, subgroup height is always 4.

My idea was to have one loop that iterates over the entire data, and then two loops that process the subgroups accordingly. But I really struggle getting the loop conditions and indices for the elements correct. My thought-process was something like this:

// Iterate over entire data
for (int i = 0; i < grid_width * grid_height; i += (group_width * group_height))
{
    int block[8];
    // Iterate groups in correct order
    for (int j = 0; j < group_height; j++)
    {
        for (int k = 0; k < group_width; k++)
        {
            // Grab current element in group
            int value = input_array[i * grid_width + j]; // ?? This ain't right

            // Add element to group array/vector
            block[??] = ??;
        }
    }

    // Do further processing with the group array
}

Can someone help me to loop over this correctly? I hope the question is clear enough. If not, let me know.

Answer 1

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