算法:15.全排列

https://www.lintcode.com/problem/permutations/description

描述

给定一个数字列表,返回其所有可能的排列。

你可以假设没有重复数字。

样例

给出一个列表,其全排列为:

挑战

使用递归和非递归分别解决。

思路递归算法就是解决一个问题时,可以先解决一个更小规模的问题(递归前进),然后根绝小规模问题的结果计算得出更大规模问题的结果(递归返回),当问题小到一定规模的情况下就不需要再分了,可以直接求解(递归边界)。排列的定义是从N个数中取出M个数按照一定顺序摆放成一行,就叫做N个数的一个M个数的排列,当两个排列的顺序与数字都相同时,视为同一个排列。例如:从【3,2,1】三个数中取出两个数的排列有【3,2】,【3,1】,【2,1】,【1,2】,【1,3】,【2,3】共六个排列。从【3,2,2】三个数中取出两个数的排列有【3,2】,【2,2】,【2,3】共三个排列,第一个数字取3,第二个数字不管是取第一个2还是第二个2,排列的结果都是【3,2】,视为同一个排列。全排列定义是从N个数中取出N个数的排列的集合称为全排列。递归的方法解决,N个数字的全部排列列表就是 [[一个数的排列],[两个数的排列],...[M个数的排列],...[N个数的排列]]。对于M个数字的排列,就是先求出 M-1 个数的排列集合,然后对于集合中的每个排列,如果排列的长度是length,那么将第M个数插入到排列中的第0,1,...j,...length 的位置上形成M个数的全部排列。

当数字列表是【1,2,3】时的求解过程。

当N等于1的时候,数字列表是【1】,返回的排列列表是 [ [1] ]。

当N等于2的时候,数字列表是【1,2】,遍历N等于1时返回的列表 [ [1] ],由于列表中只有一个排列 [1],长度是1,那么将第二个数字2插入到 [1] 的0,1位置形成新的排列 [2,1], [1,2]。那么当N等于2时的全排列就是 [ [2,1],[1,2] ]。

当N等于3的时候,就是将第三个数字3插入到 [[2,1],[1,2]] 中的每个排列的相应位置,最后的排列列表就是 [[3,2,1],[2,3,1],[2,1,3],[3,1,2],[1,3,2],[1,2,3]]。

递归实现如下:

优化调整一下,删除复制数组:

非递归版本:

非递归版本的思路与递归版本是不同的。非递归版本的思路是,先列出第一个排列,然后通过交换已有排列中数字的位置来产生新的排列。

例如数字列表是 [1,2,3,4],那么第一个排列就是原始的顺序,将 [1, 2, 3, 4] 作为第一个排列。然后从倒数第二个数字开始,也就是从3开始,将这个数字从当前的位置挪到最后,没挪动一个位置就产生一个排列。

初始的排列是 :

[ [1, 2, 3, 4] ]

挪动3产生的排列是:

[1, 2, 4, 3]

3是倒数第二个数字,往后只能挪动一个位置,所以只产生一个新的排列。那么现在新的排列列表就是

[ [1, 2, 3, 4], [1, 2, 4, 3]]

挪动倒数第三个数字产生的新的排列是:

[1, 3, 2, 4] , [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2] 。

这是后得到的全部的排列就是:

[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2]]

其实质思想就是从后往前遍历各个数字。每次得到的全部排列,其最后面的m个个数字是m个数的一个全排列,然后将nums.length-m-1位置的数字插入到后面m个数字全排列的各个位置上形成新的m+1个数字的全排列。

第一次得到的排列列表是[ [1, 2, 3, 4] ] ,后面的 4 就是4的,全排列。

第二次得到的排列列表是 [ [1, 2,3, 4], [1, 2,4, 3]] ,所有排列的后两位组合起来就是后面两个数字 3 和 4 的一个全排列。

第三次得到的排列列表是 [[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,3,4的一个全排列。

小结

非递归操作在列表的操作中使用了 remove操作,对于ArrayList来说,remove会产生数组拷贝操作,效率较低。

实际中测试了使用LinkedList,对于输入 [1,2,3,4,5,6,7,8,9] 来说,ArrayList依然表现的比LinkedList要快,可能是数据量还是太小吧。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180721G1GPPS00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券