Prev_permutation与Next_permutation难度

Question

我正在尝试一个示例程序，以掌握prev和next排列之间的区别。然而，我的程序似乎不能正常工作。我通过询问数组中元素的数量来启动程序，然后使用一个简单的for循环构建数组

for(i = 0; i < x; i++)
        ptr[i] = i;

cout << "Possible permuations using prev_permutation: " << endl;
    do{
        for(i = 0; i < x; i++)
            cout << ptr[i] << " ";
        cout << endl;
    } while(prev_permutation(ptr, ptr+x));

cout << "Possible permuations using next_permutation: " << endl;
do{
    for(i = 0; i < x; i++)
        cout << ptr[i] << " ";
    cout << endl;
} while(next_permutation(ptr, ptr+x));

当我运行包含3个元素的示例代码时，(0，1，2)。prev_permutation给我(0，1，2，仅此而已)。然后next_permutation给我(2，1，0)。但是，当我注释prev_permutation部分的代码时，当只有next_permutation在运行时，我得到了集合(0，1，2)的6种不同的排列。我似乎不明白发生了什么事。

Answer 1

prev_permutation和next_permutation以字典序(“字母”)顺序生成所有排列，一旦循环完成，它们就返回false (即，如果在第一个排列上调用prev_permutation之后，或者在最后一个排列上调用next_permutation之后)。

所发生的是按照字典序顺序准备具有第一个排列的数组，然后调用prev_permutation。但是，这是第一个，因此prev_permutation将数组设置为最后一个排列，并返回false，因此退出循环。

现在您进入了next_permutation循环，但是数组的当前内容是字典序中的最后一个排列，因此next_permutation将设置第一个排列并返回false。

但是，如果删除prev_permutation部分，next_permutation循环将从第一个开始，因此在返回false之前，它将正确地生成所有6个排列。

您可以考虑按顺序列出的所有排列，并将当前配置作为此列表中的指针来可视化效果：

0-1-2 << you start here
0-2-1
1-0-2
1-2-0
2-0-1
2-1-0

当调用next_permutation时，你是在向下移动；当调用prev_permutation时，你是在向上移动。在列表之外时，两个函数都会将指针移动到另一端，并返回false来通知您这一事实。

如果从prev开始，移动到2-1-0，函数返回false，然后调用next，函数移动到0-1-2，再次返回false。

例如，使用两个0和三个1的排列而不是0、1和2的排列，字典序顺序是：

0-0-1-1-1
0-1-0-1-1
0-1-1-0-1
0-1-1-1-0
1-0-0-1-1
1-0-1-0-1
1-0-1-1-0
1-1-0-0-1
1-1-0-1-0
1-1-1-0-0

因此，要枚举所有它们，您需要从0-0-1-1-1开始并使用next_permutation，或者您需要从1-1-1-0-0开始并使用prev_permutation。

在这种情况下，在最后一个1-1-1-0-0上调用next_permutation将更改为第一个0-0-1-1-1，并返回false；类似地，在0-0-1-1-1上调用prev_permutation将更改为1-1-1-0-0，并由于翻转而返回false。

Answer 2

prev_permutation和next_permutation考虑的所有排列都有一个定义良好的字典序。您提供给他们的数组在这个顺序中有一些位置。

这就是为什么这两个函数都不能保证提供所有的排列。

如果您向prev_permutation提供了第一个可能的排列，那么在此之前将没有排列。同样，如果您的数组定义为(2，1，0)，则next_permutation不会提供任何新的排列。

如果您需要某个集合的所有排列，您可能希望先使用sort next_permutation**.** 集合，然后再使用