Как упростить этот цикл?

Question

Учитывая массив a[i], i=0,1,...,g, где g может быть любым заданным числом, а 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]#

Проблема в том, что каждый раз мы меняем значение g, нам нужно изменить код, эти циклы выше.Это не хороший код.

Answer 1

Представьте, что вы представляете числа с массивом цифр. Например, 682 будет [6,8,2].

Если вы хотите считать от 0 до 999, вы можете написать:

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

Но если вы хотите сосчитать до 9999, вам нужен дополнительный цикл.

Вместо этого вы используете процедуру добавления 1 к числу: увеличивайте конечную цифру, если она переполняется, переходите к предыдущей цифре и так далее. Ваш цикл завершен, когда первая цифра переполнена. Это обрабатывает числа с любым количеством цифр.

Вам нужна аналогичная процедура, чтобы «добавить 1» к вашим переменным цикла.

Увеличить последнюю «цифру», то есть a[g]. Если он переполнен (т. Е. Превышает 2g-1), перейдите к следующей наиболее значимой «цифре» (a[g-1]) и повторите. Небольшое осложнение по сравнению с выполнением этого с числами состоит в том, что, пройдя обратно через массив при переполнении значений, вам нужно идти вперед, чтобы сбросить переполненные цифры до их новых базовых значений (которые зависят от значений слева).

Следующий код C # реализует оба метода и выводит массивы на консоль.

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

Рекурсия - один из способов решения этой проблемы (хотя мне очень хотелось увидеть итеративное решение).

!!! Предупреждение, непроверенный код ниже !!!

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

Затем позвоните с recurse(arr,1,g);

Answer 3

Я бы сказал, что вам не нужны вложенные циклы. Вместо этого вы просто хотите вызвать подходящую функцию, принимая текущий уровень вложенности, максимальный уровень вложенности (т. Е. g), начало цикла и все, что требуется в качестве контекста для вычисления в качестве аргументов:

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