performance – Combinatorics, C++ and optimization


Note: I have a working solution, my question is about optimization and other approaches.

Problem Description

Hello, I’m re-writing an old program I made that solves nonograms.
As part of solving it, I generate (for some of the lines) an array of all possible ways to fit the numbers in.

I want to create a piece of code, that will iterate all the positions in which I can put the spaces, for example: if there’s a line with size 5, and the numbers are 1, 1, there are multiple ways do order the numbers, like 1-1--, 1--1-, 1---1, --1-1, ... (- is a white box, while 1 will be black).

Problem Breakdown

So if we look at the example above, we can describe the options like this:

  1. The total size is 5, and we have two 1, therefore we have 2 white boxes to play around with (1 must be between the numbers), I have another function that calculates that “free space”.

  2. We can index the possible places for the spaces this way: (0) 1 (1) 1 (2), meaning the spaces can go in each of the (indexes).

  3. All the options of placing the spaces can be solved with nested loops, but since the “free space” and the possible indexes are dynamic, this is not an option.

  4. For solution I try to create “dynamic” nested loops, with any range and depth, the question is:

Is there a more efficient way of doing so?

Possible Solution

The scope my question refers to is not related specifically to solving a nonorgram or even a specific language, but since I’m writing this in C++, I will post my attempt for a code that does so:

#include <vector>
#include <iostream>

using namespace std;

int main() {
    int iterators_number = 3; // Number of iterators, bubble sort for example uses 2, note: this is not for bubble sorting.
    int iterators_range = 3; // The maximum value for the iterators values, can be the size of the array for example.
    int move_index;

    vector<int> options_iteration(iterators_number, 0);

    while (true) {
        for (int i = 0; i < iterators_number; i++) cout << options_iteration(i) << " ";
        cout << endl;

        for (move_index = iterators_range - 1;
             (move_index >= 0) && (options_iteration(move_index) > iterators_range - 1); move_index--);
        if (move_index < 0) break;
        int new_value = options_iteration(move_index) + 1;
        for (; move_index < iterators_range; move_index++) options_iteration(move_index) = new_value;
    }

    return 0;
}

Output:

0 0 0 
0 0 1 
0 0 2 
0 0 3 
0 1 1 
0 1 2 
0 1 3 
0 2 2 
0 2 3 
0 3 3 
1 1 1 
1 1 2 
1 1 3 
1 2 2 
1 2 3 
1 3 3 
2 2 2 
2 2 3 
2 3 3 
3 3 3 

If anyone is interested in the full implementation, once it’s done and fully documented, I will upload it to my GitHub account.

Thanks in advance for the helpers and commentators.