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个元素列表情况。在进入主循环时，“i”指向最后一个元素（而不是末尾后面的位置），并且列表至少有2个元素。

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

- Andrew Tomazos

---

嘿，你是怎么提取那段代码的？ 当我检查了 #include <algorithm> 后，发现代码完全不同，包含更多的函数。 - Manjunath

我刚刚注意到那个函数底部没有返回语句，这是一个好的实践吗？为什么不返回false呢？ - Jeff

@Jeff：while (true)语句是一个无限循环，函数只能通过内部return语句来返回循环所包含的内容。 - Andrew Tomazos

@Manjunath 这里是一样的：https://github.com/gcc-mirror/gcc/blob/63663e4e69527b308687c63bacb0cc038b386593/libstdc%2B%2B-v3/include/bits/stl_algo.h#L2883 - undefined

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)
    { // ...
    }
}

从循环的前两行可以看出，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;

由于右侧的数是按降序排列的，要发现“下一个最大数字”，我们只需要从末尾开始迭代，这在前三行代码中实现。

接下来，我们使用iter_swap()语句将“下一个最大数字”与开头交换，既然我们知道该数字是下一个最大值，那么右侧的数字仍然按降序排列，因此为了将其按升序排列，我们只需要使用reverse()。

- flight

---

谢谢您的解释！这个算法叫做字典序排列生成算法。在组合数学中有许多这样的算法，但这是最经典的一个。 - chain ro

这个算法的复杂度是多少？ - user72708

LeetCode有很好的解释，https://leetcode.com/problems/next-permutation/solution/ - bicepjai

我本以为需要看一个YouTube视频才能理解它。但是这个解释太好了……我只看了一遍，就不需要再读一遍（也不需要看YouTube视频）。超级棒的解释！！！ - Abinash Dash

https://www.techiedelight.com/std_next_permutation-overview-implementation/ - tanmoy

Answer 2

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

以下算法将在给定排列后以字典顺序生成下一个排列。它直接修改给定的排列。

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

- TemplateRex

---

据我所知，所有的实现都生成相同的顺序。 - MSalters

Answer 3

Knuth在《计算机程序设计艺术》的第7.2.1.2节和第7.2.1.3节中深入探讨了这个算法及其推广。他将其称为“L算法”——显然它可以追溯到13世纪。

- user755921

---

请问您可以提供这本书的名称吗？ - Grobber

TAOCP = 计算机程序设计艺术 - user755921

Answer 4

这里是使用其他标准库算法的完整实现：

template <typename I, typename C>
    // requires BidirectionalIterator<I> && Compare<C>
bool my_next_permutation(I begin, I end, C comp) {
    auto rbegin = std::make_reverse_iterator(end);
    auto rend = std::make_reverse_iterator(begin);
    auto rsorted_end = std::is_sorted_until(rbegin, rend, comp);
    bool has_more_permutations = rsorted_end != rend;

    if (has_more_permutations) {
        auto rupper_bound = std::upper_bound(
            rbegin, rsorted_end, *rsorted_end, comp);
        std::iter_swap(rsorted_end, rupper_bound);
    }

    std::reverse(rbegin, rsorted_end);
    return has_more_permutations;
}

Demo

- Brian Rodriguez

---

这凸显了良好变量命名和关注点分离的重要性。is_final_permutation 比 begin == end - 1 更具信息性。调用 is_sorted_until/upper_bound 将排列逻辑与这些操作分离，使其更易理解。此外，upper_bound 是二分查找，而 while (!(*i < *--k)); 是线性的，因此更高效。 - jgawrych

@JonathanGawrych 复杂度更好，但在实际应用中不一定更高效。 - TYeung

Answer 5

在cppreference上有一个自解释的可能实现，使用了<algorithm>。

template <class Iterator>
bool next_permutation(Iterator first, Iterator last) {
    if (first == last) return false;
    Iterator i = last;
    if (first == --i) return false;
    while (1) {
        Iterator i1 = i, i2;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2));
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

将内容更改为字典序的下一个排列（原地操作），如果存在则返回true，否则进行排序并返回false。

- Shreevardhan

Answer 6

#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int main() {

    int int_array_11[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
    do {
        copy(begin(int_array_11), end(int_array_11), ostream_iterator<int>(cout, " "));
        cout << endl;
    } while (next_permutation(begin(int_array_11), end(int_array_11)));

    return 0;
}

- Meltrix