1

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

我有一个寻找组合的程序。最好的解释方式是举个例子，假设您有 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 的项目或其他东西（将最大值考虑在内的东西）会有多少结果好）。

有没有可以做我正在寻找的算法？

4

1 回答 1

2

您可以根据包含排除原则找到数字。让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使用阶乘计算不是最好的方法，它会导致大量的中间结果并使用不必要的操作。

于 2012-05-29T16:23:41.750 回答