Время, затраченное на решение задачи Эйлера 862, слишком велико ⇐ Python

[Anonymous]

Это занимает много времени (на вычисление S(8) ушло 47 минут).
Ссылка на задачу: https://projecteuler.net/problem=862 >
Я работал над задачей Эйлера 862 проекта и в настоящее время столкнулся с проблемой производительности. Моя реализация функции S(8) занимает около 47 минут, что слишком долго для моих требований. Я ищу оптимизацию, позволяющую сократить время вычислений, чтобы оно соответствовало пределу в 100 000 мс (100 секунд).
Код вычисляет S(k), который представляет собой сумму T(n ) для всех k-значных чисел, где T(n) считает лексикографически меньшие перестановки n. Меня особенно интересует оптимизация count_permutations и T(n), чтобы решение эффективно масштабировалось, особенно по мере увеличения k.
Вот мой код:
Код выглядит следующим образом. :

Код: Выделить всё

from math import factorial
from collections import Counter
factorials = [1] * 13
for i in range(2, 13):
factorials[i] = factorials[i - 1] * i

def count_permutations(digit_count):
total_digits = sum(digit_count.values())
perms = factorials[total_digits]
for count in digit_count.values():
perms //= factorials[count]
return perms
def T(n):
str_n = str(n)
digit_count = Counter(str_n)
total_count = 0
for i in range(len(str_n)):
for digit in range(int(str_n[i]) + 1, 10):
if digit_count[str(digit)] > 0:
digit_count[str(digit)] -= 1
total_count += count_permutations(digit_count)
digit_count[str(digit)] += 1
digit_count[str_n[i]] -= 1
if digit_count[str_n[i]] == 0:
del digit_count[str_n[i]]

return total_count
def S(k):
total_sum = 0
start = 10**(k-1)
end = 10**k
for n in range(start, end):
total_sum += T(n)

return total_sum

result = S(12)
print(f"S(12) = {result}")

Каковы наиболее эффективные способы оптимизации этого кода, особенно count_permutations и T(n), чтобы улучшить время его выполнения? Мы будем очень признательны за любые предложения по кэшированию, сокращению вычислений факториалов или другим алгоритмическим оптимизациям. Спасибо!

Подробнее здесь: https://stackoverflow.com/questions/791 ... y-too-long