std::next_permutation 实现说明

Question

我很好奇 std:next_permutation 是如何实现的，所以我提取了 gnu libstdc++ 4.7 版本并清理了标识符和格式以生成以下演示……

 #include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename It>
bool next_permutation(It begin, It end)
{
        if (begin == end)
                return false;

        It i = begin;
        ++i;
        if (i == end)
                return false;

        i = end;
        --i;

        while (true)
        {
                It j = i;
                --i;

                if (*i < *j)
                {
                        It k = end;

                        while (!(*i < *--k))
                                /* pass */;

                        iter_swap(i, k);
                        reverse(j, end);
                        return true;
                }

                if (i == begin)
                {
                        reverse(begin, end);
                        return false;
                }
        }
}

int main()
{
        vector<int> v = { 1, 2, 3, 4 };

        do
        {
                for (int i = 0; i < 4; i++)
                {
                        cout << v[i] << " ";
                }
                cout << endl;
        }
        while (::next_permutation(v.begin(), v.end()));
}

输出如预期：http: //ideone.com/4nZdx

我的问题是：它是如何工作的？ i 、 j 和 k 是什么意思？它们在执行的不同部分有什么价值？证明其正确性的草图是什么？

很明显，在进入主循环之前，它只检查琐碎的 0 或 1 元素列表案例。在主循环的入口处，我指向最后一个元素（不是一个过去的结尾），并且列表至少有 2 个元素长。

主循环的主体中发生了什么？

原文由 Andrew Tomazos 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

让我们看一些排列：

 1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
...

我们如何从一个排列转到下一个排列？首先，让我们以不同的方式看待事物。 我们可以将元素视为数字，将排列视为数字。以这种方式查看问题， 我们希望以“升序”顺序排列排列/数字。

当我们订购数字时，我们希望“以最小的数量增加它们”。例如在数的时候我们不数 1,2,3,10,…，因为中间还有 4,5,…，虽然 10 大于 3，但是有缺失的数字可以通过以较小的量增加 3。在上面的示例中，我们看到 1 保持第一个数字，因为最后 3 个“数字”有许多重新排序，这“增加”了较小的排列。

那么我们什么时候最终“使用” 1 ？当最后 3 位数字不再有排列时。

什么时候不再有最后 3 位数字的排列？当最后 3 位数字按降序排列时。

啊哈！这是理解算法的关键。 我们只在右边的所有内容都按降序排列时更改“数字”的位置， _因为如果它不是按降序排列，那么还有更多的排列要走_（即我们可以“增加”排列更小的数量） .

现在让我们回到代码：

 while (true)
{
    It j = i;
    --i;

    if (*i < *j)
    { // ...
    }

    if (i == begin)
    { // ...
    }
}

从循环中的前 2 行开始， j 是一个元素，而 i 是它之前的元素。

然后，如果元素按升序排列，（ if (*i < *j) ）做一些事情。

否则，如果整个事情是按降序排列的（ if (i == begin) ）那么这是最后一个排列。

否则，我们继续，我们看到 j 和 i 本质上是递减的。

我们现在了解了 if (i == begin) 部分，所以我们只需要了解 if (*i < *j) 部分。

另请注意：“那么如果元素按升序排列……”这支持了我们之前的观察，即“当右边的所有内容都按降序排列时”我们只需要对数字做一些事情。升序 if 语句本质上是找到“右边的一切都按降序排列”的最左边的地方。

让我们再看一些例子：

 ...
1 4 3 2
2 1 3 4
...
2 4 3 1
3 1 2 4
...

我们看到，当一个数字右边的所有内容都按降序排列时，我们 找到下一个最大的数字并将其放在前面，然后 将剩余的数字按升序排列。

让我们看一下代码：

 It k = end;

while (!(*i < *--k))
    /* pass */;

iter_swap(i, k);
reverse(j, end);
return true;

好吧，因为右边的东西是按降序排列的，要找到“下一个最大的数字”，我们只需要从最后迭代，我们在前 3 行代码中看到。

接下来，我们用 iter_swap() 语句将“下一个最大的数字”交换到前面，然后由于我们知道该数字是第二大的，我们知道右边的数字仍然是降序的，所以要按升序排列，我们只需要 reverse() 它。

原文由 flight 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

gcc 实现按字典顺序生成排列。 维基百科 解释如下：

以下算法在给定排列之后按字典顺序生成下一个排列。它就地改变了给定的排列。

1. 找到满足 a[k] < a[k + 1] 的最大索引 k。如果不存在这样的索引，则排列是最后一个排列。
2. 找到最大的索引 l 使得 a[k] < a[l]。由于 k + 1 是这样一个索引，所以 l 是很好定义的并且满足 k < l。
3. 将 a[k] 与 a[l] 交换。
4. 反转从 a[k + 1] 到最后一个元素 a[n] 的序列。

原文由 TemplateRex 发布，翻译遵循 CC BY-SA 3.0 许可协议