我想知道是否有一个算法告诉我，如果我在边界内寻找排列，我会得到多少结果。
我有一个寻找组合的程序。最好的解释方法就是举个例子，比如说你有四样东西想在商店里买：苹果、桃子、梨和橘子你想知道一个篮子能装下多少百分比，但你告诉自己你想要每件物品最少20个，最多60个（所以苹果：25个，桃子：25个，梨：25个，橘子：25个效果很好，但苹果：0个，桃子：0个，梨：50个，橘子：50个，因为我们把最小值设为25个）如果运行此示例，则返回的正确项数为1771。
有没有办法提前计算而不是运行实际的程序？我有一个需要做预评估的程序，我正试图找到理想的组合，所以我想写一个程序，给我正确的输出，然后我将对输入进行蒙特卡罗模拟，以找到我喜欢的项目/范围的组合。
这是我使用的程序（在我的情况下，当不使用最上面的波段时，它可以工作，但是如果范围是tigher，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之间，或者其他什么（也可以考虑最大值）。
有没有一种算法可以做到我想要的？
最佳答案
你可以用包含排除原理找到这个数字。设distributions(itemCount,bucketCount)为itemCount项到bucketCount存储桶的无限制分布数我忽略了下限，因为这只是通过减去bucketCount*lowerLimit项来处理的。
将itemCount项分发到bucketCount个bucket（每个bucket最多包含upperLimit项）的方法数是无限制分发数减去至少一个bucket包含多于upperLimit项的无限制分发数。后者可采用包含排除原则计算如下：
有bucketCount选择的存储桶至少包含upperLimit+1项，还有itemCount - (upperLimit+1)项要分发到bucketCount存储桶：
bucketCount * distributions(itemCount - (upperLimit+1), bucketCount)
必须从不受限制的分发数中减去。
但是我们已经两次减去了两个bucket包含大于
upperLimit项的分布，我们必须修正它并加上nCr(bucketCount,2) * distributions(itemCount - 2*(upperLimit+1), bucketCount)
同样，因为有两个bucket的选择。
但是，我们已经将三个bucket包含超过
nCr(bucketCount,2)项的分布减去了三次，然后再加上三次（upperLimit），所以我们必须减去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
注意，对于大量的项和bucket，使用factorial计算
nCr(3,2)并不是最好的方法，它会导致大量的中间结果，并且使用的操作比必要的多。