Python: получите все возможные комбинации для распределения x яблок по y корзинам с учетом ограничений - PullRequest
Новая
       11

Python: получите все возможные комбинации для распределения x яблок по y корзинам с учетом ограничений

0 голосов
/ 07 марта 2019

Предположим, у нас есть x яблоки и y корзины, мы хотим распределить все яблоки по корзинам таким образом, чтобы в каждой корзине было максимум 1003 * яблока.Как писать коды Python, чтобы получить все возможные комбинации.Для небольшого числа y я могу просто выполнить цикл по y следующим образом (x = 5, y = 3, z = 2). 

all_chances = np.zeros((0,3))
for a in range(3):
   for b in range(3):
      for c in range(3):
          if a+b+c == 5:
             all_chances = np.vstack((all_chances, np.array([a,b,c])))

В основном all_chances являются 

array([[1., 2., 2.],
   [2., 1., 2.],
   [2., 2., 1.]])

Мой вопрос: что, если у большое число, например х = 30, у = 26, z = 2?Нужно ли зацикливаться 26 раз?

Ответы [ 2 ]

0 голосов
/ 07 марта 2019

Вот метод, основанный на диаграммах Юнга. Например, 4 корзины, 6 яиц, максимум 3 яйца на корзину. Если мы упорядочим корзины по степени их заполнения, мы получим диаграммы Юнга. 

x x x x   x x x x   x x x     x x x      x x
x x       x         x x x     x x        x x
          x                   x          x x

Код ниже перечисляет все возможные диаграммы Юнга и для каждой перечисляет все возможные перестановки.

Та же логика также может использоваться для подсчета. 

from itertools import product, combinations
from functools import lru_cache
import numpy as np

def enum_ord_part(h, w, n, o=0):
    if h == 1:
        d = n
        for idx in combinations(range(w), d):
            idx = np.array(idx, int)
            out = np.full(w, o)
            out[idx] = o+1
            yield out
    else:
        for d in range((n-1)//h+1, min(w, n) + 1):
            for idx, higher in product(combinations(range(w), d),
                                       enum_ord_part(h-1, d, n-d, o+1)):
                idx = np.array(idx)
                out = np.full(w, o)
                out[idx] = higher
                yield out

def bc(n, k):
    if 2*k > n:
        k = n-k
    return np.prod(np.arange(n-k+1, n+1, dtype='O')) // np.prod(np.arange(1, k+1, dtype='O'))

@lru_cache(None)
def count_ord_part(h, w, n):
    if h == 1:
        return bc(w, n)
    else:
        return sum(bc(w, d) * count_ord_part(h-1, d, n-d)
                   for d in range((n-1)//h+1, min(w, n) + 1))

Несколько примеров: 

>>> for i, l in enumerate(enum_ord_part(3, 4, 6), 1):
...     print(l, end=' ' if i % 8 else '\n')
... 
[3 3 0 0] [3 0 3 0] [3 0 0 3] [0 3 3 0] [0 3 0 3] [0 0 3 3] [3 2 1 0] [2 3 1 0]
[3 1 2 0] [2 1 3 0] [1 3 2 0] [1 2 3 0] [2 2 2 0] [3 2 0 1] [2 3 0 1] [3 1 0 2]
[2 1 0 3] [1 3 0 2] [1 2 0 3] [2 2 0 2] [3 0 2 1] [2 0 3 1] [3 0 1 2] [2 0 1 3]
[1 0 3 2] [1 0 2 3] [2 0 2 2] [0 3 2 1] [0 2 3 1] [0 3 1 2] [0 2 1 3] [0 1 3 2]
[0 1 2 3] [0 2 2 2] [3 1 1 1] [1 3 1 1] [1 1 3 1] [1 1 1 3] [2 2 1 1] [2 1 2 1]
[2 1 1 2] [1 2 2 1] [1 2 1 2] [1 1 2 2]
>>> 
>>> print(f'{count_ord_part(2, 26, 30):,}')
154,135,675,070
>>> print(f'{count_ord_part(50, 30, 1000):,}')
63,731,848,167,716,295,344,627,252,024,129,873,636,437,590,711
0 голосов
/ 07 марта 2019

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

Я получаю 154 135 675 070 уникальных перестановок.

Для начала ... я возился с itertools, и перестановки длились вечно со списками длины 26. Итак ... чтобы напомнить себе о давно забытой формуле, по крайней мере, для подсчета различных перестановок, я нашел это .. . https://socratic.org/questions/how-many-distinct-permutations-can-be-made-from-the-letters-of-the-word-infinity

С этим я запустил следующее, чтобы получить счет. Он работает менее чем за секунду. 

from numpy import prod
from math import factorial
import itertools

# number of unique permutations
def count_distinct_permutations(tup):
    value_counts = [len(list(grp)) for _, grp in itertools.groupby(tup)]
    return factorial(sum(value_counts)) / prod([float(factorial(x)) for x in value_counts])

# starting values
x = 30 # apples
y = 26 # baskets
z = 3  # max per basket

# count possible results
result = 0
for combos in itertools.combinations_with_replacement(range(z), y):
    if sum(combos) == x:
        result += count_distinct_permutations(combos)

Теперь ... это, очевидно, не отвечает на ваш конкретный вопрос. Честно говоря, я все равно не смог удержать в памяти результат, который ты ищешь. Но ... вы можете сделать некоторые выводы с этим ... с выбранными вами значениями, есть только 12 комбинаций значений, но между 15k и 50 миллионами перестановок каждой комбинации.

Вы можете посмотреть на каждую комбинацию ... в функции count_distinct_permutations(), itertools.groupby сообщает вам, сколько из каждого числа из (0,1,2) находится в комбинации, и вы можете работать с каждым из этих двенадцати результатов, чтобы вывести некоторые вещи. Не уверен, что, но я также не совсем уверен, что делать с 154 миллиардами списков длиной 26.:)

Надеюсь, здесь было что-то полезное, даже если оно не ответило на ваш точный вопрос. Удачи!

...