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个元素长.

主循环体内发生了什么？

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;

好吧,因为右边的东西是降序的,要找到"下一个最大的数字",我们只需要从最后进行迭代,我们在前3行代码中看到.

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

Answer 2

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

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

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

Answer 3

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

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 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;
}

演示