Почему next_permutation пропускает некоторые перестановки?

Почему эта простая функция не выводит все перестановки введенной 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);
}

Ответ 1

Чтобы вернуть все перестановки в цикле до тех пор, пока next_permutation не вернет false, вектор должен быть отсортирован до начала цикла. next_permutation возвращает перестановки в порядке возрастания. Поэтому, если вы начинаете с несортированного вектора, он начнет частично через серию перестановок.

std::sort(letters.begin(), letters.end());
do 
    lettercombos.push_back(letters);        
while(next_permutation(letters.begin(), letters.end()));

Ответ 2

Как уже указывалось в некоторых ранее сделанных ответах, если вы хотите использовать возвращаемое значение 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).

Ответ 3

Вам нужно отсортировать вход, next_permutation вернет следующую перестановку в лексикографическом порядке. Поскольку входная перестановка: "gnary" лексикографически "больше", чем перестановка, такая как "сердитый" , эти "меньшие" перестановки никогда не будут достигнуты.

Вы можете отсортировать строку с помощью std::sort()

Ответ 4

Возвращаемое значение bool next_permutation похоже на условие переполнения или бит переноса. Он false, когда он продвигается от последней перестановки к первому, в лексикографическом порядке. Но он все равно продвигается безоговорочно.

Если вы знаете, что существует ровно 120 перестановок, вы можете игнорировать возвращаемое значение и просто зацикливаться вслепую:

for ( int i = 0; i != 120; ++ i ) {
    lettercombos.push_back(letters);        
    next_permutation(letters.begin(), letters.end());
}