Использование math.factorial в лямбда-функции с функцией reduce()

Я пытаюсь написать функцию, которая вычисляет количество уникальных перестановок строки. Например, aaa вернет 1, а abc вернет 6.
Я пишу метод следующим образом:

(Псевдокод :)

len(string)! / (A!*B!*C!*...)

где A,B,C — количество вхождений каждого уникального символа. Например, строка 'aaa' будет 3! / 3! = 1, а 'abc' будет 3! / (1! * 1! * 1!) = 6.

Мой код пока такой:

def permutations(n):
    '''
    returns the number of UNIQUE permutations of n
    '''
    from math import factorial

    lst = []
    n = str(n)
    for l in set(n):
        lst.append(n.count(l))

    return factorial(len(n)) / reduce(lambda x,y: factorial(x) * factorial(y), lst)

Все работает нормально, за исключением случаев, когда я пытаюсь передать строку, содержащую только один уникальный символ, т.е. aaa - я получаю неправильный ответ:

>>> perm('abc')
6
>>> perm('aaa')
2
>>> perm('aaaa')
6

Теперь я могу сказать, что проблема заключается в запуске лямбда-функции с факториалами в списке длины 1. Однако я не знаю, почему. Большинство других лямбда-функций работают со списком длиной 1, даже если он ожидает два элемента:

>>> reduce(lambda x,y: x * y, [3])
3
>>> reduce(lambda x,y: x + y, [3])
3

Этот не:

>>> reduce(lambda x,y: ord(x) + ord(y), ['a'])
'a' 
>>> reduce(lambda x,y: ord(x) + ord(y), ['a','b'])
195

Есть ли что-то, что я должен делать по-другому? Я знаю, что могу переписать функцию разными способами, чтобы обойти это (например, не используя lambda), но я ищу, почему это конкретно не работает.


python lambda reduce permutation factorial
person Hod - Monica's Army    schedule 26.09.2011    source источник

Ответы (4)


arrow_upward
1
arrow_downward

Функция Python reduce не всегда знает, каким должно быть значение по умолчанию (начальное). Должна быть версия, которая принимает начальное значение. Укажите разумное начальное значение, и ваш reduce должен работать прекрасно.

Кроме того, из комментариев вам, вероятно, следует просто использовать factorial во втором аргументе в вашей лямбде:

reduce(lambda x,y: x * factorial(y), lst, 1)
person Platinum Azure    schedule 26.09.2011
comment
@agf и Platinum Azure. Спасибо, это работает для списка размером 1, но все, что больше, не работает. Почему? В документации, похоже, говорится, что начальное значение следует рассматривать так, как если бы список был просто на один элемент длиннее. - person Hod - Monica's Army; 27.09.2011
comment
Вы можете попробовать reduce(lambda x,y: x * factorial(y), lst, 1). Ваша лямбда вычисляется как ((1! * 2!)! * 3!)! .... - person cHao; 27.09.2011
comment
Вы уверены, что должны использовать factorial(x) в качестве первого аргумента? Если вам нужен продукт всех факториалов, вы должны использовать reduce(lambda x,y: x * factorial(y), lst, 1). - person Platinum Azure; 27.09.2011
comment
@cHao и Platinum Azure. Спасибо! Это исправило это. - person Hod - Monica's Army; 27.09.2011

arrow_upward
2
arrow_downward

См. документацию для reduce(), там есть необязательный аргумент "инициализатор", который помещается перед всеми другими элементами в списке, чтобы поведение для одного списка элементов было согласованным, например, для вашей лямбды ord() вы можете установить initializer на символ с ord() равным 0:

>>> reduce(lambda x, y: ord(x) + ord(y), ['a'], chr(0))
97
person Andrew Clark    schedule 26.09.2011

arrow_upward
1
arrow_downward

Если вы хотите len(s)! / A!*B!*C!, то использование reduce() не сработает, так как будет вычислено factorial(factorial(A)*factorial(B))*factorial(C). Другими словами, операция действительно должна быть коммутативной.

Вместо этого вам нужно создать список факториалов, а затем перемножить их вместе:

import operator
reduce(operator.mul, [factorial(x) for x in lst])
person Malcolm Box    schedule 26.09.2011

arrow_upward
0
arrow_downward

Сокращение работает, сначала вычисляя результат для первых двух элементов в последовательности, а затем псевдорекурсивно следует оттуда. Список размера 1 является частным случаем.

Я бы использовал понимание списка здесь:

prod( [ factorial(val) for val in lst ] )

Удачи!

person user    schedule 26.09.2011