2

現在、リストから素数のすべての組み合わせとそのサブセットの積を次のように出力しています。

from operator import mul
from itertools import combinations

primes = [2, 3, 5, 7, 11]

for r in range(1,len(primes)):
    for combo in combinations(primes,r+1):
        print combo, reduce(mul, combo)

どの出力

(2,) 2
(3,) 3
(5,) 5
(7,) 7
(11,) 11
(2, 3) 6
(2, 5) 10
(2, 7) 14
(2, 11) 22
(3, 5) 15
(3, 7) 21
(3, 11) 33
(5, 7) 35
(5, 11) 55
(7, 11) 77
(2, 3, 5) 30
(2, 3, 7) 42
(2, 3, 11) 66
(2, 5, 7) 70
(2, 5, 11) 110
(2, 7, 11) 154
(3, 5, 7) 105
(3, 5, 11) 165
(3, 7, 11) 231
(5, 7, 11) 385
(2, 3, 5, 7) 210
(2, 3, 5, 11) 330
(2, 3, 7, 11) 462
(2, 5, 7, 11) 770
(3, 5, 7, 11) 1155
(2, 3, 5, 7, 11) 2310

ここで、次のチャンクを見ているとしましょう。

(2, 5, 7) 70
(2, 5, 11) 110
(2, 7, 11) 154
(3, 5, 7) 105
(3, 5, 11) 165
(3, 7, 11) 231
(5, 7, 11) 385
(2, 3, 5, 7) 210
(2, 3, 5, 11) 330

例として、積が 110 未満のすべての組み合わせを反復処理したいと思います。ここでの最初の「エンドポイント」は、積が 110 であるため、(2,5,11) で発生します。

問題は、この時点で中断すると、長さ 3 のすべてのタプルを中断して (2,3,5,7) に移動しようとしていると見なされ、そうでなければ有効な (3,5,7) がスキップされることです。 ) <110 の積を持つ。一方、この時点で単純に続行すると、時間の無駄になることがわかっている大量のタプルを繰り返し処理することになります。(2, 5, 11) が大きすぎることがわかっている場合、(2, 7, 11) も明らかに大きすぎるため、評価する必要はありません。

私の質問が明確かどうかはわかりませんが、出力の順序が私の構造により一致する組み合わせを生成する別の方法はありますか?

4

1 に答える 1

1

「問題」は、combinationsジェネレーターがr特定の順序で長さのすべてのタプルを発行することです。あなたはそれらが別の順序で来ることを望みます。combinationsしたがって、独自のジェネレーターを作成する必要があります。

これらの種類のジェネレータは通常、再帰的に記述されます: すべてのr長さの組み合わせをiあなたから放出するには、まず 1 つの要素 (最初の要素) を削除(r-1)し、残りからすべての長さの組み合わせを再帰的に放出します。

ここで、不要なタプルを発行しないように、積が大きすぎるとすぐに再帰を停止する必要があります。残念ながら、辞書式順序は「積の増加する順序」と同じではないため、このようなジェネレータの通常の書き方ではそれができません。

つまり、再帰の別の方法、つまり毎回数値の積を増加させる方法を見つけなければならないということです。少し考えれば、次のアルゴリズムにたどり着くはずです。

  • 可能な限り最小のタプルから始めます。
  • タプルのインデックスごとに、次の素数に「バンプアップ」してみてください。場合にのみこれを行います。
    • 製品が制限未満のままであり、かつ
    • タプルはソートされたままです。
  • これにより、開始する新しいタプルが得られるので、それを再帰します。

これは次のように実装できます。

from operator import mul
primes = [2, 3, 5, 7, 11]
primes_inorder = dict(zip(primes, primes[1:]))

def my_combinations(primes, r, N, start=None, prod=None):
    """Yield all sorted combinations of length `r`
       from the sorted list `primes`."""
    if start is None:
        start = primes[:r]
        prod = reduce(mul, start)
        if prod > N: return

    yield start

    for i, v in enumerate(start):
        next_v = primes_inorder.get(v, None)
        if next_v is None or (i+1 < r and next_v > start[i+1]):
            continue

        new_prod = prod / v * next_v
        if new_prod > N:
            continue

        new_start = start[:]
        new_start[i] = next_v
        for combination in my_combinations(primes, r, N, start=new_start, prod=new_prod):
            yield combination
于 2012-04-17T20:28:01.193 に答える