4

私は 2 つのジェネレーターを持ってgenAおりgenB、それぞれが厳密に単調に増加する無限の整数シーケンスを生成します。

ここで、すべてのタプルを生成するジェネレーターが必要です。これは、によって生成(a, b)さaれgenA、およびbによって生成されgenB、昇順a < bで並べられます。a + bあいまいな場合、順序は重要ではありません。つまり、最初に生成されるか最初a + b == c + dに生成されるかは問題ではありません。(a, b)(c, d)

例えば。と の両方が素数genAを生成する場合、新しいジェネレーターは以下を生成する必要があります。genB

(2, 3), (2, 5), (3, 5), (2, 7), (3, 7), (5, 7), (2, 11), ...

genAとが有限のリストである場合genB、圧縮してから並べ替えるとうまくいきます。

どうやら、フォームのすべてのタプルについて(x, b)次のことが成り立ちます:first(genA) <= x <= max(genA,b) <= bは、first(genA)によって生成された最初の要素であり、 によって生成されgenAたmax(genA,b)最後の要素genAは 未満ですb。

これが私が得た距離です。説明されている方法で2つのジェネレーターを組み合わせる方法のアイデアはありますか?

4

1 に答える 1

2

からのすべての結果を保存せずにこれを行うことは不可能だと思いますgenA。解決策は次のようになります。

import heapq
def gen_weird_sequence(genA, genB):
    heap = []
    a0 = next_a = next(genA)
    saved_a = []
    for b in genB:
        while next_a < b:
            saved_a.append(next_a)
            next_a = next(genA)
        # saved_a now contains all a < b
        for a in saved_a:
            heapq.heappush(heap, (a+b, a, b)) #decorate pair with sorting key a+b
        # (minimum sum in the next round) > b + a0, so yield everything smaller
        while heap and heap[0][0] <= b + a0:
            yield heapq.heappop(heap)[1:] # pop smallest and undecorate

説明: メイン ループは、 内のすべての要素を単純に反復し、 からより小さいgenBすべての要素を取得し、それらをリストに保存します。次に、すべてのタプルを生成し、それらをmin-heapに格納します。これは、コレクションの最小値のみを抽出することに関心がある場合に効率的なデータ構造です。タプル間の比較は最初の項目の比較から始まるため、並べ替えと同様に、ペア自体を保存せずに、並べ替えたい値 ( ) を先頭に追加するというトリックを実行できます。最後に、すべての要素をヒープからポップして、その合計が次の生成されたペアの合計よりも小さいことが保証され、それらを生成します。genAb(a0, b), (a1, b), ..., (a_n, b)a+bb

heap結果を生成している間、 との両方が増加することに注意してくださいsaved_a。これまでに生成された要素の数の平方根に比例すると思います。

いくつかの素数を使った簡単なテスト:

In [2]: genA = (a for a in [2,3,5,7,11,13,17,19])
In [3]: genB = (b for b in [2,3,5,7,11,13,17,19])
In [4]: for pair in gen_weird_sequence(genA, genB): print pair
(2, 3)
(2, 5)
(3, 5)
(2, 7)
(3, 7)
(5, 7)
(2, 11)
(3, 11)
(2, 13)
(3, 13)
(5, 11)
(5, 13)
(7, 11)
(2, 17)
(3, 17)
(7, 13)

予想通り。無限発生器でテストする:

In [11]: from itertools import *
In [12]: list(islice(gen_weird_sequence(count(), count()), 16))
Out[12]: [(0, 1), (0, 2), (0, 3), (1, 2), (0, 4), (1, 3), (0, 5), (1, 4),
          (2, 3), (0, 6), (1, 5), (2, 4), (0, 7), (1, 6), (2, 5), (3, 4)]
于 2013-10-18T20:25:43.750 に答える