递归生成全排列

从最开始的问题来说吧:

给出 [1,2,3....n] 的全排列 这个也是很简单直接的问题,n个数的全排列就是一个数加上其他n-1个数的全排列,这样用递归就很容易得到结果
1
2
3
4
5
6
7
def innerPerm(li,start,ret):
	if start == len(li)-1:
		ret.append(copy(li))
	for i in range(start,len(li)):
		swap(li,start,i)
		innerPerm(li,start+1,ret)
		swap(li,start,i)

[1,2,3]的返回值是 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

分析下结果,前两个是固定1,用2,3做全排,然后固定2,用1,3做全排,最后固定3,以1,2做全排,和预想的一样。

#####顺序全排列

给出 [1,2,3....n] 的全排列,且结果为递增序

如何生成递增序,还是从最简单的看起:

[1,2,3,4] 的生成过程 : 首先是把4移到3前面 --> [1,2,4,3] 然后把3移到2前面 --> [1,3,2,4] ..-->[1,3,4,2] --> [1,4,3,2] |  --> [2,1,3,4] ... --> [4,3,2,1]

我们找到重要的点,那就是[1,4,3,2] 整个问题可以分解为 把 1,2,3,4 依次放到第一位,其他的数来顺序排列,得到的结果就是[1,2,3,4]的顺序全排列。 那么怎么找呢? 这里给出一个方法:

  • 从最后一个数向前找,满足 a[i] < a[i+1]的第一个数,如果找不到,排列就结束,如果找到,进入下面
  • 从最后一个数向前走,找到第一满足a[j] > a[i]的数,交换a[i]a[j]
  • a[i+1]到最后的数反序

问题

ok,perm的随机序和递增序的两种生成方法都有了,所以基本上所以关于perm的问题都可以解了,下面是一个例子:

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

你可以用上面的方法解决它吗?可以不生成k个排列吗?

引申

给定一个list,其中每个元素都是一个非空且元素不重复的list,例如 [ [1,2,3], [4,5], [1,3,8] ],在其中没个list上拿出一个数就可以组成一个新的list,例如都取第一个,那就是[1,4,1],那么你能把所以这样的list都求出来吗?

这里就不给出方法了,hint : 你怎么数数的,遇10进位,如果不是10呢?