前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >编程小知识之生成排列

编程小知识之生成排列

作者头像
用户2615200
发布2019-05-13 19:22:09
3350
发布2019-05-13 19:22:09
举报
文章被收录于专栏:tkokof 的技术,小趣及杂念

本文简述了两种生成排列的方法

生成排列的方法不少,一种经典的方法就是采用递归,假设我们需要求解 1 ~ n 的所有排列,那么我们假设已经求解了 1 ~ n - 1 的所有排列,然后对于求解出的每一种排列(1 ~ n - 1 的一种排列),我们将 n 放置于该排列中可能的 n 个空位上,即可完成 1 ~ n 的排列求解.

说的有些抽象,举个实际的例子:

假设我们要求解 1 ~ 3 这三个数字的所有排列,并且我们已经求解出了 1 ~ 2 的所有排列,求解出的排列如下所示:

1,22,1 \begin{aligned} 1, 2 \\ 2, 1 \end{aligned} 1,22,1​

其中每个排列都有 3 个空位:

empty 1,empty 2 emptyempty 2,empty 1 empty \begin{aligned} \boxed{empty}\ 1, \boxed{empty}\ 2\ \boxed{empty} \\ \boxed{empty}\ 2, \boxed{empty}\ 1\ \boxed{empty} \end{aligned} empty​ 1,empty​ 2 empty​empty​ 2,empty​ 1 empty​​

我们将 3 依序填入每个空位即可完成 1 ~ 3 排列的求解:

3,1,21,3,21,2,33,2,12,3,12,1,3 \begin{aligned} \boxed{3}, 1, 2 \\ 1, \boxed{3}, 2 \\ 1, 2, \boxed{3} \\ \boxed{3}, 2, 1 \\ 2, \boxed{3}, 1 \\ 2, 1, \boxed{3} \end{aligned} 3​,1,21,3​,21,2,3​3​,2,12,3​,12,1,3​​


求解排列的另外一种思路,就是给每个可能的排列规定一个大小次序,仍然拿 1 ~ 3 的排列举例,我们可以规定:

1,2,3&lt;1,3,2&lt;2,1,3&lt;2,3,1&lt;3,1,2&lt;3,2,1 \begin{aligned} &amp; 1, 2, 3 &lt; 1, 3, 2 &lt; 2, 1, 3 &lt; 2, 3, 1 &lt; 3, 1, 2 &lt; 3, 2, 1 \end{aligned} ​1,2,3<1,3,2<2,1,3<2,3,1<3,1,2<3,2,1​

即排列 1,2,31, 2, 31,2,3 最小,排列 3,2,13, 2, 13,2,1 最大,扩展到 1 ~ n 的排列来讲,如果给定一个现有排列(初始即为 1 ~ n 的顺序排列: 1,2,3,...,n1, 2, 3, ..., n1,2,3,...,n),我们生成大于该排列的最小排列,依次进行下去便可生成所有排列.

那么如何生成大于该排列的最小排列呢?方法如下:

假设当前给定的排列为 a1,a2,a3,a4,...ana_1, a_2, a_3, a_4, ... a_na1​,a2​,a3​,a4​,...an​

  1. 从后(ana_nan​ 开始)往前查找,找到第一个满足 ai&lt;ai+1a_i &lt; a_{i+1}ai​<ai+1​ 的元素
  2. 再次从后(ana_nan​ 开始)往前查找,找到第一个满足 aj&gt;aia_j &gt; a_iaj​>ai​ 的元素(aia_iai​ 为上一步骤的结果元素)
  3. 交换 aia_iai​ 和 aja_jaj​
  4. 将 ai+1a_{i+1}ai+1​ 至 ana_nan​ 的元素重新排序

(这里我们只给出了过程描述,更多细节大家可以参考相关书籍)

有了算法步骤,我们便可以进行代码实现了,过程中有两点值得一提:

  • 如果第 1 步中找不到满足 ai&lt;ai+1a_i &lt; a_{i+1}ai​<ai+1​ 的元素怎么办?这种情况会出现在元素逆序的排列中(譬如排列: 3,2,13, 2, 13,2,1),处理方法很简单,我们直接跳过 2, 3 步骤,直接执行第 4 步中的排序即可,由于此时元素是逆序的,我们直接反转(reverse)排列元素即可完成排序(排序之后排列又回到了"原点").
  • 如果正常进行了 1, 2, 3 这三个步骤,第 4 步中的重新排序操作我们仍然可以通过直接反转(reverse)排列元素来完成:

考虑第 1 步骤的操作,当找到目标元素 aia_iai​ 时,我们可知以下元素关系:

ai&lt;ai+1&gt;ai+2&gt;ai+3&gt;...&gt;an a_i &lt; a_{i+1} &gt; a_{i+2} &gt; a_{i+3} &gt; ... &gt; a_n ai​<ai+1​>ai+2​>ai+3​>...>an​

考虑第 2 步骤的操作,当找到目标元素 aja_jaj​ 时,我们可知以下元素关系:

...&gt;aj−1&gt;aj&gt;ai&gt;aj+1&gt;... ... &gt; a_{j-1} &gt; a_j &gt; a_i &gt; a_{j+1} &gt; ... ...>aj−1​>aj​>ai​>aj+1​>...

第 3 步骤我们执行了 aia_iai​ 与 aja_jaj​ 的交换,根据之前的元素关系,我们可知:

aj&lt;ai+1&gt;ai+2&gt;...&gt;aj−1&gt;ai&gt;aj+1&gt;...&gt;an \boxed{a_j} &lt; a_{i+1} &gt; a_{i+2} &gt; ... &gt; a_{j-1} &gt; \boxed{a_i} &gt; a_{j+1} &gt; ... &gt; a_n aj​​<ai+1​>ai+2​>...>aj−1​>ai​​>aj+1​>...>an​

所以 ai+1a_{i+1}ai+1​ 至 ana_nan​ 间的元素在 1, 2, 3 步骤之后仍然是逆序关系,自然我们就可以通过直接反转(reverse)这些元素来对它们进行排序了,最终的示例代码如下:

代码语言:javascript
复制
// C#
public static List<int> NextPermutation(List<int> curPermutation)
{
    var swapIndex = -1;

    var index = curPermutation.Count - 2;
    while (index >= 0)
    {
        if (curPermutation[index] < curPermutation[index + 1])
        {
            swapIndex = index;
            break;
        }
        --index;
    }

    if (swapIndex >= 0)
    {
        // valid swap index, swap with the rest smallest big number
        var swapElement = curPermutation[swapIndex];
        var smallIndex = swapIndex + 1;
        for (int i = curPermutation.Count - 1; i >= swapIndex + 2; --i)
        {
            if (curPermutation[i] > swapElement)
            {
                smallIndex = i;
                break;
            }
        }

        // do swap
        curPermutation[swapIndex] = curPermutation[smallIndex];
        curPermutation[smallIndex] = swapElement;
    }

    // do sort
    var startIndex = swapIndex + 1;
    var endIndex = curPermutation.Count - 1;
    while (endIndex > startIndex)
    {
        var temp = curPermutation[startIndex];
        curPermutation[startIndex] = curPermutation[endIndex];
        curPermutation[endIndex] = temp;
        ++startIndex;
        --endIndex;
    }

    return curPermutation;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年04月29日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档