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

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

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

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

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

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

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

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

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

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


python combinations itertools
person deepgeek    schedule 29.10.2011    source источник
comment
Это нужно для решения расширения Car Talk Puzzle от 22 октября. Дали ответ и намекнули на общее решение. cartalk.com/content/puzzler/transcripts/201143/index.html< /а>   -  person deepgeek    schedule 30.10.2011
comment
Ссылка ведет не туда, куда должна   -  person joaquin    schedule 22.11.2011
comment
Ссылка на загадку Car Talk.   -  person Li-aung Yip    schedule 27.03.2012

Ответы (3)


arrow_upward
2
arrow_downward

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

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

См. Википедию, чтобы узнать фактическую формулу.

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

person Jochen Ritzel    schedule 29.10.2011

arrow_upward
6
arrow_downward

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

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

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

person Danica    schedule 29.10.2011
comment
Действительно "грубая сила"! Отлично работало для исходного решения, но я вижу, что оно не сильно масштабируется. Но их общее решение «степень трех» действительно имеет смысл для решений, превышающих 6 частей. Спасибо. - person deepgeek; 30.10.2011
comment
@deepgeek: В каком-то смысле это удивительное применение троичной системы подсчета. Вы могли бы сделать то же самое с гирями в степени двойки: 1, 2, 4, 8, 16... только в том случае, если сумма требуемых камней не будет равна 40 кг. (Вместо этого они в сумме дают более удобный набор чисел: n такие камни в сумме дают вес 2^ n - 1.) - person Li-aung Yip; 27.03.2012

arrow_upward
0
arrow_downward

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

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

person Raymond Hettinger    schedule 30.10.2011