题 std :: next_permutation实现说明


我很好奇 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

我的问题是:它是如何工作的?是什么意思 ij 和 k?他们在执行的不同部分有什么价值?什么是正确性证明的草图?

显然,在进入主循环之前,它只检查普通的0或1元素列表情况。在主循环的入口处,我指向最后一个元素(不是一个过去的结尾),并且列表至少是2个元素长。

主循环体内发生了什么?


88
2017-07-14 10:37


起源




答案:


让我们看看一些排列:

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;

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

接下来,我们将“下一个最大的数字”交换到前面 iter_swap() 声明然后因为我们知道数字是下一个最大的数字,我们知道右边的数字仍然是降序,所以要按升序排列,我们只需要 reverse() 它。


142
2017-07-14 11:32



惊人的解释
很好的解释! - XiaJun
感谢您解释代码。 - Abhijeet
谢谢你的解释!调用此算法 以字典顺序生成。有许多这样的算法 Combinatorics,但这是最经典的一个。 - chain ro
这种算法的复杂性是什么? - user72708


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

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

  1. 找到最大的索引k,使得a [k] <a [k + 1]。如果没有这样的指数   存在,排列是最后的排列。
  2. 找到最大的索引l,使得a [k] <a [l]。由于k + 1是这样的指数,因此l是   明确定义并满足k <l。
  3. 用[l]交换[k]。
  4. 将序列从[k + 1]反转到包括最终元素a [n]。

33
2017-07-14 10:56



AFAICT,所有实现都生成相同的顺序。 - MSalters


Knuth深入探讨了该算法及其在7.2.1.2和7.2.1.3节中的概括 计算机程序设计的艺术。他称之为“算法L” - 显然它可以追溯到13世纪。


10
2018-01-22 02:47



你能提一下这本书的名字吗? - Grobber
TAOCP =计算机程序设计的艺术


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

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 next_unsorted = std::is_sorted_until(rbegin, rend, comp);
    bool at_final_permutation = (next_unsorted == rend);
    if (!at_final_permutation) {
        auto next_permutation = std::upper_bound(
            rbegin, next_unsorted, *next_unsorted, comp);
        std::iter_swap(next_unsorted, next_permutation);
    }
    std::reverse(rbegin, next_unsorted);
    return !at_final_permutation;
}

演示


6
2017-09-21 12:36



这强调了良好变量名称和关注点分离的重要性。 is_final_permutation 比信息更丰富 begin == end - 1。调用 is_sorted_until/upper_bound 将置换逻辑与那些操作分开,使这更容易理解。另外,upper_bound是二进制搜索,而 while (!(*i < *--k)); 是线性的,所以这是更高效的。 - Jonathan Gawrych


有一个自我解释的可能的实现 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。


1
2017-09-21 12:58