Блог

Главная - Вопросы по программированию - вычисления с перестановками в c

вычисления с перестановками в c

#c #recursion #permutation

#c #рекурсия #перестановка

Вопрос:

Я хочу написать программу, которая получает целое число n и печатает все перестановки 1,2, …, n . Я знаю, что есть рекурсивный способ сделать это, и я знаю накладные расходы на вызовы функций. Есть ли какой-нибудь способ сделать это без рекурсии??

Комментарии:

1. Если вы что-то вычисляете и печатаете немедленный результат, вам никогда не нужно беспокоиться о накладных расходах: печать сама по себе очень медленная, и вы не хотите этого делать, когда результат будет больше, скажем, 1000 строк. Но для таких безобидных объемов данных производительность вообще не имеет значения.

2. @leftaroundabout: это не только накладные расходы на производительность. Проблема может быть в очень больших входных данных, в том, что в системах с небольшим стеком будет слишком много рекурсии

3. @sehe: хорошо, я должен был сделать это утверждение немного менее общим. Размер стека в данном конкретном случае не имеет значения, поскольку рекурсивное вычисление перестановок (при условии обычного алгоритма) выполняется O(n!) по времени, но только O(n) по глубине рекурсии. Поэтому, если вы создадите n очень большой (достаточно большой, чтобы быть проблемой стека), программа все равно никогда не завершится.

Ответ №1:

Да, вы можете выполнять это итеративно с std::next_permutation помощью from <algorithm> в качестве while условия, или в зависимости от того, как вы настроили цикл, это может быть одним из случаев, когда do...while это более уместно.

Ответ №2:

 #include <vector>
#include <algorithm>

std::vector<int> v = { 1,2,3,4,5,6,7,8,9,10 }; // see std::iota also


// important: sort v if not sorted
std::sort(v.begin(), v.end());

while (std::next_permutation(v.begin(), v.end()))
{
      // use v (unique permutation)
}
// use v: first sorted position