Prev_permutation vs 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运行时,我得到了一个正确的6个不同的集合排列(0,1,2).我似乎无法理解发生了什么.

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将从第一个开始,因此它将在返回之前正确生成所有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以通知您这一事实.

如果你开始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.

在这种情况下,调用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,因为翻转.