「LeetCode每日一题」—— 46. 全排列
46. 全排列
链接:https://leetcode-cn.com/problems/permutations/
难度:中等
题目
点击原文链接跳转查看题目
思路
这题算是一个基础题,给的是没有重复的序列。让我来做,我会直接用库函数来实现。
代码如下,调用itertools.permutations函数。
def permute(self, nums: List[int]) -> List[List[int]]:
return list(itertools.permutations(nums))
今天想深入聊下permutations函数的实现。
itertools.permutations(iterable, r=None)
接受两个参数
- iterable 可迭代对象
- r 默认为iterable的长度,生成全排列,指定代表生成的长度
官方给出的permutations实现逻辑如下:
def permutations(iterable, r=None):
# permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
# permutations(range(3)) --> 012 021 102 120 201 210
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = list(range(n))
cycles = list(range(n, n-r, -1))
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
我们拿题目中的[1,2,3]代入,indices=[0,1,2], cycles为[3,2,1],然后进行枚举。
先写1开头的全排列:[1, 2, 3], [1, 3, 2]
再写以 2 开头的全排列,[2, 1, 3], [2, 3, 1]
最后写以 3 开头的全排列,[3, 1, 2], [3, 2, 1]
在代码中,yield tuple(pool[i] for i in indices[:r]) 这行先把不需要改变的返回,然后根据顺序,
indices[i], indices[-j] = indices[-j], indices[i]通过交换得到所有的全排列。
permutations函数其实可以用product函数,
product的函数是返回输入对象的笛卡尔积,代码如下:
def permutations(iterable, r=None):
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
for indices in product(range(n), repeat=r):
if len(set(indices)) == r:
yield tuple(pool[i] for i in indices)
方案代码
库函数:
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return list(itertools.permutations(nums))
原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/352.html
您必须登录才能发表评论。