如何生成列表的所有排列？

问题描述 投票：548回答：29

您如何在Python中生成列表的所有排列，而与列表中元素的类型无关？

例如：

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]
python algorithm permutation combinatorics python-2.5
29个回答
441
投票

从Python 2.6开始（如果您使用的是Python 3），您可以使用standard-library工具：itertools.permutations。

itertools.permutations

如果您出于某些原因使用旧Python（<2.6），或者只是想知道其工作方式，以下是一种不错的方法，摘自import itertools list(itertools.permutations([1, 2, 3])) ：

http://code.activestate.com/recipes/252178/

def all_perms(elements): if len(elements) <=1: yield elements else: for perm in all_perms(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
10
投票
[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]
8
投票

我使用了基于[ [1, 2.0, 'three'], [1, 'three', 2.0], [2.0, 1, 'three'], [2.0, 'three', 1], ['three', 1, 2.0], ['three', 2.0, 1] ] 的算法-对于长度为n的列表，您可以逐项组合每个置换项，并从每个阶段剩下的项中进行选择。第一项有n个选择，第二项有n-1个，最后一项只有n个，因此可以使用阶乘数字系统中数字的数字作为索引。这样，数字0到n！-1对应于按字典顺序的所有可能排列。

7
投票

请注意，此算法的时间复杂度为[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]] ，其中n factorial是输入列表的长度

7
投票

的确可以像tzwenn的回答中那样迭代每个排列的第一个元素；我更喜欢这样写解决方案：

5
投票

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

4
投票

出于性能考虑，一个受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 启发的numpy解决方案（p22）：

3
投票
In [1]: %timeit -n10 list(permutations(range(10)))
10 loops, best of 3: 815 ms per loop

In [2]: %timeit -n100 perms(10) 
100 loops, best of 3: 40 ms per loop
3
投票

这里是一种在列表上工作的算法，无需创建类似于from __future__ import print_function def perm(n): p = [] for i in range(0,n+1): p.append(i) while True: for i in range(1,n+1): print(p[i], end=' ') print("") i = n - 1 found = 0 while (not found and i>0): if p[i]<p[i+1]: found = 1 else: i = i - 1 k = n while p[i]>p[k]: k = k - 1 aux = p[i] p[i] = p[k] p[k] = aux for j in range(1,(n-i)/2+1): aux = p[i+j] p[i+j] = p[n-j+1] p[n-j+1] = aux if not found: break perm(5) 处Ber的解决方案的新中间列表。

3
投票

递归之美：

3
投票

[该算法是最有效的，它避免了在递归调用中进行数组传递和操作，在Python 2、3中有效]]

>>> 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']
330
投票

并且从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) 开始：

Python 2.6

（作为生成器返回。使用import itertools itertools.permutations([1,2,3]) 作为列表返回。）

3
投票
for p in permute((1,2,3)):
    print(p)

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
2
投票

生成所有可能的排列

2
投票

另一种方法（无库）

1
投票

我看到这些递归函数中正在进行迭代的lot

1
投票

另一个解决方案：

1
投票

[为了节省您的人们可能的搜索和实验时间，这是Python中的非递归置换解决方案，它也适用于Numba（自0.41版起：]]]

def permutation(flag, k =1 ):
    N = len(flag)
    for i in xrange(0, N):
        if flag[i] != 0:
            continue
        flag[i] = k 
        if k == N:
            print flag
        permutation(flag, k+1)
        flag[i] = 0

permutation([0, 0, 0])
0
投票

我的Python解决方案：

%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
0
投票
def permutes(input,offset):
    if( len(input) == offset ):
        return [''.join(input)]

    result=[]        
    for i in range( offset, len(input) ):
         input[offset], input[i] = input[i], input[offset]
         result = result + permutes(input,offset+1)
         input[offset], input[i] = input[i], input[offset]
    return result

# input is a "string"
# return value is a list of strings
def permutations(input):
    return permutes( list(input), 0 )

# Main Program
print( permutations("wxyz") )

输出：['abc'，'acb'，'bac'，'bca'，'cab'，'cba']

0
投票

使用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') 

Counter
-3
投票

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

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]]
264
投票

以下代码仅适用于Python 2.6及更高版本

首先，导入list(permutations(l))：

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

37
投票
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)]
25
投票
permutations('abc')
21
投票

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

15
投票

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

13
投票

我认为，很明显的一种方式可能是：

12
投票

以实用样式

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.