Перестановка без рекурсии?
Я пытался использовать цикл for, чтобы заменить рекурсию, которую я обычно использую, но я обнаружил, что это сложнее, чем я думал. Может кто-нибудь сказать мне, как это сделать? Спасибо!
Например, с учетом вектора 2, 1, 3. Должно быть шесть перестановок:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Вектор ниже …
vector<int> simple;
simple.push_back(2);
simple.push_back(1);
simple.push_back(3);
РЕДАКТИРОВАТЬ: изменил порядок с 1 2 3 на случайный порядок 2 1 3
Решение
Я думаю, вы ищете std::next_permutation():
#include <iostream>
#include <algorithm>
#include <vector>
int main()
{
std::vector<int> simple{1, 2, 3};
do
{
for (auto e : simple) { std::cout << e << " "; }
std::cout << std::endl;
}
while (next_permutation(simple.begin(), simple.end()));
}
Вот живой пример.
Если вы не хотите начинать с отсортированного вектора, вы можете использовать std::next_permutation() следующим образом:
#include <iostream>
#include <algorithm>
#include <vector>
constexpr int factorial(int i)
{
return i == 0 ? 1 : i * factorial(i-1);
}
int main()
{
std::vector<int> simple{3, 1, 2};
for (int i = 0; i < factorial(simple.size()); i++)
{
std::next_permutation(simple.begin(), simple.end());
for (auto e : simple) { std::cout << e << " "; }
std::cout << std::endl;
}
}
Вот живой пример.
Обратите внимание, что, если размер вектора известен во время компиляции, как, кажется, имеет место в вашем примере, вы можете использовать std::array вместо std::vector, как показано в этот живой пример.
Другие решения
Других решений пока нет …