解决Leetcode第3470题全排列IV

3470.全排列IV

难度：困难

问题描述：

给你两个整数n和k，一个交替排列是前n个正整数的排列，且任意相邻两个元素不都为奇数或都为偶数。

返回第k个交替排列，并按字典序排序。如果有效的交替排列少于k个，则返回一个空列表。

示例1

输入：n=4,k=6

输出：[3,4,1,2]

解释：

[1,2,3,4]的交替排列按字典序排序后为：

[1,2,3,4]

[1,4,3,2]

[2,1,4,3]

[2,3,4,1]

[3,2,1,4]

[3,4,1,2]←第6个排列

[4,1,2,3]

[4,3,2,1]

由于k=6，我们返回[3,4,1,2]。

示例2

输入：n=3,k=2

输出：[3,2,1]

解释：

[1,2,3]的交替排列按字典序排序后为：

[1,2,3]

[3,2,1]←第2个排列

由于k=2，我们返回[3,2,1]。

示例3

输入：n=2,k=3

输出：[]

解释：

[1,2]的交替排列按字典序排序后为：

[1,2]

[2,1]

只有2个交替排列，但k=3超出了范围。因此，我们返回一个空列表[]。

提示：

1<=n<=100

1<=k<=1015

分析问题：

这个问题关键是要先把1至n共n个数的全排列找出来，然后根据“任意相邻两个元素不都为奇数或都为偶数”的规则生成交替排列，并按字典序排好序，剩下的输出第k个排列就好办了。生成全排列又用到了递归的方法。

程序如下：

#将一个整数插入到一个整数列表中的各个位置，形成一个新的全排列并返回
def one_into_all(a,b):n=len(b)c=[]for i in range(n+1):left=b[:i]right=b[i:]d=left+[a]+rightc.append(d)return c#生成列表a的全排列，并返回
def all_array(a):n=len(a)if n==2:return[[a[0],a[1]],[a[1],a[0]]]elif n==3:return [[a[0],a[1],a[2]],[a[0],a[2],a[1]],[a[1],a[0],a[2]],[a[1],a[2],a[0]],[a[2],a[0],a[1]],[a[2],a[1],a[0]]]else:c=[]b=a[0]for i in all_array(a[1:]):d=one_into_all(b,i)c.extend(d)c.sort()return c#检查一个列表中相邻两个整数是否都为奇数或都为偶数，如果是返回True，否则返回False
def is_odd_or_even(a):n=len(a)for i in range(n-1):if a[i]%2==0 and a[i+1]%2==0 or a[i]%2==1 and a[i+1]%2==1:return Trueelse:return False#主程序之输入部分
n=int(input('pls input n='))
k=int(input('pls input k='))
#根据输入的n值，生成元素为1至n的列表
a=list(range(1,n+1))#从1至n的全排列中去除相邻元素都为奇数或都为偶数的排列，生成交替排列
b=[]
for i in all_array(a):if is_odd_or_even(i):continueelse:b.append(i)#根据k的值，输出第k个排列或输出空列表
n=len(b)
if k<=n:print(f'生成的交替排列中的第{k}个排列为：{b[k-1]}')
else:print([])#将交替排列按一行四个排列的格式输出
k=0
print('生成的交替排列按每行4个元素排列如下：',end=' ')
for i in b:if k%4!=0:print(i,end=' ')else:print()print(i,end=' ')k=k+1

运行实例一

pls input n=4

pls input k=3

生成的交替排列中的第3个排列为：[2, 1, 4, 3]

生成的交替排列按每行4个元素排列如下：

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

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

运行实例二

pls input n=3

pls input k=2

生成的交替排列中的第2个排列为：[3, 2, 1]

生成的交替排列按每行4个元素排列如下：

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

运行实例三

pls input n=2

pls input k=3

生成的交替排列中没有第3个排列，故输出[]

生成的交替排列按每行4个元素排列如下：

[1, 2] [2, 1]

全排列是解决很多问题的关键，探究生成全排列的各种方法应该是必要的。