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

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 permuteArray (arr):

    arraySize = len(arr)

    permutedList = []

    if arraySize == 1:
        return [arr]

    i = 0

    for item in arr:

        for elem in permuteArray(arr[:i] + arr[i + 1:]):
            permutedList.append([item] + elem)

        i = i + 1    

    return permutedList

我不打算在一个新的行中穷尽所有的可能性,以使它有点独特。

其他回答

这是受Haskell实现使用列表理解的启发:

def permutation(list):
    if len(list) == 0:
        return [[]]
    else:
        return [[x] + ys for x in list for ys in permutation(delete(list, x))]

def delete(list, item):
    lc = list[:]
    lc.remove(item)
    return lc

在我看来,一个很明显的方式可能是:

def permutList(l):
    if not l:
            return [[]]
    res = []
    for e in l:
            temp = l[:]
            temp.remove(e)
            res.extend([[e] + r for r in permutList(temp)])

    return res

注意,该算法具有n个阶乘时间复杂度,其中n是输入列表的长度

打印跑步结果:

global result
result = [] 

def permutation(li):
if li == [] or li == None:
    return

if len(li) == 1:
    result.append(li[0])
    print result
    result.pop()
    return

for i in range(0,len(li)):
    result.append(li[i])
    permutation(li[:i] + li[i+1:])
    result.pop()    

例子:

permutation([1,2,3])

输出:

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

用递归求解,遍历元素,取第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

此解决方案实现了一个生成器,以避免在内存中保留所有排列:

def permutations (orig_list):
    if not isinstance(orig_list, list):
        orig_list = list(orig_list)

    yield orig_list

    if len(orig_list) == 1:
        return

    for n in sorted(orig_list):
        new_list = orig_list[:]
        pos = new_list.index(n)
        del(new_list[pos])
        new_list.insert(0, n)
        for resto in permutations(new_list[1:]):
            if new_list[:1] + resto <> orig_list:
                yield new_list[:1] + resto