Как масштабируется itertools.combination в Python

Question

Я использую метод грубой силы, пытаясь найти комбинацию для продолжения головоломки.

Я пытаюсь получить большое количество комбинаций и затем проверить каждую комбинацию, чтобы увидеть,соответствуют определенным критериям.Я генерирую комбинации, используя отличные инструменты Python для Python, по сути, это дает мне итератор, который я могу пройти и проверить каждую.

Это быстро возвращается и дает мне 91390 комбинаций для проверки:

itertools.combinations(range(1, 40), 4)

Это займет пару минут и даст мне 198792594 комбинаций для тестирования:

itertools.combinations(range(1, 122), 5)

Когда я перехожу на следующий уровень, мне нужен ответ на этот вопрос:

itertools.combinations(range(1, 365), 6)

Когда я попадаю в 6-комбинационные комбинации из 364 ... это занимает очень много времени. ВОЗРАСТ .Я по своей сути прошу много комбинаций?Как оно масштабируется?

Answer 1

Вы просите 365 выбрать 6 = (365 * 364 * ... * 360) / (6 * 5 * ... * 2 * 1) = 3 151 277 509 380 комбинаций. Это лот . Зацикливание более 3 триллионов элементов просто не будет происходить на вашем рабочем столе в Python - никак.

Если вы просто ищете, сколько их должно быть, формула для вычисления этого напрямую, без учета всех из них, будет в Википедии .

Редактировать: Я только что посмотрел на проблему, и кажется, что вы пытаетесь решить ее, рассматривая все возможные комбинации весов и проверяя, работают ли они. Грубое принуждение явно не сработает в этой ситуации - вам придется подумать о более умном решении.

Answer 2

Вы рассчитываете эти числа следующим образом:

1. Перейти на google.com
2. введите "40 выберите 4"
3. введите "121 выберите 5"
4. введите " 364 выберите 6 "

См. википедию для фактической формулы.

Масштабируется как факторная функция.

Answer 3

Согласно документации itertools , number of items returned is n! / r! / (n-r)! when 0 <= r <= n or zero when r > n.

Использование памяти мало - достаточно для хранения пула n-элементов и кортежа результата r-длины.