1

境界内の順列を探している場合に得られる結果の数を教えてくれるアルゴリズムがあるかどうか疑問に思っています。

組み合わせを探すプログラムがあります。説明する最良の方法は、たとえば、店で購入したい商品が 4 つあるとします。リンゴ、桃、ナシ、オレンジです。それぞれをバスケットに入れることができる割合を知りたいのですが、分が欲しいと自分に言い聞かせます。各アイテムの 20 個と各アイテムの最大 60 個 (つまり、apple:25、peach:25、pear:25、および orange:25 は完全に機能しますが、apple:0、peach:0、pear:50、および orange: は機能しません:最小値を 25 に設定しているため、50 です)。この例を実行すると、返されるアイテムの正しい数は 1771 になります。

実際のプログラムを実行する代わりに、これを事前に計算する方法はありますか? premuations を実行する必要があるプログラムがあり、理想的な混合を見つけようとしているので、正しい出力を提供するプログラムを作成したかったので、入力に対してモンテカルロ シミュレーションを実行して混合を見つけます。好きなアイテム/範囲。

これが私が使用したプログラムです（私の場合、トップバンドが使用されていない場合は機能しますが、範囲が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のみを使用します）。しかし、2〜5の範囲の40個のアイテムなど（最大値を良い）。

私が探していることを実行できるアルゴリズムはありますか?

4

1 に答える 1

2

包含排除の原則で数を見つけることができます。をバケットへのアイテムdistributions(itemCount,bucketCount)の無制限配布の数とします。単純にアイテムを差し引くだけなので、下限は無視します。itemCountbucketCountbucketCount*lowerLimit

各バケットが最大アイテムを含むバケットにitemCountアイテムを配布する方法の数は、無制限の配布の数から、少なくとも 1 つのバケットに より多くのアイテムが含まれる無制限の配布の数を差し引いたものです。後者は、次のように包含除外原則を使用して計算できます。bucketCountupperLimitupperLimit

  • bucketCount少なくともアイテムを含むバケットの選択肢があり、バケットに配布するアイテムupperLimit+1が残っています:itemCount - (upperLimit+1)bucketCount

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

    無制限の配布数から差し引く必要があります。

  • しかし、2 つのバケットに 2 回以上のupperLimitアイテムが含まれる分布を差し引いたので、それを修正して追加する必要があります。

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

    nCr(bucketCount,2)繰り返しますが、2 つのバケットの選択肢があるためです。

  • しかし、3 つのバケットに 2 つ以上のupperLimit項目が含まれる分布を 3 回減算し、それを 3 回追加した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 に答える