как заменить вложенные циклы на с++

[+VANO+]

есть код:
for(int i=0; i<n; i++){
// условие1
for(int i1=0; i1<n; i1++){
// условие2
for(int i2=0; i2<n; i2++){
// условие3
.
.
.
}
}
}
всего k циклов. Чем можно всё это заменить? Если рекурсией, то как?
заранее спасибо

[arseniiv]

Насколько я понимаю, надо взять массив, который будет изображать все переменные-итераторы, и ходить по нему нехитрым способом, проверяя значения его элементов на конечность, увеличивая их и присваивая начальные значения когда следует. Раз «ходить» — значит, нужен индекс активного (в котором мы изменяем переменную) цикла. А ещё, естественно, надо не забывать выполнять тело цикла.

Попробуйте теперь.

-- Сб дек 18, 2010 22:52:37 --

Кстати, зачем вам такое? Вдруг можно упростить.

-- Сб дек 18, 2010 22:55:08 --

+VANO+ в сообщении #388862 писал(а):

// условие1

Это означает, что там какой-то if стоит или что?

P. S. В следующий раз используйте [syntax]: topic26708.html (Тссс, если будут спрашивать, я ничего такого не говорил.)

[+VANO+]

arseniiv в сообщении #388876 писал(а):

+VANO+ в сообщении #388862 писал(а):

// условие1

Это означает, что там какой-то if стоит или что?

но if никакого отношения к следующему фору не имеет.

[arseniiv]

В принципе, в любом случае это бы не помешало. Если бы имел, можно было бы не выполнять много циклов, а в этом случае, если все ifы имеют похожий вид (а точнее, могут быть засунуты в цикл по номеру цикла), с ними всё легко, они впишутся в систему. Будут выполняться при изменении «своей» итерационной переменной.

Вы когда пробовать-то совет будете? Если что-то не выйдет, покажу более подробно. Хотя не исключено, что есть лучшее решение, чем моё. Какое-нибудь неочевидное как быстрое перемножение матриц.

[Circiter]

2+VANO+

Цитата:

Чем можно всё это заменить?

Фактически, каждая итерация такой конструкции эквивалентна прибавлению единице к $k$-значному числу в $n$-чной системе счисления. Цифры этого числа дают нужный вам набор i, i1, i2, ... Единица прибавляется также как и на бумажке.

-- Вс дек 19, 2010 01:44:56 --

Также можно смотреть на все возможные наборы счетчиков как на элементы декартовой степени $[0;\ n[^k$. Я тоже когда-то искал что-нибудь стандарное из STL для работы с декартовыми произведениями, но ничего не нашел... В любом случае погуглите еще разок по словам "cartesian product in c++", может быть уже кто-нибудь придумал решение.

[arseniiv]

(2 Criticer)

Circiter в сообщении #388977 писал(а):

Фактически, каждая итерация такой конструкции эквивалентна прибавлению единице к $k$-значному числу в $n$-чной системе счисления. Цифры этого числа дают нужный вам набор i, i1, i2, ...

А так раскладывать по цифрам каждый раз не будет дольше? А ещё это всё может не влезть и в Int64.

[Circiter]

(2asreiniv)

Я там добавил про бумажку. Необязательно использовать нативные числа, можно просто вектор (вы уже предложили алгоритм в начале темы).

[arseniiv]

(Оффтоп)

[Circiter]

2+VANO+

Цитата:

Если рекурсией, то как?

Ну а это вообще элементарно. Просто оставляете один цикл, итерирующий счетчик, соответствующий уровню рекурсивной вложенности, а все остальные $k-1$ штук циклов заменяете единственным вызовом самого себя (если остались свободные счетчики). Т.е. что-то вроде:

Используется синтаксис C++

int i[k];

void f(int Level)
{
    if(Level<k)
        for(i[Level]=0; i[Level]<n; i[Level]++)
        {
            // One of your conditions here.

            f(Level+1) // Recursive call.
        }
    else
        // Innermost level (using i[0]..i[k-1]).
}

f(0);
 

Вышеописанное прибавление единицы может выглядеть так (нерекурсивное инкрементное решение):

Используется синтаксис C++

int i[k]; // Initialize to zeroes.

bool Next()
{
    for(int c=0; c<k; c++)
        if(i[c]>=n-1) // Overflow detected.
            i[c]=0;
        else
        {
            i[c]++; // Change a digit.
            return true;
        }

    return false;
}
 

Эта функция генерирует следующую комбинацию значений счетчиков и возвращает истину, если это новая комбинация. Т.е., использовать её надо примерно так: do /* Innermost logic. */ while(Next());. Но здесь надо ещё подумать, куда же впендюрить ваши условия...

Можно ещё попробовать метапрограммирование от boost, но там используется препроцессор для генерации вложенных циклов.

[arseniiv]

Circiter в сообщении #389017 писал(а):

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

Тогда можно сделать функцию с условиями, принимающую номер цикла, и передавать её в Next() (?)

[Circiter]

Все верно, но проблема-то не в том, как передать функцию, а где и когда её вызвать. :) Код-то должен получиться эквивалентным решению с вложенными циклами. Но я думаю, что топикстартер разберется.

[+VANO+]

Спасибо всем. Во всём разобрался, всё работает