Что такое алгоритм для печати перестановок строки с большой эффективностью?

Question

алгоритма, который я знаю, что это ниже, но почему я ненавижу этот подход является его сложность время O ((п + 1)!) Тоже хуже в случае больших строк

Start сортировки строки и печатать это как первую перестановку.
Теперь мы можем найти следующую перестановку следующим образом:

Пусть я в последний индекс, что вход [я] < вход [я + 1]. Если такого индекса нет, тогда все готово. Пусть j - последний индекс, такой как вход [i] < вход [j]. Вход обмена [i] с входом [j]. Обратный вход [i + 1] через вход [input.length - 1].

Есть ли лучший подход, чем один из приведенных выше? (Если объяснение через код, пожалуйста, рассмотреть С или С ++) ... просто я ожидал лучшего алгоритма с меньшей временной сложностью, чем один из приведенных выше

Answer 1

Есть n! перестановки для строки длиной n. Просто распечатать их - O(n * n!), как вы можете ожидать, что это будет намного эффективнее?

Answer 2

Имейте в виду, что в C++ STL имеет зЬй :: next_permutation, что делает работу вам нужно

Answer 3

Даже стандартный C++ реализации для печати перестановкам строки следует точно такой же алгоритм (std::next_permutation и std::prev_permutation)

std::string s; 
std::sort(s.begin(), s.end()); 
do { 
    std::cout << s << std::endl; 
} while(std::next_permutation(s.begin(), s.end()));