在一个列表的所有可能排列中，已排序元素（排列数）的数量

Question

给定一个数组，比如说，arr = [5, 5, 4, 4, 2, 1]，我该如何找到所有可能的排列中与原始数组相同的排列数量（假设原始数组总是按降序排列）。在这个示例中，将有4个排列与原始数组相等。使用Python中的itertools.permutations可以得到这个结果。有没有更快的方法？我会非常感激。以下是我的Python代码，速度太慢了。

from itertools import permutations

arr = sorted(map(int, (raw_input().split())), reverse = True)

perms = permutations(n,len(arr))

cnt = 0;

for i in perms:
    if list(i) == arr: print i; cnt += 1
print cnt

- Carlson Bimbuh

---

有人能告诉我为什么我的问题被踩了吗？ - Carlson Bimbuh

Answer 1

假设您的数组大小为n，其中包含r1、r2、...、rk个重复元素，使得ri之和等于n。那么答案就是这些重复元素的阶乘的乘积。

例如，对于arr = [5, 5, 4, 4, 2, 1]，我们得到r = [2, 2, 1, 1]，答案为2！* 2！* 1！* 1！= 4。

- Dave

---

它是否已排序并不重要。您可以处理任意数组以获取每个元素的计数，然后取这些计数的阶乘乘积。 - Dave

Answer 2

你可以得到所有相同值子序列长度的阶乘积：

from itertools import groupby
from functools import reduce
from math import factorial
from operator import mul
print(reduce(mul, map(lambda t: factorial(sum(1 for i in t[1])), groupby(arr))))

这将输出：4。

- blhsing

---

附带的解释可能会很有用，但functools的使用很好。 - D. Ben Knoble

Answer 3

对于N个元素，可能的排列数为N！

例如，如果你有[5, 5, 5, 4, 1]，那么有3！种排列方式是相同的。

我会循环遍历数组，并将值和该值出现的次数存储在关联数组中。

伪代码：

firstArray = [5, 5, 4, 4, 2, 1]
doubleArray = []

for each item in firstArray:
    if item is in doubleArray keys:
        doubleArray[item]++
    else:
        doubleArray[item] = 1

result = 1
for each elem in doubleArray:
    result *= fact(elem)

print "There is " + elem + " permutations possible where the original array remains the same"

- Cid