How to simplify this loop?

Question

Considering an array a[i], i=0,1,...,g, where g could be any given number, and a[0]=1.

for a[1]=a[0]+1 to 1 do
   for a[2]=a[1]+1 to 3 do
      for a[3]=a[2]+1 to 5 do
         ...
            for a[g]=a[g-1]+1 to 2g-1 do
               #print a[1],a[2],...a[g]#

The problem is that everytime we change the value of g, we need to modify the code, those loops above. This is not a good code.

Answer 1

Imagine you are representing numbers with an array of digits. For example, 682 would be [6,8,2].

If you wanted to count from 0 to 999 you could write:

for (int n[0] = 0; n[0] <= 9; ++n[0])
    for (int n[1] = 0; n[1] <= 9; ++n[1])
        for (int n[2] = 0; n[2] <= 9; ++n[2])
            // Do something with three digit number n here

But when you want to count to 9999 you need an extra for loop.

Instead, you use the procedure for adding 1 to a number: increment the final digit, if it overflows move to the preceding digit and so on. Your loop is complete when the first digit overflows. This handles numbers with any number of digits.

You need an analogous procedure to "add 1" to your loop variables.

Increment the final "digit", that is a[g]. If it overflows (i.e. exceeds 2g-1) then move on to the next most-significant "digit" (a[g-1]) and repeat. A slight complication compared to doing this with numbers is that having gone back through the array as values overflow, you then need to go forward to reset the overflowed digits to their new base values (which depend on the values to the left).

The following C# code implements both methods and prints the arrays to the console.

static void Print(int[] a, int n, ref int count)
{
    ++count;
    Console.Write("{0} ", count);
    for (int i = 0; i <= n; ++i)
    {
        Console.Write("{0} ", a[i]);
    }
    Console.WriteLine();
}

private static void InitialiseRight(int[] a, int startIndex, int g)
{
    for (int i = startIndex; i <= g; ++i)
        a[i] = a[i - 1] + 1;
}

static void Main(string[] args)
{
    const int g = 5;

    // Old method
    int count = 0;
    int[] a = new int[g + 1];
    a[0] = 1;
    for (a[1] = a[0] + 1; a[1] <= 2; ++a[1])
        for (a[2] = a[1] + 1; a[2] <= 3; ++a[2])
            for (a[3] = a[2] + 1; a[3] <= 5; ++a[3])
                for (a[4] = a[3] + 1; a[4] <= 7; ++a[4])
                    for (a[5] = a[4] + 1; a[5] <= 9; ++a[5])
                        Print(a, g, ref count);

    Console.WriteLine();
    count = 0;

    // New method

    // Initialise array
    a[0] = 1;
    InitialiseRight(a, 1, g);

    int index = g;
    // Loop until all "digits" have overflowed
    while (index != 0)
    {
        // Do processing here
        Print(a, g, ref count);

        // "Add one" to array
        index = g;
        bool carry = true;
        while ((index > 0) && carry)
        {
            carry = false;

            ++a[index];
            if (a[index] > 2 * index - 1)
            {
                --index;
                carry = true;
            }
        }
        // Re-initialise digits that overflowed.
        if (index != g)
            InitialiseRight(a, index + 1, g);
    }
}

Answer 2

Recursion is one way to solve this(although I was love to see an iterative solution).

!!! Warning, untested code below !!!

template<typename A, unsigned int Size>
void recurse(A (&arr)[Size],int level, int g)
{
   if (level > g) 
   { 
     // I am at the bottom level, do stuff here
     return;
   }

   for (arr[level] = arr[level-1]+1; arr[level] < 2 * level -1; arr[level]++)
   {

      recurse(copy,level+1,g);
   }
}

Then call with recurse(arr,1,g);

Answer 3

I'd say you don't want nested loops in the first place. Instead, you just want to call a suitable function, taking the current nesting level, the maximum nesting level (i.e. g), the start of the loop, and whatever if needs as context for the computation as arguments:

void process(int level, int g, int start, T& context) {
    if (level != g) {
        for (int a(start + 1), end(2 * level - 1); a < end; ++a) {
            process(level + 1, g, a, context);
        }
    }
    else {
        computation goes here
    }
}