为什么next_permutation会跳过一些排列？

Question

为什么这个简单的函数不输出输入的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);
}

Answer 1

要在循环中返回所有排列直到next_permutation返回false,必须在循环开始之前对向量进行排序.next_permutation按升序返回排列.因此,如果你从一个未排序的向量开始,它将从一系列排列开始.

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

Answer 2

正如之前提出的一些答案所述,如果要使用bool返回值std::next_permutation来停止迭代,则必须确保从"排序"排列开始.否则,您的周期将提前终止.

但这并非绝对必要.

通过std::next_permutation形成没有开头或结尾的循环序列来枚举的排列,这意味着您可以std::next_permutation无限期地调用它并且将一次又一次地循环通过120个排列的相同序列.这意味着您可以从该循环中的绝对任何排列开始.你只需要记住你的起始排列,并观察这个排列再次出现的那一刻.在你到达原始排列的那一刻,迭代就结束了.在你的情况下,它预计将接到120个电话std::next_permutation.

例如,以下代码打印"abcde"set的所有5个字母的排列,即使它从完全任意的开始

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的回答中所建议的那样).

Answer 3

您需要对输入进行排序,next_permutation将按字典顺序返回下一个排列.因为输入排列:"gnary"在字典上比"愤怒"之类的排列"更大",所以永远不会达到那些"较小"的排列.

您可以使用排序字符串 std::sort()

Answer 4

返回bool值next_permutation类似于溢出条件或进位.它是false按照字典顺序从最后一个排列回到第一个排列的时候.但它仍然无条件地推进.

如果您知道正好有120个排列,则可以忽略返回值并盲目循环:

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