使用边界查找预测数量的算法？

Question

我想知道如果我在范围内寻找排列，是否有一种算法可以告诉我会得到多少结果。

我有一个寻找组合的程序。最好的解释方法是举个例子，假设你有 4 种商品要在商店购买:苹果、桃子、梨和橙子。你想知道你能把每一个放入一个篮子里的百分比是多少，但你告诉自己你想要一分钟。每个项目 20 个，每个项目最多 60 个(因此 apple:25、peach:25、pear:25 和 orange:25 完美但不是 apple:0、peach:0、pear:50 和 orange: 50，因为我们将最小值设置为 25)。如果您运行此示例，则返回的正确项目数为 1771。

有没有办法提前计算这个而不是运行实际的程序？我有一个程序需要进行预测，我正在尝试找到理想的组合，所以我想编写一个程序来提供正确的输出，然后我将对输入进行蒙特卡洛模拟以找到混合我喜欢的项目/范围。

这是我使用的程序(它适用于我从未使用过最高频段的情况，但如果范围更窄，1-4 则它不起作用，因为它在不考虑范围的情况下为我提供了组合):

import math

def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)

if __name__ == '__main__':
    print nCr(20+4-1,20)  #percent+buckets(items)-1, percent

这给了我正确的答案(1771)，因为它不需要考虑最大值(60)，因为它从未达到(它只使用 20 作为输入)。但是有没有一种方法可以修改这个公式(或使用其他方法)来告诉我如果我有 40 个范围为 2-5 的项目或其他东西(最大值为好吧)。

是否有一种算法可以满足我的要求？

Answer 1

你可以用包含排除原则找到这个数字。设 distributions(itemCount,bucketCount) 是 itemCount 项目到 bucketCount 桶的无限制分布的数量。我忽略了下限，因为只需减去 bucketCount*lowerLimit 项即可解决这个问题。

将itemCount项分发到bucketCount个桶中且每个桶最多包含upperLimit个项的方法数是无限制分发的次数减去至少一个桶包含超过 upperLimit 项目的不受限制分布的数量。后者可以用包含排除原则计算如下:

• 有 bucketCount 个选择的桶至少包含 upperLimit+1 个项目，还有 itemCount - (upperLimit+1) 项目分发到 bucketCount 桶:

  bucketCount * distributions(itemCount - (upperLimit+1), bucketCount)
  

  必须从无限制分发的数量中减去。

• 但是我们已经两次减去两个桶包含超过 upperLimit 个项目的分布，我们必须更正它并添加

  nCr(bucketCount,2) * distributions(itemCount - 2*(upperLimit+1), bucketCount)
  

  同样，因为有两个桶的nCr(bucketCount,2)选择。

• 但是我们已经三次减去三个桶包含超过 upperLimit 项目的分布，并再次添加三次 (nCr(3,2))，所以我们必须减去

  nCr(bucketCount,3) * distributions(itemCount - 3*(upperLimit+1), bucketCount)
  

  纠正这一点。等等

总而言之，数是

 m
 ∑ (-1)^k * nCr(bucketCount,k) * distributions(itemCount - k*(upperLimit+1), bucketCount)
k=0

在哪里

m = min { bucketCount, floor(itemCount/(upperLimit+1)) }

(因为无法分发负数的项目)。

通过实现函数来更正要点中的代码，以计算根据下限和上限分配项目的方式:

import math

def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)

def itemCount_cal(target, items, minValue):
    return target- items*minValue

def distributions(itemCount, bucketCount):
    # There's one way to distribute 0 items to any number of buckets: all get 0 items
    if itemCount == 0:
        return 1
    # we can't distribute fewer than 0 items, and we need at least one bucket
    if itemCount < 0 or bucketCount < 1:
        return 0
    # If there's only one bucket, there's only one way
    if bucketCount == 1:
        return 1
    #get all possible solutions
    # The number of ways to distribute n items to b buckets is
    # nCr(n+b-1,n)
    f = math.factorial
    return f(itemCount + bucketCount-1)/(f(itemCount) *  f(bucketCount-1))

def ways(items,buckets,lower,upper):
    if upper < lower: # upper limit smaller than lower: impossible
        return 0
    if buckets*upper < items: # too many items: impossible
        return 0
    necessary = buckets*lower
    if items == necessary:  # just enough items to meet the minimum requirement
        return 1
    if items < necessary:   # too few items: impossible
        return 0
    # put the minimum required number in each bucket, leaving
    # items - necessary
    # to distribute
    left = items - necessary
    # We have put 'lower' items in each bucket, so each bucket can now take
    # at most (upper - lower) more
    # any more, and the bucket is overfull
    over = upper + 1 - lower
    # maximal number of buckets we can put more than upper in at all
    # after we fulfilled the minimum requirement
    m = left // over
    # We start with the number of ways to distribute the items disregarding
    # the upper limit
    ws = distributions(left,buckets)
    # Sign for inclusion-exclusion, (-1)**k
    sign = -1
    # Number of overfull buckets
    k = 1
    while k <= m:
        # Add or subtract the number of ways to distribute
        # 'left' items to 'buckets' buckets with
        # k buckets overfull
        #
        # nCr(buckets,k) choices of the buckets we overfill at the start
        #
        # That leaves (left - k*over) items to distribute.
        ws += sign * nCr(buckets,k) * distributions(left - k*over,buckets)
        # flip sign and increment number of overfull buckets
        sign = -sign
        k += 1
    return ws

请注意，对于大量的项目和桶，使用阶乘计算 nCr 并不是最好的方法，它会导致大量的中间结果并使用不必要的操作。