5

配列があり、その長さはXです。配列の各要素には range があります1 .. L。sum を持つすべての配列の組み合わせを効率的に反復処理したいと考えていLます。

正しい解: L = 4 および X = 2

1 3
3 1
2 2

正しい解: L = 5 および X = 3

1 1 3
1 3 1
3 1 1
1 2 2
2 1 2
2 2 1

単純な実装は、私の問題には (当然のことながら) 遅すぎます (私の場合、X は最大 8 で、L は最大 128 です)。

この問題がどのように呼ばれているか、または問題の高速なアルゴリズムを見つける場所を誰か教えてもらえますか?

ありがとう！

4

1 に答える 1

9

私の理解が正しければ、2 つの数値 1 ≤ X ≤ Lが与えられ、合計がLになる長さXの正の整数のすべてのシーケンスを生成したいとします。

(注: これは整数分割問題に似ていますが、1,2,2 は 2,1,2 とは異なるシーケンスであると見なされるため、同じではありませんが、整数分割問題では順序を無視するため、これらは同じパーティションと見なされます。)

あなたが探している数列は、 L − 1 のうちX  − 1 個の組み合わせに対応します。たとえば、1 からL − 1 までの数字を並べてX − 1 個 を選ぶと 、区間の長さは選択された数値の間は、合計がLになる正の整数です。

たとえば、Lが 16 でXが 5 だとします。次に、1 から 15 までの 4 つの数字を選択します。

1から15までの中から3、7、8、14の4つの数字を選ぶ

最初に 0 を追加し、最後に 16 を追加すると、間隔は次のようになります。

間隔 0 ～ 3、3 ～ 7、7 ～ 8、8 ～ 14、14 ～ 16

必要に応じて、3 + 4 + 1 + 6 + 2 = 16。

L − 1 個からX  − 1 個の組み合わせを生成し 、それぞれについて間隔を求めてパーティションに変換します。たとえば、Python では次のように記述できます。

from itertools import combinations

def partitions(n, t):
    """
    Generate the sequences of `n` positive integers that sum to `t`.
    """
    assert(1 <= n <= t)
    def intervals(c):
        last = 0
        for i in c:
            yield i - last
            last = i
        yield t - last
    for c in combinations(range(1, t), n - 1):
        yield tuple(intervals(c))

>>> list(partitions(2, 4))
[(1, 3), (2, 2), (3, 1)]
>>> list(partitions(3, 5))
[(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)]

( L  − 1) 個あります! / ( X  − 1)!( L  − <em>X)! L − 1 のうちX  − 1 項目の組み合わせである ため、このアルゴリズムの実行時間 (およびその出力のサイズ) はLで指数関数的です。ただし、出力をカウントしない場合、必要なのは O( L ) スペースだけです。

L  = 128、X = 8 の場合、 89,356,415,775 個のパーティションがあるため、すべてを出力するには時間がかかります。

(これらのパーティションを計算している理由を説明していただければ、実際にすべてを作成しなくても要件を満たす方法を提案できるかもしれません。)

于 2012-12-21T13:11:54.713 に答える