Количество отсортированных элементов (перестановок) во всех возможных перестановках списка

Question

Учитывая массив, скажем, arr = [5, 5, 4, 4, 2, 1], как я могу найти из всех возможных перестановок этого массива количество перестановок, которые совпадают с исходным массивом (если исходный массив всегда сортируется в порядке убывания),В этом примере будет 4 перестановки, равные исходному массиву.Ну, вот что я получаю, используя itertools.permutations в Python.Кто-нибудь с чем-то быстрее?Я буду очень благодарен.Ниже приведен мой медленный код 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

Answer 1

Вы можете получить произведение факториалов на длины всех подпоследовательностей одинакового значения:

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

Answer 2

Для 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"

Answer 3

Скажите, что ваш массив имеет размер n, а повторения - это r1, r2, ..., rk, так что сумма (ri) = n.Тогда ответом является произведение факториалов повторений.

Например, для arr = [5, 5, 4, 4, 2, 1] получаем r = [2, 2, 1, 1] и ответ 2!* 2!* 1!* 1!= 4