Prev_permutation和Next_permutation的区别难度

Question

Prev_permutation和Next_permutation的区别难度

c++algorithmsortingpermutationprobability

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种不同排列。我似乎无法理解发生了什么。

- Josh

2个回答

3

< p > prev_permutation 和 next_permutation 考虑到的所有排列都有明确定义的字典顺序。您提供给它们的数组在该顺序中具有某个位置。

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

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

如果您需要某个集合的所有排列，则需要先对集合进行sort ，然后使用 next_permutation 。

- Drew Dormann

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- 6502 · Accepted Answer

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 和 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。