Перебор чисел

Кроме непосредственно тем по плюсам в роадмапе, есть еще маленькая строчка алгоритмы, которая включает в себя огромное количество информации и задач. Про бинарные деревья немного поговорили, сегодня про перебор чисел.

Идея задачи получить все последовательности чисел/символов в определенном диапазоне. Например, получить все комбинации чисел 1, 2, 3. Результатом будет 27 комбинаций подобного вида (приведена только часть из них, но думаю идея понятна)

111 112 113 121 122 123 … 331 332 333

Прежде чем приступать к реализации, я бы хотел показать один прием, который упростит дальнейшее понимание задачи. Вспомним, как обычно мы делаем циклы. Например, выведем числа от 0 до 2

int max_i = 3;
for(int i = 0; i < max_i; i++)
{
     cout << i << " " << endl;
}

Теперь перепишем все это в рекурсивном виде. Пугаться не стоит, так как ничего нового мы не добавили, а всего лишь переписали в другом виде.

void helper(int i, int max_index)
{
    if (i == max_index)
    {
        return;
    }

    cout << "index = " << i << endl;
    helper(i + 1, max_index);
}

int main(int argc, char *argv[])
{
    helper(0, 3);
    return 0;
}

Попробуем разобраться детально по шагам. Как мы знаем, рекурсия это функция, которая вызывает сама себя. Главное в рекурсии - определить условие, когда мы выходим из функции, чтобы не было бесконечных вызовов. В нашем случае это if (i == max_index).

Теперь смотрим по шагам.

1. В функции main выполняется функция helper с параметрами 0 и 3, т.е. i = 0, i_max = 3. Все как в нашем for.
2. i равно 0 и не равно 3, т.е. из рекурсии не выходим. условие if (i == max_index) не выполняется
3. выводим в cout текущий i, он в этот момент равен 0
4. снова выполняем функцию helper но уже с параметрами 0+1 и 3, т.е. держим в уме что функция helper(0, 3) ждет своего часа, но именно в этой точке программы мы погружаемся в helper(1, 3)
5. снова идем мимо if (i == max_index)
6. выводим 1 на экран
7. погружаемся в helper(2, 3), но помним что helper(0, 3) и helper(1, 3) все еще не закончились, т.к. ждут когда остальные функции рекурсии выйдут.
8. снова идем мимо if (2 == 3)
9. выводим 2 на экран
10. Погружаемся в helper(3, 3) и тут магия выполняется, т.е. выполняется if (i == max_index) и мы наконец то не погружаемся в рекурсию дальше.
11. Остается только закончить выполнение helper(2, 3), но так как там никакого кода больше нет, то просто выходим из этой функции и аналогично выходим из helper(1, 3) и helper(0, 3)

Сложно? Когда первый раз этим обмазываешься - да. Но в конце концов ты смотришь только на вход в рекурсию и когда выход из нее, остальное не важно

Так и зачем же все эти страдания, если можно просто написать for и не мучаться? Ответ прост - масштабирование, к сожалению for требует от нас понимания входных параметров, в нашем случае нужно написать гибкое решение, когда не известно сколько чисел и какой длины нужно перебрать.

Итак, вернемся к нашей задаче, с помощью цикла выше мы будем задавать длину строки перебора. А вот хороший вопрос, сколько комбинаций будет в итоге, как это посчитать? Нужно разницу чисел, которые мы перебираем возвести в степень длины строки. Условно говоря мы перебираем числа от 0 до 2, соотвественно у нас 3 числа: 0, 1, 2 и длина строки, которую мы хотим получить 3, т.к. нас интересуют последовательности вида 0 0 0, 0 0 1, 0 0 2 и т.п. Итого 3 в степени 3, т.е. 27 комбинаций.

Теперь посмотрим на код, который нам позволит это сделать

void helper(vector& res, int index, int max_index)
{
    if (index == max_index)
    {
        for(int i = 0; i < res.size(); i++)
            cout << res[i] << " ";
        cout << endl;
        return;
    }

    for(int i = 0; i < max_index; i++)
    {
        res[index] = i;
        helper(res, index + 1, max_index);
    }
}

int main(int argc, char *argv[])
{
    vector res(3);
    helper(res, 0, 3);
    return 0;
}

Логика прежняя, за исключением небольшого нюанса с вектором, это заранее подготовленный вектор размером 3, заполненный нулями vector res(3);

1. Из main вызываем helper(res, 0, 3);
2. Идем мимо условия выхода из рекурсии так как наш цикл еще не закончен if (index == max_index)
3. Заходим в новый для нас цикл, for(int i = 0; i < max_index; i++) он поможет на перебрать числа от 0 до 3 на каждом из уровней рекурсии.
4. Пока мы внутри helper(res, 0, 3) и i = 0, поэтому в res[0] = 0;
5. Погрузимся в рекурсию ниже т.е. helper(res, 1, 3);
6. Снова идет в цикл и присвоим в res[1] = 0; т.к. i = 0
7. Погрузимся в рекурсию ниже т.е. helper(res, 2, 3);
8. Аналогично в res[2] = 0; т.к. i = 0
9. Внутри helper(res, 3, 3); выводим на экран, то что находилось в res, а это напомню 0 0 0
10. Важно, что в этот момент мы выходим из рекурсии helper(res, 3, 3) и тут нужно вспомнить, а где мы находились до этого
11. А находились мы внутри helper(res, 2, 3); при этом напомню мы находимся внутри цикла где i = 0, т.е. цикл сделает i++ и начнется заново, т.е. в res[2] = 1; и снова погрузимся в helper(res, 3, 3); Просто магия какая то.
12. Внутри helper(res, 3, 3); снова распечатаем содержимое а это напомню 0 0 1

Думаю дальше нет смысла расписывать, так как идея точно такая же.

А теперь еще немного магии, я всего лишь поменял, то что выводить и теперь та же самая программа умеет печатать все комбинации вида

a a a 
a a b 
a a c 
a b a 
a b b 
a b c 

void helper(vector& res, int index, int max_index)
{
    if (index == max_index)
    {
        for(int i = 0; i < res.size(); i++)
            cout << res[i] << " ";
        cout << endl;
        return;
    }

    for(int i = 'a'; i <= 'c'; i++)
    {
        res[index] = i;
        helper(res, index + 1, max_index);
    }
}

int main(int argc, char *argv[])
{
    vector res(3);
    helper(res, 0, 3);
    return 0;
}

Думаю на этом можно закончить, возможно кому то пригодится в задачах, где нужно перебрать все возможные последовательности или хотя бы прибавит понимания, как в принципе решаются подобные задачи.