8

计算排列数的最快方法是什么？我有以下问题：

首先我有这个：

ncombos = itertools.combinations_with_replacement(['a1', 'a2', 'a3'], years*n)
('a1', 'a1', 'a1')
('a1', 'a1', 'a2')
('a1', 'a1', 'a3')
('a1', 'a2', 'a2')
.... etc.....    
('a3', 'a3', 'a3')

目的是遍历每一个并计算每个排列的数量，并用这些值构造一个数组。我使用以下方法实现了这个：

nodes = np.ones(len(leafs)); i=0  #This will store the number of permutations

for j in ncombos:
    nodes[i] =len(list(set(itertools.permutations(np.asanyarray(j), n))))
    i = i+1

np.asanyarray(j) 将 ('a1','a1','a1') 转换为正式的 ['a1','a1', 'a1'] ，这是 permutations() 工作所需要的。set 删除相同的排列。list 列出了这个。len 计算我可以用 a1、a1、a1 进行多少排列。

所以基本上我想要的只是计算排列的数量......但是我的代码非常好！减缓 ！谢谢！

4

2 回答 2

18

使用数学。列表的排列数是列表长度的阶乘除以每个元素的多重性的阶乘的乘积（因为重复元素的集合被排列而没有效果）。

import operator
from collections import Counter
from math import factorial
def npermutations(l):
    num = factorial(len(l))
    mults = Counter(l).values()
    den = reduce(operator.mul, (factorial(v) for v in mults), 1)
    return num / den

例子：

>>> npermutations([1,1,1])
1
>>> npermutations([1,2,3])
6
>>> npermutations([1,3,1,2,1,3,1,2])
420
于 2013-05-09T02:09:33.347 回答
0

如果您想要置换置换，这存在并称为笛卡尔积。Itertools 对此有一个功能product()：

>>> for i in itertools.product('ABC', repeat=3):
...     print i
...
('A', 'A', 'A')
('A', 'A', 'B')
('A', 'A', 'C')
('A', 'B', 'A')
('A', 'B', 'B')
('A', 'B', 'C')
('A', 'C', 'A')
('A', 'C', 'B')
('A', 'C', 'C')
('B', 'A', 'A')
('B', 'A', 'B')
('B', 'A', 'C')
('B', 'B', 'A')
('B', 'B', 'B')
('B', 'B', 'C')
('B', 'C', 'A')
('B', 'C', 'B')
('B', 'C', 'C')
('C', 'A', 'A')
('C', 'A', 'B')
('C', 'A', 'C')
('C', 'B', 'A')
('C', 'B', 'B')
('C', 'B', 'C')
('C', 'C', 'A')
('C', 'C', 'B')
('C', 'C', 'C')
于 2013-05-09T02:08:41.130 回答