为什么 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

到return循环中的所有排列直到next_permutation为returns false，向量必须在循环开始前排序。 next_permutation returns 升序排列。因此，如果您从一个未排序的向量开始，它将从一系列排列的一部分开始。

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

Answer 2

您需要对输入进行排序，next_permutation将return下一个字典序排列。因为输入排列："gnary" 比 "angry" 这样的排列在字典序上 "larger"，那些 "smaller" 永远不会达到排列。

您可以使用 std::sort()

对字符串进行排序

Answer 3

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

如果你知道恰好有 120 个排列，你可以忽略 return 值并盲目循环：

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

Answer 4

正如之前做出的一些回答所述，如果您想使用 std::next_permutation 的 bool return 值来停止迭代，您必须确保开始来自 "sorted" 排列。否则，您的周期将提前终止。

但这不是绝对必要的。

通过std::next_permutation枚举的排列形成一个循环序列，无始无终，也就是说你可以无限调用std::next_permutation，它会循环一次又一次地通过相同的 120 次排列序列。这意味着您可以从该循环中的任何排列开始。您只需要记住您的起始排列并观察该排列再次出现的那一刻。在您到达原始排列的那一刻，迭代就结束了。在您的情况下，预计需要对 std::next_permutation.

进行 120 次调用

例如，以下代码打印 "abcde" 集合的所有 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 的 return 值（来自算法内部 "for free" ), 所以如果你对预排序起始排列的解决方案感到满意，那么它确实是一种更有效的方法。

或者，如果您知道循环中排列的确切数量（在本例中为 120），您可以简单地调用 std::next_permutation 确切的次数（如@Potatoswatter 的回答中所建议）。

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

Why does next_permutation skip some permutations?

c++

permutation