拆分B的可能性

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}

效率：

您可能希望通过递归实现这一点，因此在每一步中，您都知道堆栈的可能大小至少是前一步的大小

您知道以下所有堆栈大小必须至少为当前大小。因此，最大大小是剩余的图书数量除以剩余的书堆数量（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

备注：尽管您需要所有独特的组合，但这仍然是一个快速增长的函数，只适用于少量堆栈。或者当书堆的数量几乎等于书的数量时。你会注意到的。你知道吗