3

itertools.combinations()整数のタプルを反復処理するために使用しています。

いくつかの条件を満たす最小の合計を持つタプルに興味があります。

def findLowestNiceTuple:
    for tup in itertools.combinations(range(1, 6), 2):
        if niceTuple(tup):
            return tup

ジェネレーターのデフォルトの順序は、要素の合計の順序ではありません。例えば：

>>> itertools.combinations(range(1, 6), 2)

次の要素を生成するジェネレータを提供します。

[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]

ご覧のとおり、(1, 5) の合計は (2,3) の合計よりも大きくなっています。早期終了のために、順番にタプルが必要..., (1, 4), (2, 3), (1, 5), ...です。

組み合わせの数が少ない場合は、次を使用してこれを回避できますsorted()。

>>> sorted(itertools.combinations(range(1, 6), 2), key=sum)
[(1, 2), (1, 3), (1, 4), (2, 3), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]

ただし、sorted()ジェネレーターを完全にメモリに保持されるリストに変換します。これは、もはやうまくスケーリングできないことを意味します。のようなものitertools.combinations(range(1, 600), 400)は必然的にMemoryError.

目的の結果を達成するためのよりメモリに優しい方法はありますか?

PS: 私が言及した最後のシーケンスを完全に繰り返すには何年もかかることを認識していますが、探しているタプルは開始点に非常に近いはずです。そして、注文を当てにすることができれば、最初のスニペットのように早期に終了できます。

4

2 に答える 2

3

これを解決する方法は次のとおりです。合計すると特定の値になるすべての組み合わせを見つける再帰関数を使用します。

def ordered_combinations(pop, n):
    pop = sorted(pop)

    for s in range(sum(pop[:n]), sum(pop[-n:])+1):
        yield from get_sums(pop, s, n)

def get_sums(pop, s, n):
    if n == 1:
        if s in pop:
            yield [s]
        return

    for i, v in enumerate(pop):
        if sum(pop[i:i+n]) > s:
            return
        for rest in get_sums(pop[i+1:], s-v, n-1):
            rest.append(v)
            yield rest

出力の例を次に示します。

>>> for c in ordered_combinations(range(1, 8), 4):
    print(c, sum(c))


[4, 3, 2, 1] 10
[5, 3, 2, 1] 11
[6, 3, 2, 1] 12
[5, 4, 2, 1] 12
[7, 3, 2, 1] 13
[6, 4, 2, 1] 13
[5, 4, 3, 1] 13
[7, 4, 2, 1] 14
[6, 5, 2, 1] 14
[6, 4, 3, 1] 14
[5, 4, 3, 2] 14
[7, 5, 2, 1] 15
[7, 4, 3, 1] 15
[6, 5, 3, 1] 15
[6, 4, 3, 2] 15
[7, 6, 2, 1] 16
[7, 5, 3, 1] 16
[6, 5, 4, 1] 16
[7, 4, 3, 2] 16
[6, 5, 3, 2] 16
[7, 6, 3, 1] 17
[7, 5, 4, 1] 17
[7, 5, 3, 2] 17
[6, 5, 4, 2] 17
[7, 6, 4, 1] 18
[7, 6, 3, 2] 18
[7, 5, 4, 2] 18
[6, 5, 4, 3] 18
[7, 6, 5, 1] 19
[7, 6, 4, 2] 19
[7, 5, 4, 3] 19
[7, 6, 5, 2] 20
[7, 6, 4, 3] 20
[7, 6, 5, 3] 21
[7, 6, 5, 4] 22

組み合わせは常に、最初に最大値で生成されます。これは、それらをリストとして構築する方法のアーティファクトです (前に連結するのではなく、最後に小さな値を追加することによって)。最小から最大の順に並べたい場合は、rest.append(v); yield rest行を に変更できますyield [v]+rest。

コードは、yield fromPython 3.3 で導入された構文を使用します。それをサポートしていない以前のバージョンを使用している場合は、次の同等のコードを使用できます。

for v in get_sums(pop, s, n):
    yield v

コードは、800 のメンバー範囲から取得された 400 の組み合わせの極端なケースを処理することもできます。その計算の最初の 20 個の結果 (残りはすべて同じように 390 から 1 になるため、最大の 10 個の値のみが示されています) とそれらの合計は次のとおりです。

>>> for i, v in enumerate(ordered_combinations(range(1, 800), 400)):
    if i >= 20:
        break
    print(v[:10], sum(v))


[400, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80200
[401, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80201
[402, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80202
[401, 400, 398, 397, 396, 395, 394, 393, 392, 391] 80202
[403, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80203
[402, 400, 398, 397, 396, 395, 394, 393, 392, 391] 80203
[401, 400, 399, 397, 396, 395, 394, 393, 392, 391] 80203
[404, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80204
[403, 400, 398, 397, 396, 395, 394, 393, 392, 391] 80204
[402, 401, 398, 397, 396, 395, 394, 393, 392, 391] 80204
[402, 400, 399, 397, 396, 395, 394, 393, 392, 391] 80204
[401, 400, 399, 398, 396, 395, 394, 393, 392, 391] 80204
[405, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80205
[404, 400, 398, 397, 396, 395, 394, 393, 392, 391] 80205
[403, 401, 398, 397, 396, 395, 394, 393, 392, 391] 80205
[403, 400, 399, 397, 396, 395, 394, 393, 392, 391] 80205
[402, 401, 399, 397, 396, 395, 394, 393, 392, 391] 80205
[402, 400, 399, 398, 396, 395, 394, 393, 392, 391] 80205
[401, 400, 399, 398, 397, 395, 394, 393, 392, 391] 80205
[406, 399, 398, 397, 396, 395, 394, 393, 392, 391] 80206

これは再帰的であるため、1000 の組み合わせを要求すると、このコードは失敗する可能性があります (これは、Python のデフォルトの再帰制限によるものです)。必要に応じて制限を変更できますsys.setrecursionlimit。

get_sumsまた、再帰ステップで人口をスライス (およびコピー) するため、人口が非常に多い場合に非常に深くなると、メモリの問題が発生する可能性があります。このコードで s のみを使用する場合、Python 3 のオブジェクトは効率的にスライスできる (つまり is )ため、 から行をrange削除することでメモリの問題を解決できる可能性があります。pop = sorted(pop)ordered_combinationsrangerange(1,100)[10:]range(11,100)

于 2013-02-14T02:13:01.107 に答える