c++ - Prev_permutation 与 Next_permutation 难度

Question

我正在尝试一个示例程序来了解上一个和下一个排列之间的区别。但是，我的程序似乎无法正常运行。我通过询问数组中元素的数量来启动程序，然后使用简单的 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 and that's it)。然后 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 的循环将从第一个开始，因此它将在返回之前正确生成所有 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因为翻转。