全排列生成算法:next_permutation

概念

全排列的生成算法有很多种,有递归遍例,也有循环移位法等等。C++/STL中定义的next_permutation和prev_permutation函数则是非常灵活且高效的一种方法,它被广泛的应用于为指定序列生成不同的排列。本文将详细的介绍prev_permutation函数的内部算法。

按照STL文档的描述,next_permutation函数将按字母表顺序生成给定序列的下一个较大的序列,直到整个序列为减序为止。prev_permutation函数与之相反,是生成给定序列的上一个较小的序列。二者原理相同,仅遍例顺序相反,这里仅以next_permutation为例介绍算法。

下文内容都基于一个假设,即序列中不存在相同元素。对序列大小的比较做出定义:两个长度相同的序列,从两者的第一个元素开始向后比较,直到出现一个不同元素(也可能就是第它们的第一个元素),该元素较大的序列为大,反之序列为小;若一直到最后一个元素都相同,那么两个序列相等。

设当前序列为pn,下一个较大的序列为pn+1,那么不存在pm,使得pn < pm < pn+1。

问题

给定任意非空序列,生成下一个较大或较小的序列。

数学推导

根据上述概念易知,对于一个任意序列,最小的序列是增序,最大的序列为减序。那么给定一个pn要如何才能生成pn+1呢?先来看下面的例子:

我们用<a1 a2 ... am>来表示m个数的一种序列。设序列pn=<3 6 4 2>,根据定义可算得下一个序列pn+1=<4 2 3 6>。观察pn可以发现,其子序列<6 4 2>已经为减序,那么这个子序列不可能通过交换元素位置得出更大的序列了,因此必须移动最高位3(即a1)的位置,且要在子序列<6 4 2>中找一个数来取代3的位置。子序列<6 4 2>中6和4都比3大,但6大于4。如果用6去替换3得到的序列一定会大于4替换3得到的序列,因此只能选4。将4和3的位置对调后形成排列<4 6 3 2>。对调后得到的子序列<6 3 2>仍保持减序,即这3个数能够生成的最大的一种序列。而4是第1次作为首位的,需要右边的子序列最小,因此4右边的子序列应为<2 3 6>,这样就得到了正确的一个序列pn+1=<4 2 3 6>。

下面归纳分析该过程。假设一个有m个元素的序列pn,其下一个较大序列为pn+1。

1) 若pn最右端的2个元素构成一个增序子序列,那么直接反转这2个元素使该子序列成为减序,即可得到pn+1。

2) 若pn最右端一共有连续的s个元素构成一个减序子序列,令i = m - s,则有pn(i) < pn(i+1),其中pn(i)表示排列pn的第i个元素。例如pn=<1 2 5 4 3>,那么pn的右端最多有3个元素构成一个减序子集<5 4 3>,i=5-3=2,则有pn(i)=2 < 5=pn(i+1)。因此若将pn(i)和其右边的子集s {pn(i+1), pn(i+2), ..., pn(m)}中任意一个元素调换必能得到一个较大的序列(不一定是下一个)。要保证是下一个较大的序列,必须保持pn(i)左边的元素不动,并在子集s {pn(i+1), pn(i+2), ..., pn(m)}中找出所有比pn(i)大的元素中最小的一个pn(j),即不存在pn(k) ∈ s且pn(i) < pn(k) < pn(j),然后将二者调换位置。现在只要使新子集{pn(i+1), pn(i+2), ..., pn(i), ...,pn(m)}成为最小序列即得到pn+1。注意到新子集仍保持减序,那么此时直接将其反转即可得到pn+1 {pn(1), pn(2), ..., pn(j), pn(m), pn(m-1), ..., pn(i), ..., pn(i+2), pn(i+1)}。

复杂度

最好的情况为pn的最右边的2个元素构成一个最小的增序子集,交换次数为1,复杂度为O(1),最差的情况为1个元素最小,而右面的所有元素构成减序子集,这样需要先将第1个元素换到最右,然后反转右面的所有元素。交换次数为1+(n-1)/2,复杂度为O(n)。因为各种排列等可能出现,所以平均复杂度即为O(n)。

扩展

1. 能否直接算出集合{1, 2, ..., m}的第n个排列?

设某个集合{a1, a2, ..., am}(a1<a2<...<am)构成的某种序列pn,基于以上分析易证得:若as<at,那么将as作为第1个元素的所有序列一定都小于at作为第1个元素的任意序列。同理可证得:第1个元素确定后,剩下的元素中若as'<at',那么将as'作为第2个元素的所有序列一定都小于作为第2个元素的任意序列。例如4个数的集合{2, 3, 4, 6}构成的序列中,以3作为第1个元素的序列一定小于以4或6作为第1个元素的序列;3作为第1个元素的前题下,2作为第2个元素的序列一定小于以4或6作为第2个元素的序列。

推广可知,在确定前i(i<n)个元素后,在剩下的m-i=s个元素的集合{aq1, aq2, ..., aq3}(aq1<aq2<...<aqm)中,以aqj作为第i+1个元素的序列一定小于以aqj+1作为第i+1个元素的序列。由此可知:在确定前i个元素后,一共可生成s!种连续大小的序列。

根据以上分析,对于给定的n(必有n<=m!)可以从第1位开始向右逐位地确定每一位元素。在第1位不变的前题下,后面m-1位一共可以生成(m-1)!中连续大小的序列。若n>(m-1)!,则第1位不会是a1,n中可以容纳x个(m-1)!即代表第1位是ax。在确定第1位后,将第1位从原集合中删除,得到新的集合{aq1, aq2, ..., aq3}(aq1<aq2<...<aqm),然后令n1=n-x(m-1)!,求这m-1个数中生成的第n1个序列的第1位。

举例说明:如7个数的集合为{1, 2, 3, 4, 5, 6, 7},要求出第n=1654个排列。

(1654 / 6!)取整得2,确定第1位为3,剩下的6个数{1, 2, 4, 5, 6, 7},求第1654 % 6!=214个序列;

(214 / 5!)取整得1,确定第2位为2,剩下5个数{1, 4, 5, 6, 7},求第214 % 5!=94个序列;

(94 / 4!)取整得3,确定第3位为6,剩下4个数{1, 4, 5, 7},求第94 % 4!=22个序列;

(22 / 3!)取整得3,确定第4位为7,剩下3个数{1, 4, 5},求第22 % 3!=4个序列;

(4 / 2!)得2,确定第5为5,剩下2个数{1, 4};由于4 % 2!=0,故第6位和第7位为增序<1 4>;

因此所有排列为:3267514。

2. 给定一种排列,如何算出这是第几个排列呢?

和前一个问题的推导过程相反。例如3267514:

后6位的全排列为6!,3为{1, 2, 3 ,4 , 5, 6, 7}中第2个元素(从0开始计数),故2*720=1440;

后5位的全排列为5!,2为{1, 2, 4, 5, 6, 7}中第1个元素,故1*5!=120;

后4位的全排列为4!,6为{1, 4, 5, 6, 7}中第3个元素,故3*4!=72;

后3位的全排列为3!,7为{1, 4, 5, 7}中第3个元素,故3*3!=18;

后2位的全排列为2!,5为{1, 4, 5}中第2个元素,故2*2!=4;

最后2位为增序,因此计数0,求和得:1440+120+72+18+4=1654

C++/STL实现

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
//主函数,算法详见相关说明
int main(void) {
    //循环处理输入的每一个字符串
    for (string str; cin >> str;) {
        if (str.empty()) {
            continue;
        }
        //如果字符串只有1个字符,则直接输出结束
        if (str.length() <= 1) {
            cout << "No more Permutation" << endl;
        }
        //iPivot为右边最大减序子集左边相邻的一个元素
        string::iterator iPivot = str.end(), iNewHead;
        //查找右边最大的减序子集
        for (--iPivot; iPivot != str.begin(); --iPivot) {
            if (*(iPivot - 1) <= *iPivot ) {
                break;
            }
        }
        //如果整个序列都为减序,则重排结束。
        if (iPivot == str.begin()) {
            cout << "No more Permutation" << endl;
        }
        //iPivot指向子集左边相邻的一个元素
        iPivot--;
        //iNewHead为仅比iPivot大的元素,在右侧减序子集中寻找
        for (iNewHead = iPivot + 1; iNewHead != str.end(); ++iNewHead) {
            if (*iNewHead < *iPivot) {
                break;
            }
        }
        //交换iPivot和iNewHead的值,但不改变它们的指向
        iter_swap(iPivot, --iNewHead);
        //反转右侧减序子集,使之成为最小的增序子集
        reverse(iPivot + 1, str.end());
        //本轮重排完成,输出结果
        cout << str << endl;
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

Leetcode|Find K Closest Elements

01 — 题目 Given a sorted array, two integers k and x, find the k closest elements ...

3654
来自专栏Python攻城狮

科学计算工具Numpy1.ndarray的创建与数据类型2.ndarray的矩阵运算ndarray的索引与切片3.ndarray的元素处理元素判断函数元素去重排序函数4.2016年美国总统大选民意调查

Numpy:提供了一个在Python中做科学计算的基础库,重在数值计算,主要用于多维数组(矩阵)处理的库。用来存储和处理大型矩阵,比Python自身的嵌套列表结...

1853
来自专栏Leetcode名企之路

【Leetcode】81. 搜索旋转排序数组 II

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

1552
来自专栏mathor

Xor(滴滴笔试题)

 给出一个数组,问最多有多少个不重叠的非空区间,使得每个区间内的数字的xor都等于0。

751
来自专栏Python绿色通道

Numpy归纳整理

说明本文主要是关于Numpy的一些总结,包括他们的一些运算公式,我整理一下方便日后查阅公式!

1312
来自专栏程序生活

连续子数组的最大和

题目1 连续子数组的最大和 描述: 输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度...

2955
来自专栏kalifaの日々

线段树 BIT 求冒泡排序的交换次数

线段树特别适合与区间相关的运算,比如MRQ(minimum range query)求一段区间内的最小值。 BIT可以看作是压缩了的线段树,由于(某类)线段树...

4148
来自专栏用户2442861的专栏

桶排序

http://blog.csdn.net/houapple/article/details/6480100

1954
来自专栏Python小屋

Python高级数组处理模块numpy用法精要

numpy是Python的高级数组处理扩展库,提供了Python中没有的数组对象,支持N维数组运算、处理大型矩阵、成熟的广播函数库、矢量运算、线性代数、傅里叶变...

4027
来自专栏数据结构与算法

P3391 【模板】文艺平衡树(Splay)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

4117

扫码关注云+社区