如何生成列表的所有排列?例如:

permutations([])
[]

permutations([1])
[1]

permutations([1, 2])
[1, 2]
[2, 1]

permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

当前回答

def permutation(word, first_char=None):
    if word == None or len(word) == 0: return []
    if len(word) == 1: return [word]

    result = []
    first_char = word[0]
    for sub_word in permutation(word[1:], first_char):
        result += insert(first_char, sub_word)
    return sorted(result)

def insert(ch, sub_word):
    arr = [ch + sub_word]
    for i in range(len(sub_word)):
        arr.append(sub_word[i:] + ch + sub_word[:i])
    return arr


assert permutation(None) == []
assert permutation('') == []
assert permutation('1')  == ['1']
assert permutation('12') == ['12', '21']

print permutation('abc')

输出:['abc','acb','bac','bca','cab','cba']

其他回答

使用计数器

from collections import Counter

def permutations(nums):
    ans = [[]]
    cache = Counter(nums)

    for idx, x in enumerate(nums):
        result = []
        for items in ans:
            cache1 = Counter(items)
            for id, n in enumerate(nums):
                if cache[n] != cache1[n] and items + [n] not in result:
                    result.append(items + [n])

        ans = result
    return ans
permutations([1, 2, 2])
> [[1, 2, 2], [2, 1, 2], [2, 2, 1]]

为了节省您可能的搜索和实验时间,下面是Python中的非递归置换解决方案,它也适用于Numba(从0.41版开始):

@numba.njit()
def permutations(A, k):
    r = [[i for i in range(0)]]
    for i in range(k):
        r = [[a] + b for a in A for b in r if (a in b)==False]
    return r
permutations([1,2,3],3)
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

要给人留下绩效印象:

%timeit permutations(np.arange(5),5)

243 µs ± 11.1 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
time: 406 ms

%timeit list(itertools.permutations(np.arange(5),5))
15.9 µs ± 8.61 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
time: 12.9 s

因此,只有在必须从njit函数调用它时才使用此版本,否则更倾向于itertools实现。

用递归求解,遍历元素,取第i个元素,然后问自己:“其余项目的排列是什么”,直到没有更多的元素。

我在这里解释了解决方案:https://www.youtube.com/watch?v=_7GE7psS2b4

class Solution:
    def permute(self,nums:List[int])->List[List[int]]:
        res=[]
        def dfs(nums,path):
            if len(nums)==0:
                res.append(path)
            for i in range(len(nums)):
                dfs(nums[:i]+nums[i+1:],path+[nums[i]])
        dfs(nums,[])
        return res

首先,导入itertools:

import itertools

排列(顺序重要):

print(list(itertools.permutations([1,2,3,4], 2)))

[(1, 2), (1, 3), (1, 4),
(2, 1), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 4),
(4, 1), (4, 2), (4, 3)]

组合(顺序无关紧要):

print(list(itertools.combinations('123', 2)))

[('1', '2'), ('1', '3'), ('2', '3')]

笛卡尔积(具有多个可迭代项):

print(list(itertools.product([1,2,3], [4,5,6])))

[(1, 4), (1, 5), (1, 6),
(2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6)]

笛卡尔积(具有一个可迭代的和自身):

print(list(itertools.product([1,2], repeat=3)))

[(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]
def permutate(l):
    for i, x in enumerate(l):
        for y in l[i + 1:]:
            yield x, y


if __name__ == '__main__':
    print(list(permutate(list('abcd'))))
    print(list(permutate([1, 2, 3, 4])))

#[('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]
#[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]