Создать продукт списка с условиями

Question

Я хочу обрабатывать большие числа с 10k + цифрами, поэтому я использую кортежи, потому что нельзя использовать целочисленный тип (точность числа важна, потому что сумма цифр). Есть только 2 уникальные цифры, 9 и 0.

Первое условие: по модулю сумма цифр с 999 равна 0.
Второе условие: это большое целое число, поэтому первая ди git не может быть 0.
Последнее условие: Last di git равно 0.

Мое решение:

from itertools import product

L = [10000,11000,12000]

for M in L:
    for i in product([0, 9], repeat=M):
        if i[0] != 0 and i[-1] == 0:
            s = sum(i)
            if s % 999 == 0:
                print (s)

Возможно ли подсчитать количество сгенерированных значений с этими условиями? Возможно ли изменить решение / другое решение (я) для сокращения времени генерации ожидаемого результата, например, генерировать только цифры с sum of digits больше похоже на 999? Я думаю о Decimal, но здесь проблема с sum цифр. Порядок сгенерированных number s (кортежей, массивов) не важен.

Это настолько огромные кортежи, что проблематично c легкое тестирование. Я пытаюсь создать пример (не идея, если она полезна):

for i in product([9, 0], repeat=20):
    if i[0] != 0 and i[-1] == 0:
        s = sum(i)
        if s % 99 == 0:
            print (i, s)

Answer 1

Количество таких возможных чисел было бы слишком велико, чтобы сгенерировать все.

Давайте назовем L числом цифр в вашем номере, а n числом 9.

Модуль суммы цифр с 999 равен 0 означает, что: n * 9 = m * 999, поэтому n = k * 111, где k - целое число.

Первое число di git равно 9, а последнее равно 0, поэтому осталось L-2 места для размещения оставшихся (k * 111 - 1) 9 цифр.

Таким образом, число таких чисел является суммой количества комбинаций ((L-2) select (k * 111-1)) для k между 1 и int ((L -1) / 111))

Итак, возможный код:

import operator as op
from functools import reduce

# From https://stackoverflow.com/questions/4941753/is-there-a-math-ncr-function-in-python
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom  # Changed for integer division

def possible_numbers(L):
    return sum(ncr(L-2, 111*k - 1) for k in range(1, (L-1)//111))

print(possible_numbers(10000))

# 46506588317635469366401415658013639152242514965252855714041144018498987152707044490194457854465305060020773686383485941436739496916009717012616366376246414571169910310699834725291436347258613064146124967400646078243663290971123135369040450765747850207912640778375391521167004887068454467534692885571315434928724105198818380334746555427574950364615165695566283976630032289652540054620732064526597228268611847676696899672765577347754597526393233231013911103228183531257080334315932738035622562131489280570776426153110319970303630143757955230868260221372217820886676391878309046535523092899792732603384686832015291205699914402933832273424671204699396414708887671531202101527299797220557526495935874078061714541726044022824401127277289199364810083989340886903060879319068042995827037751119856277555325118818012910801413269671414202747818363564693812789991123599795926600974448559896232026533659303781683288750777356519373140416641070335357434342957815577446771837059264519071351111701743419392138893923198793667574531536322827159764885405347516087975885606826893886851504292563461335005149974908491745377479301673268815242719993061641393932755789000155034631404392298259100662543152918803846714114697300923960523557500317195566759812657273510052876469933988067730551693799653175259045326679352888837840615599025061763546193617710870648379633919635058872421276909819607798170545658257733866028814603688331134993133516485082037147925444085128568947517112262094010118995477748614613681297345233932152146172358997240155349554049974584904754905949454881684316277423691704957916937555749917546766207774972493217477043714652995265409684903579726779500656471405514359721102426435531185506178592945522184727847016844486420511644284474508534529688998209007331208512957982383305010070433027822069432758467560863914508655552438978200137331142103777139831138329641584247585016869654053739406398693488384069254725347054264531039092260379613683402826431841651702016107570078218034751759156452991362380781969813524106141836783707976391132433066632109509663706711194120392913346984831497576260954280288258157219236029228818152608039675500130313183928069363862241906263121908112579346403564641214804122206420758371341181045355185272831160085528848859295608701517219671599684543743252593692174235989978345204406049350779297271034684859111097644033128750102959471412294900623227232358717924727059914175333714529865811974930107943791917826273949743788824216294023431731389259674185985763199421896541289618952210976760618905706699064025869740093553019041859274291091877197046340635783795996884883288761816361022414903437664468405527174106098428305866565043923442930029525366818247447766037463650273567442968538251684623455304412633953426243893756890813731429721493555818339963997009857257028373522283512536995315377100044676823672536566066483879259428166867133820082490868856820190168040370122307493700971959637546773031509327007856264111997525714829526125911250334270232166355120078967567596110824407335535205220718583123846127299455

# It's 3008 digits long....

Answer 2

Меньше математического решения - использование динамического программирования c:

M = 1000
cache = {}

def dp(i, v, sum_of_digits):
  if(i == M-1):
    return sum_of_digits % 999 == 0 and v == 0

  if((i, sum_of_digits) in cache):
    return cache.get((i, sum_of_digits))

  result = dp(i + 1, 0, sum_of_digits) + dp(i + 1, 9, sum_of_digits + 9)
  cache[(i, sum_of_digits)] = result
  return result


print(dp(0, 9, 9))

Вывод:

281853033550040537904406694735205583322614867369419355514834998793657889372557150681302072580895266688090267034276630517914503707145674628565136259594047883519869400688956077638702940707076342539608905721192230524534619011898800645140130344499642277977871480846234887754725793524573506157312565257

Пояснение :

Динами c алгоритм программирования работает на , запоминая полученные результаты В нашем случае это cache dict, которые хранят промежуточные результаты.

При каждом вызове у нас есть две возможности: 1) либо следующий di git равен 0; поэтому мы не увеличиваем sum_of_digits; 2) или это 9; поэтому мы увеличиваем sum_of_digits.

При каждом вызове мы запоминаем результаты, которые получаем, суммируя два промежуточных результата: dp(i + 1, 0, sum_of_digits), dp(i + 1, 9, sum_of_digits + 9).

мы завершаем работу при наличии M количества цифр, возвращая True, если sum_of_digits по модулю 999 равно 0, а последний ди git v равен 0.

Обратите внимание, что мы не проверяем первый ди git, потому что у нас всегда 9 в качестве первого ди git dp(0, 9, 9).

Примечание:

1. вам может потребоваться увеличить максимальную глубину рекурсии, используя:

   sys.setrecursionlimit(XXXXXX..)

   или вы можете преобразовать рекурсивное решение в итеративное (это всегда возможно сделать).

2. Хотя это решение более эффективно, чем решение методом перебора, @Thierry_Lathuille более эффективно чем это решение.