std::Next_置换实现说明

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (69)

我很好奇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()));
}

我的问题是:它是如何工作的?何谓ijk?在执行的不同部分,他们有什么价值?什么是证明其正确性的草图?

提问于
用户回答回答于

让我们来看看一些排列:

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位数字按降序排列时。

现在让我们回到代码:

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

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

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

在循环的前2行,j是一个元素i是它前面的元素。

然后,如果元素按升序排列,(if (*i < *j))做点什么。

否则,如果整件事是降序的话,if (i == begin)这是最后一次排列。

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

我们现在明白了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()

用户回答回答于

gcc实现按字典顺序生成排列。

下面的算法在给定的置换之后按字典顺序生成下一个置换。它改变了给定的置换位置。

  1. 找到最大的索引k,这样一个k<aK+1。如果不存在这样的指数,则置换是最后的置换。
  2. 找到最大的索引l,这样一个k<aL。由于k+1是这样一个指标,所以l定义得很好,并且满足k<l。
  3. 交换ak带着L。
  4. 从K+1直到并包括最后一个元素an。

扫码关注云+社区

领取腾讯云代金券