10

これは一般的な組み合わせ論の問題だと思いますが、名前や資料が見つからないようです。私はこれを Python と numpy で行っていますが、これに対する高速なマトリックス メソッドがあれば、おそらく翻訳できます。

基本的に、n 個のアイテムが与えられた場合、それらをm 個のビンに入れるにはすべての方法を生成する必要があります。例として、4 つのアイテムを 3 つのビンにビニングすると、次のようになり[(4, 0, 0), (3, 1, 0), (3, 0, 1), (2, 2, 0), (2, 1, 1), ...]ます。合計金額が決まっている商品です。

これを itertools で実装するのは簡単です。

import itertools

def fixed_total_product(bins, num_items):
""" Return iterator of all item binning possibilities. """
return itertools.ifilter(lambda combo: sum(combo) == num_items,
                         itertools.product(xrange(num_items + 1), repeat=bins))

残念ながら、その後の計算をループで行うのは効率が悪いと思います。これを 2D numpy 配列として使用すると、後で高速になりますが、これを使用して配列を作成する効率的な方法がわかりません。ifilter の結果を反復処理して可能性のリストを作成し、これを使用して配列を作成することもできますが、それは非常に無駄に思えます。

これを行う最善の方法は、すべてを「派手な方法」で構築することだと思いますが、これを行う方法がわかりません。stackoverflow には迅速な製品の実装があります。numpy を使用して、2 つの配列のすべての組み合わせの配列を構築します。これを変更して、正しい合計の製品を出力することしかできないと思います。m-1 個のビン境界があるため、配列のサイズは ((m-1) + n) n を選択する必要があります。

何か案は？ベンチマークは大歓迎ですが、必須ではありません。

4

2 に答える 2

7

再帰 C(n, k) = C(n - 1, k) + C(n - 1, k - 1) に基づいて、numpy 操作を使用してメモ化します。

import numpy as np

def binnings(n, k, cache={}):
    if n == 0:
        return np.zeros((1, k))
    if k == 0:
        return np.empty((0, 0))
    args = (n, k)
    if args in cache:
        return cache[args]
    a = binnings(n - 1, k, cache)
    a1 = a + (np.arange(k) == 0)
    b = binnings(n, k - 1, cache)
    b1 = np.hstack((np.zeros((b.shape[0], 1)), b))
    result = np.vstack((a1, b1))
    cache[args] = result
    return result

if __name__ == '__main__':
    import timeit
    print timeit.timeit('binnings(20, 5, {})', setup='from __main__ import binnings', number=1)

(20, 5) の秒単位の時間:

0.0129251480103
于 2011-07-19T22:30:25.490 に答える
3

numpy でいくつかの異なるトリックを使用するより高速な方法がおそらくあります。numpy.indicesあなたが始めたいところです。itertools.productと組み合わせると、本質的には と同等ですrollaxis。この質問での Sven Marnach の回答は、これの優れた例です (ただし、最後の例には小さなエラーがありますが、これは使用したいものですnumpy.indices((len(some_list) + 1), * some_length...。

ただし、このようなものについては、 itertools を使用すると読みやすくなる可能性があります。

numpy.fromiter特にイテレータ内のアイテム数を指定する場合は、明示的にリストに変換するよりも少し高速です。主な利点は、使用するメモリが大幅に少なくなることです。これは、大きな反復子の場合に非常に役立ちます。

numpy.indicesイテレータをnumpy配列に変換するトリックとさまざまな方法の両方を使用した例を次に示します。

import itertools
import numpy as np
import scipy.special


def fixed_total_product(bins, num_items):
    return itertools.ifilter(lambda combo: sum(combo) == num_items,
            itertools.product(xrange(num_items + 1), repeat=bins))

def fixed_total_product_fromiter(bins, num_items):
    size = scipy.special.binom(bins - 1 + num_items, num_items)
    combinations = fixed_total_product(bins, num_items)
    indicies = (idx for row in combinations for idx in row)
    arr = np.fromiter(indicies, count=bins * int(size), dtype=np.int)
    return arr.reshape(-1, bins)

def fixed_total_product_fromlist(bins, num_items):
    return np.array(list(fixed_total_product(bins, num_items)), dtype=np.int)

def fixed_total_product_numpy(bins, num_items):
    arr = np.rollaxis(np.indices((num_items + 1,) * bins), 0, bins + 1)
    arr = arr.reshape(-1, bins)
    arr = np.arange(num_items + 1)[arr]
    sums = arr.sum(axis=1)
    return arr[sums == num_items]

m, n = 5, 20

if __name__ == '__main__':
    import timeit
    list_time = timeit.timeit('fixed_total_product_fromlist(m, n)',
            setup='from __main__ import fixed_total_product_fromlist, m, n',
            number=1)
    iter_time = timeit.timeit('fixed_total_product_fromiter(m, n)',
            setup='from __main__ import fixed_total_product_fromiter, m, n',
            number=1)
    numpy_time = timeit.timeit('fixed_total_product_numpy(m, n)',
            setup='from __main__ import fixed_total_product_numpy, m, n',
            number=1)

    print 'All combinations of {0} items drawn from a set of {1} items...'.format(m,n)
    print '  Converting to a list and then an array: {0} sec'.format(list_time)
    print '  Using fromiter: {0} sec'.format(iter_time)
    print '  Using numpy.indices: {0} sec'.format(numpy_time)

タイミングについて：

All combinations of 5 items drawn from a set of 20 items...
  Converting to a list and then an array: 2.75901389122 sec
  Using fromiter: 2.10619592667 sec
  Using numpy.indices: 1.44955015182 sec

それらのどれも特に高速ではないことに気付くでしょう。

ブルート フォース アルゴリズムを使用しています (考えられるすべての組み合わせを生成してから、それらをフィルター処理します)。ここで numpy ベースの例にコピーしています。

これを行うには、おそらくもっと効率的な方法があります。ただし、私は決してCSや数学の人ではないので、最初にすべての可能な組み合わせを生成せずにこれを行うためのよく知られたアルゴリズムがあるかどうかはわかりません...

とにかく頑張ってください！

于 2011-07-19T17:40:40.630 に答える