「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))

「LeetCode每日一题」—— 46. 全排列

46. 全排列

题目

思路

方案代码

相关

相关推荐

`46. 全排列`

`题目`

`思路`