python:获取所有可能的组合,以便根据约束将x个苹果分配给y个篮子

这是一个基于年轻图表的方法。例如,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

我把你的问题搞砸了…尝试实现一种基于树的bc方法,我认为它很聪明,但我的笔记本电脑被它卡住了。我很好奇我们到底要用这么大的数字来寻找多少排列,然后(对我自己)把问题改成简单地计算排列,看看在一台轻量级笔记本电脑上是否可行。

我得到154135675070个独特的排列。

开始…我把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到5000万之间。

你可以看看每个组合…在 count_distinct_permutations() 函数, itertools.groupby 为您提供每个数字的来源 (0,1,2) 在组合中,你可以用这12个结果中的每一个来推断一些东西。不知道是什么,但我也不太确定如何处理长度为26的1540亿个列表。:)

希望这里有有用的东西,即使它没有回答你确切的问题。祝你好运!