拆分书架的可能性

Question

我在 Python 中遇到以下问题。这个问题更像是数学问题而不是 Python 具体问题。

我有很多 N 本书作为一个堆栈。还有一些 P 个堆栈可以拆分。 我正在寻找拆分此堆栈的可能性，避免重复和空堆栈。

假设我的书堆有 4 本书高，分成 2 书堆的可能性有多大？

拆分的可能性为：

(1,3)
(2,2)

也有可能 (3,1)，但由于 (1,3) 已经在我的输出中，我不希望 (3,1) 也在那里。

另一个例子：

5 books, 3 stacks

(3,1,1)
(2,2,1)

像 (1,1,3)、(2,1,2) 这样的解决方案在我的输出中 不是 因为它们是多余的。

我正在寻找一种高效 方法来计算堆栈的元组。 我正在处理一个最大 400 的起始堆栈，这个堆栈可以拆分成另一个堆栈，另一个堆栈也可以拆分等等。

是否已有涵盖此问题的参考资料？

我认为用组合术语很容易解决，但这里的问题是，我对可能性本身感兴趣，而不仅仅是可能性的数量！

这里有什么帮助吗？

干杯

Answer 1

消除重复项：

您可以通过对每个组合进行第一个排列来做到这一点。

换句话说，前面的筹码最少。 例如 {1,2,3},{1,3,2},{2,1,3}, {2,3,1},{3,1,2},{3,2,1}

效率：

你可能想用递归来做这件事，所以在每一步你都知道堆栈的可能大小是至少前一个

的大小

您知道以下所有 stackSizes 必须至少为当前大小。所以最大尺寸是剩余的书数除以剩余的书堆数 (floor)。

例如10 本书还剩 3 叠。 floor(10/3) = 3。这是正确的，因为此时剩下的最大组合是 {3,3,4}

因此，这将阻止您进入失败的组合。

代码

import math

def bookStack(cur, min, booksLeft, sizes):
    if len(sizes) == (cur+1):
        sizes[cur] = booksLeft
        print(sizes)
        return;
    max = math.floor(booksLeft / (len(sizes)-cur))+1;
    for take in range(min,max):
        sizes[cur] = take
        bookStack(cur+1, take, booksLeft-take, sizes)

对于超过 3 叠的 5 本书，将其命名为：

bookStack(0,1,5,[0]*3)

Run it here

备注：虽然你想要所有独特的组合，但这仍然是一个快速增长的功能，只适用于少量的堆栈。或者当书堆的数量几乎等于书籍的数量时。你会注意到的。