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

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]

当前回答

免责声明:无耻的插件由包作者。:)

trotter包与大多数实现的不同之处在于,它生成的伪列表实际上不包含排列,而是描述排列与排序中各个位置之间的映射,从而可以处理非常大的排列“列表”,如本演示所示,它在一个包含字母表中所有字母排列的伪列表中执行相当即时的操作和查找,而不使用比典型网页更多的内存或处理。

在任何情况下,要生成排列列表,我们可以执行以下操作。

import trotter

my_permutations = trotter.Permutations(3, [1, 2, 3])

print(my_permutations)

for p in my_permutations:
    print(p)

输出:

A pseudo-list containing 6 3-permutations of [1, 2, 3].
[1, 2, 3]
[1, 3, 2]
[3, 1, 2]
[3, 2, 1]
[2, 3, 1]
[2, 1, 3]

其他回答

如果用户希望在列表中保留所有排列,可以使用以下代码:

def get_permutations(nums, p_list=[], temp_items=[]):
    if not nums:
        return
    elif len(nums) == 1:
        new_items = temp_items+[nums[0]]
        p_list.append(new_items)
        return
    else:
        for i in range(len(nums)):
            temp_nums = nums[:i]+nums[i+1:]
            new_temp_items = temp_items + [nums[i]]
            get_permutations(temp_nums, p_list, new_temp_items)

nums = [1,2,3]
p_list = []

get_permutations(nums, p_list)

为了节省您可能的搜索和实验时间,下面是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实现。

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

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

使用标准库中的itertools.permutations:

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

从这里改编的是itertools.permutations如何实现的演示:

def permutations(elements):
    if len(elements) <= 1:
        yield elements
        return
    for perm in permutations(elements[1:]):
        for i in range(len(elements)):
            # nb elements[0:1] works in both string and list contexts
            yield perm[:i] + elements[0:1] + perm[i:]

itertools.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 = range(n)
    cycles = 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

另一个基于itertools.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)