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

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 all_insert(x, e, i=0):
    return [x[0:i]+[e]+x[i:]] + all_insert(x,e,i+1) if i<len(x)+1 else []

def for_each(X, e):
    return all_insert(X[0], e) + for_each(X[1:],e) if X else []

def permute(x):
    return [x] if len(x) < 2 else for_each( permute(x[1:]) , x[0])


perms = permute([1,2,3])

其他回答

另一种方法(无libs)

def permutation(input):
    if len(input) == 1:
        return input if isinstance(input, list) else [input]

    result = []
    for i in range(len(input)):
        first = input[i]
        rest = input[:i] + input[i + 1:]
        rest_permutation = permutation(rest)
        for p in rest_permutation:
            result.append(first + p)
    return result

输入可以是字符串或列表

print(permutation('abcd'))
print(permutation(['a', 'b', 'c', 'd']))

如果不想使用内置方法,例如:

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

你可以自己实现permute函数

from collections.abc import Iterable


def permute(iterable: Iterable[str]) -> set[str]:
    perms = set()

    if len(iterable) == 1:
        return {*iterable}

    for index, char in enumerate(iterable):
        perms.update([char + perm for perm in permute(iterable[:index] + iterable[index + 1:])])

    return perms


if __name__ == '__main__':
    print(permute('abc'))
    # {'bca', 'abc', 'cab', 'acb', 'cba', 'bac'}
    print(permute(['1', '2', '3']))
    # {'123', '312', '132', '321', '213', '231'}

这是受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
list2Perm = [1, 2.0, 'three']
listPerm = [[a, b, c]
            for a in list2Perm
            for b in list2Perm
            for c in list2Perm
            if ( a != b and b != c and a != c )
            ]
print listPerm

输出:

[
    [1, 2.0, 'three'], 
    [1, 'three', 2.0], 
    [2.0, 1, 'three'], 
    [2.0, 'three', 1], 
    ['three', 1, 2.0], 
    ['three', 2.0, 1]
]

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

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)