4

我正在尝试一个示例程序来掌握 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 种不同排列。我似乎无法理解发生了什么。

4

2 回答 2

8

prev_permutation并按next_permutation字典（“字母”）顺序生成所有排列，false一旦循环完成，它们就会返回（即，如果在调用prev_permutation第一个排列之后或在调用next_permutation最后一个排列之后）。

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

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

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

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

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以通知您这一事实。

如果您从prevmove to 2-1-0and function returns开始false，那么您调用next并且函数 move to0-1-2并false再次返回。

使用例如代替0,1以及2两个零和三个 1 的排列，字典顺序是：

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.

在这种情况下，调用next_permutation最后一个1-1-1-0-0将更改为第一个0-0-1-1-1并返回false；以类似的方式调用prev_permutation将更0-0-1-1-1改为1-1-1-0-0并会false因为翻转而返回。

于 2012-09-01T19:39:25.713 回答
3

prev_permutation两者都考虑的所有排列都next_permutation具有明确定义的字典顺序。您提供给他们的数组在该顺序中有一些位置。

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

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

如果您需要某个集合的所有排列，则需要先sort收集该集合，然后再使用next_permutation.

于 2012-09-01T19:40:07.943 回答