next_permutation原理剖析

最近刷leetcode的时候遇见next permutation这道题,感觉挺有意思的一个题目,递归的方法是较简单并且容易想到的,在网上搜了其余的解法,就是std::next_permutation非递归解法,但是让人不是很舒服的就是关于原理的部分,千篇一律的都是摘抄《STL源码剖析》,也就是这样的。

在当前序列中,从尾端往前寻找两个相邻元素,前一个记为*i,后一个记为*ii,并且满足*i < *ii。然后再从尾端寻找另一个元素*j,如果满足*i < *j,即将第i个元素与第j个元素对调,并将第ii个元素之后(包括ii)的所有元素颠倒排序,即求出下一个序列了。

想必有点C++功底的人都能看明白源码是这么个意思,但是这能算是原理么,这至多算是实现吧。相比之下老外就严谨多了,我找到了一篇文章,防止丢失,我保存在这里。http://blog.csdn.net/qq575787460/article/details/41206601,其中图片资源已经没了。看了这篇文章之后,我豁然开朗,在佩服老外严谨的态度之余,也把自己的理解纪律下来,希望能够帮助到一些人。

首先,关于什么是全排列不做解释。如果一个排列为A,下一个排列为A_NEXT,那么A_NEXT一定与A有尽可能长的公共前缀。

看具体例子,一个排列为124653,如何找到它的下一个排列,因为下一个排列一定与124653有尽可能长的前缀,所以,脑洞大开一下,从后面往前看这个序列,如果后面的若干个数字有下一个排列,问题就得到了解决。

第一步:找最后面1个数字的下一个全排列。

124653,显然最后1个数字3不具有下一个全排列。

第二步:找最后面2个数字的下一个全排列。

124653,显然最后2个数字53不具有下一个全排列。

第三步:找最后面3个数字的下一个全排列。

124653,显然最后3个数字653不具有下一个全排列。

------插曲:到这里相信大家已经看出来,如果一个序列是递减的,那么它不具有下一个排列。

第四步:找最后面4个数字的下一个全排列。

124653,我们发现显然最后4个数字4653具有下一个全排列。因为它不是递减的,例如6453,5643这些排列都在4653的后面。

我们总结上面的操作,并总结出重复上面操作的两种终止情况:

1:从后向前比较相邻的两个元素,直到前一个元素小于后一个元素,停止

2:如果已经没有了前一个元素,则说明这个排列是递减的,所以这个排列是没有下一个排列的。

124653这个排列终止情况是上面介绍的第一种,从后向前比较相邻的2个元素,遇到4<6的情况停止。

并且我们可以知道:

1:124653和它的下一个排列的公共前缀为12(因为4653存在下一个排列,所以前面的数字12保持不变)

2:4后面的元素是递减的(上面介绍的终止条件是前一个元素小于后一个元素,这里是4<6)

现在,我们开始考虑如何找到4653的下个排列,首先明确4后面的几个数字中至少有一个大于4.

4肯定要和653这3个数字中大于4的数字中(6,5)的某一个进行交换。这里就是4要和6,5中的某一个交换,很明显要和5交换,如果找到这样的元素呢,因为我们知道4后面的元素是递减的,所以在653中从后面往前查找,找到第一个大于4的数字,这就是需要和4进行交换的数字。这里我们找到了5,交换之后得到的临时序列为5643.,交换后得到的643也是一个递减序列。

所以得到的4653的下一个临时序列为5643,但是既然前面数字变大了(4653--->5643),后面的自然要变为升序才行,变换5643得到5346.

所以124653的下一个序列为125643.

时间: 09-19

next_permutation原理剖析的相关文章

HTTPS 原理剖析与项目场景

最近手头有两个项目,XX导航和XX产业平台,都需要使用HTTPS协议,因此,这次对HTTPS协议做一次整理与分享. 为什么使用HTTPS HTTP 协议,本身是明文传输的,没有经过任何安全处理.那么这个时候就很容易在传输过程中被中间者窃听.篡改.冒充等风险.这里提到的中间者主要指一些网络节点,是用户数据在浏览器和服务器中间传输必须要经过的节点,比如 WIFI 热点,路由器,防火墙,反向代理,缓存服务器等. HTTP 协议,中间者可以窃听隐私,使用户的敏感数据暴露无遗:篡改网页,例如往页面插的广告

MapReduce/Hbase进阶提升(原理剖析、实战演练)

什么是MapReduce? MapReduce是一种编程模型,用于大规模数据集(大于1TB)的并行运算.概念"Map(映射)"和"Reduce(归约)",和他们的主要思想,都是从函数式编程语言里借来的,还有从矢量编程语言里借来的特性.他极大地方便了编程人员在不会分布式并行编程的情况下,将自己的程序运行在分布式系统上. 当前的软件实现是指定一个Map(映射)函数,用来把一组键值对映射成一组新的键值对,指定并发的Reduce(归约)函数,用来保证所有映射的键值对中的每一

EventBus的使用和原理剖析

尊重原创:http://blog.csdn.net/yuanzeyao/article/details/38174537 代码下载:http://download.csdn.net/detail/yuanzeyao2008/7684041 在编程过程中,当我们想通知其他组件某些事情发生时,我们通常使用观察者模式,正式因为观察者模式非常常见,所以在jdk1.5中已经帮助我们实现了观察者模式,我们只需要简单的继承一些类就可以快速使用观察者模式,在Android中也有一个类似功能的开源库EventBu

清除浮动的原理剖析

常用的清除浮动的几种方法总结下: 1,手动设置一个标签(在浮动元素下方),然后对其设置clear属性 2,给浮动元素设置 :after伪类,创建块元素,设置clear属性 3,给父元素设置浮动 4,给父元素设置overflow设置非visible值(auto,hidden) 5,给父元素的display设置为table-cell 7,在ie6,7中,设置zoom或者width,height来触发haslayout,使父元素包含浮动元素 原理剖析: 1,2方法之所以可以成功,是因为了clear属性

Koa框架实践与中间件原理剖析

Koa框架实践与中间件原理剖析 最近尝试用了一下Koa,并在此记录一下使用心得. 注意:本文是以读者已经了解Generator和Promise为前提在写的,因为单单Generator和Promise都能够写一篇博文来讲解介绍了,所以就不在这里赘述.网上资料很多,可以自行查阅. Koa是Express原班人马打造的一个更小,基于nodejs平台的下一代web开发框架.Koa的精妙之处就在于其使用generator和promise,实现了一种更为有趣的中间件系统,Koa的中间件是一系列generat

图像处理之基础---二维卷积运算原理剖析

卷积运算(Convolution)是通过两个函数f 和g 生成第三个函数的一种数学算子,表示函数f 与经过翻转和平移与g 的重叠部分的累积.如果将参加卷积的一个函数看作区间的指示函数,卷积还可以被看作是“滑动平均”的推广.假设: f(x),g(x)是R1上的两个可积函数,并且积分是存在的.这样,随着 x 的不同取值,这个积分就定义了一个新函数h(x),称为函数f 与g 的卷积,记为h(x)=(f*g)(x). 两个向量卷积,说白了就是多项式乘法.下面用个矩阵例子说明其工作原理: a和d的卷积就是

ASP.NET Core 运行原理剖析2:Startup 和 Middleware(中间件)

小分享:我有几张阿里云优惠券,用券购买或者升级阿里云相应产品最多可以优惠五折!领券地址:https://promotion.aliyun.com/ntms/act/ambassador/sharetouser.html?userCode=ohmepe03 ASP.NET Core 运行原理剖析2:Startup 和 Middleware(中间件) Startup Class 1.Startup Constructor(构造函数) 2.ConfigureServices 3.Configure方法

简单代码生成器原理剖析(二)

上篇<简单代码生成器原理剖析(一)>分 析了代码生成器的原理,查询数据库系统视 图:INFORMATION_SCHEMA.TABLES. INFORMATION_SCHEMA.COLUMNS  可以获得数据库中表.列的相关信息,再运用StringBuilder类的其AppendLine方法追加字符串,最后早运用 File.WriteAllText方法将字符串写入文件. 第二版代码生成器在第一版的基础上扩展了以下功能: 使用了部分类(partial):当使用大项目或自动生成的代码(如由 Wind

Java中的静态代理、通用动态代理类以及原理剖析

代理模式和静态代理 在开发中,代理模式是常用的模式之一,一般来说我们使用的代理模式基本上都是静态代理,实现模式大致如下 : 我们以网络代理为例,简单演示一下静态代理的实现 : // 网络接口 interface Network { public void surfTheInternet(); public void gotoFacebook(); } // 普通网络 class CommonNetwork implements Network { @Override public void su