Использование math.factorial в лямбда-функции с помощью less () - PullRequest
Новая
       10

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

1 голос
/ 26 сентября 2011

Я пытаюсь написать функцию, которая вычисляет количество уникальных перестановок строки.Например, 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), но я ищу, почему это конкретно не работает.

Ответы [ 4 ]

2 голосов
/ 26 сентября 2011

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

>>> reduce(lambda x, y: ord(x) + ord(y), ['a'], chr(0))
97
1 голос
/ 26 сентября 2011

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

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

import operator
reduce(operator.mul, [factorial(x) for x in lst])
1 голос
/ 26 сентября 2011

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

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

reduce(lambda x,y: x * factorial(y), lst, 1)
0 голосов
/ 26 сентября 2011

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

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

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

Удачи!

...