Почему эта простая функция не выводит все перестановки введенной 5-строчной строки? Я думаю, что должно быть 120, и только выходы 90.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
// Creates permutation lists for strings
vector<string> createdcombos2(string letters)
{
vector<string> lettercombos;
cout << "Letters are: " << letters << endl; //input string
do
lettercombos.push_back(letters);
while(next_permutation(letters.begin(), letters.end()));
cout <<"Letter combos: " << endl; //print out permutations
for (auto i : lettercombos)
cout << i << endl;
cout << endl << lettercombos.size() << endl; //number of permutations
return lettercombos;
}
int main()
{
string letters = "gnary";
vector<string> lettercombos;
lettercombos = createdcombos2(letters);
}
Чтобы вернуть все перестановки в цикле до тех пор, пока next_permutation не вернет false, вектор должен быть отсортирован до начала цикла. next_permutation возвращает перестановки в порядке возрастания. Поэтому, если вы начинаете с несортированного вектора, он начнет частично через серию перестановок.
std::sort(letters.begin(), letters.end());
do
lettercombos.push_back(letters);
while(next_permutation(letters.begin(), letters.end()));
Как уже указывалось в некоторых ранее сделанных ответах, если вы хотите использовать возвращаемое значение bool для std::next_permutation, чтобы остановить итерации, вы должны убедиться, что вы начинаете с "отсортированной" перестановки. В противном случае ваш цикл закончится преждевременно.
Это не совсем необходимо.
Перестановки, перечисленные через std::next_permutation, образуют циклическую последовательность без начала или конца, что означает, что вы можете называть std::next_permutation неопределенно, и снова и снова будет повторяться одна и та же последовательность из 120 перестановок. Это означает, что вы можете начать с абсолютно любой перестановки в этом цикле. Вам просто нужно запомнить начальную перестановку и посмотреть, как эта перестановка появляется снова. В тот самый момент, когда вы достигли первоначальной перестановки, итерация завершена. В вашем случае он будет принимать 120 вызовов std::next_permutation.
Например, следующий код печатает все 5-буквенные перестановки для "abcde", даже если он начинается с полностью произвольного
std::string start = "cadeb", current = start;
do
std::cout << current << std::endl;
while (std::next_permutation(current.begin(), current.end()), current != start);
Можно заметить, что сравнение перестановок на каждой итерации цикла дороже, чем использование возвращаемого значения std::next_permutation (которое приходит "бесплатно" из встроенных алгоритмов), поэтому, если вы довольны решение, которое предварительно сортирует начальную перестановку, тогда это действительно более эффективный способ сделать это.
В качестве альтернативы, если вы знаете точное количество перестановок в цикле (в этом случае 120), вы можете просто называть std::next_permutation ровно столько раз (как указано в ответе @Potatoswatter).
Вам нужно отсортировать вход, next_permutation вернет следующую перестановку в лексикографическом порядке. Поскольку входная перестановка: "gnary" лексикографически "больше", чем перестановка, такая как "сердитый" , эти "меньшие" перестановки никогда не будут достигнуты.
Вы можете отсортировать строку с помощью std::sort()
Возвращаемое значение bool next_permutation похоже на условие переполнения или бит переноса. Он false, когда он продвигается от последней перестановки к первому, в лексикографическом порядке. Но он все равно продвигается безоговорочно.
Если вы знаете, что существует ровно 120 перестановок, вы можете игнорировать возвращаемое значение и просто зацикливаться вслепую:
for ( int i = 0; i != 120; ++ i ) {
lettercombos.push_back(letters);
next_permutation(letters.begin(), letters.end());
}