Как я могу переписать эту функцию в нерекурсивной форме?Как я могу переписать эту функцию в нерекурсивной форме?
void generate(int pos)
{
if (pos == n + 1)
{
print_table();
}
else
{
for (int i = 1; i <= n; i++)
{
if (!used[i])
{
used[i] = true;
perm[pos] = i;
generate(pos + 1);////recursion
used[i] = false;
}
}
}
}
Этот код вызывает print_table() для каждой перестановки чисел 1, ..., n. Для этого в C++ есть встроенный инструмент.
#include <algorithm>
void generate() {
int n = 10; // or whatever
std::vector<int> perm(n);
for(int i=0; i<n; i++) perm[i] = i+1;
do {
print_table(perm);
} while(std::next_permutation(perm, perm+n));
}
Упс: Я исправил это сейчас. В этом коде не должно быть 'used'. –
Спасибо! Отлично! Это почти работает. Но, кроме того, ваша функция создает для меня бесполезные результаты. На мой взгляд, эта проблема в алгоритме std :: next_permutation –
Обратите внимание, что значения хранятся в 'perm [0], ..., perm [n-1]', тогда как вы, возможно, ожидали, что они будут сохранены в 'perm [ 1], ..., perm [n] '. Обычно в C/C++ для индексирования массивов следует начинать с 0. –
Ваш код представляется стандартным рекурсивным алгоритмом для генерации всех перестановок списка элементов. Вместо того, чтобы пытаться механически массировать рекурсивный алгоритм в итеративном (что, вероятно, потребует какой-то стек), вы можете посмотреть итеративные алгоритмы для перечисления всех перестановок списка. Например, C++ предоставляет алгоритм std::next_permutation, который вы можете использовать для перечисления перестановок. Для справки, у меня есть a simple implementation of this algorithm вместе с комментарием, объясняющим, как это работает.
Надеюсь, это поможет!
Откуда берется 'n'? –
Какое это имеет значение, @Vite? –
Использовать явный стек? Кстати, что делает эта функция? –