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

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]

当前回答

from typing import List
import time, random

def measure_time(func):
    def wrapper_time(*args, **kwargs):
        start_time = time.perf_counter()
        res = func(*args, **kwargs)
        end_time = time.perf_counter()
        return res, end_time - start_time

    return wrapper_time


class Solution:
    def permute(self, nums: List[int], method: int = 1) -> List[List[int]]:
        perms = []
        perm = []
        if method == 1:
            _, time_perm = self._permute_recur(nums, 0, len(nums) - 1, perms)
        elif method == 2:
            _, time_perm = self._permute_recur_agian(nums, perm, perms)
            print(perm)
        return perms, time_perm

    @measure_time
    def _permute_recur(self, nums: List[int], l: int, r: int, perms: List[List[int]]):
        # base case
        if l == r:
            perms.append(nums.copy())

        for i in range(l, r + 1):
            nums[l], nums[i] = nums[i], nums[l]
            self._permute_recur(nums, l + 1, r , perms)
            nums[l], nums[i] = nums[i], nums[l]

    @measure_time
    def _permute_recur_agian(self, nums: List[int], perm: List[int], perms_list: List[List[int]]):
        """
        The idea is similar to nestedForLoops visualized as a recursion tree.
        """
        if nums:
            for i in range(len(nums)):
                # perm.append(nums[i])  mistake, perm will be filled with all nums's elements.
                # Method1 perm_copy = copy.deepcopy(perm)
                # Method2 add in the parameter list using + (not in place)
                # caveat: list.append is in-place , which is useful for operating on global element perms_list
                # Note that:
                # perms_list pass by reference. shallow copy
                # perm + [nums[i]] pass by value instead of reference.
                self._permute_recur_agian(nums[:i] + nums[i+1:], perm + [nums[i]], perms_list)
        else:
            # Arrive at the last loop, i.e. leaf of the recursion tree.
            perms_list.append(perm)



if __name__ == "__main__":
    array = [random.randint(-10, 10) for _ in range(3)]
    sol = Solution()
    # perms, time_perm = sol.permute(array, 1)
    perms2, time_perm2 = sol.permute(array, 2)
    print(perms2)
    # print(perms, perms2)
    # print(time_perm, time_perm2)
```

其他回答

对于Python,我们可以使用itertools并导入排列和组合来解决问题

from itertools import product, permutations
A = ([1,2,3])
print (list(permutations(sorted(A),2)))

生成所有可能的排列

我正在使用python3.4:

def calcperm(arr, size):
    result = set([()])
    for dummy_idx in range(size):
        temp = set()
        for dummy_lst in result:
            for dummy_outcome in arr:
                if dummy_outcome not in dummy_lst:
                    new_seq = list(dummy_lst)
                    new_seq.append(dummy_outcome)
                    temp.add(tuple(new_seq))
        result = temp
    return result

测试用例:

lst = [1, 2, 3, 4]
#lst = ["yellow", "magenta", "white", "blue"]
seq = 2
final = calcperm(lst, seq)
print(len(final))
print(final)

递归之美:

>>> import copy
>>> def perm(prefix,rest):
...      for e in rest:
...              new_rest=copy.copy(rest)
...              new_prefix=copy.copy(prefix)
...              new_prefix.append(e)
...              new_rest.remove(e)
...              if len(new_rest) == 0:
...                      print new_prefix + new_rest
...                      continue
...              perm(new_prefix,new_rest)
... 
>>> perm([],['a','b','c','d'])
['a', 'b', 'c', 'd']
['a', 'b', 'd', 'c']
['a', 'c', 'b', 'd']
['a', 'c', 'd', 'b']
['a', 'd', 'b', 'c']
['a', 'd', 'c', 'b']
['b', 'a', 'c', 'd']
['b', 'a', 'd', 'c']
['b', 'c', 'a', 'd']
['b', 'c', 'd', 'a']
['b', 'd', 'a', 'c']
['b', 'd', 'c', 'a']
['c', 'a', 'b', 'd']
['c', 'a', 'd', 'b']
['c', 'b', 'a', 'd']
['c', 'b', 'd', 'a']
['c', 'd', 'a', 'b']
['c', 'd', 'b', 'a']
['d', 'a', 'b', 'c']
['d', 'a', 'c', 'b']
['d', 'b', 'a', 'c']
['d', 'b', 'c', 'a']
['d', 'c', 'a', 'b']
['d', 'c', 'b', 'a']

对于Python 2.6及以上版本:

import itertools
itertools.permutations([1, 2, 3])

这将作为生成器返回。使用列表(排列(xs))作为列表返回。

以下代码是给定列表的就地排列,作为生成器实现。由于它只返回对列表的引用,因此不应在生成器外部修改列表。该解决方案是非递归的,因此使用了低内存。还可以很好地处理输入列表中元素的多个副本。

def permute_in_place(a):
    a.sort()
    yield list(a)

    if len(a) <= 1:
        return

    first = 0
    last = len(a)
    while 1:
        i = last - 1

        while 1:
            i = i - 1
            if a[i] < a[i+1]:
                j = last - 1
                while not (a[i] < a[j]):
                    j = j - 1
                a[i], a[j] = a[j], a[i] # swap the values
                r = a[i+1:last]
                r.reverse()
                a[i+1:last] = r
                yield list(a)
                break
            if i == first:
                a.reverse()
                return

if __name__ == '__main__':
    for n in range(5):
        for a in permute_in_place(range(1, n+1)):
            print a
        print

    for a in permute_in_place([0, 0, 1, 1, 1]):
        print a
    print