Ответ 1

import heapq
import itertools
import operator


def increasing(fn, left, right):
    """
    Given two never decreasing iterators produce another iterator
    resulting from passing the value from left and right to fn.
    This iterator should also be never decreasing.
    """
    # Imagine an infinite 2D-grid.
    # Each column corresponds to an entry from right
    # Each row corresponds to an entry from left
    # Each cell correspond to apply fn to those two values

    # If the number of columns were finite, then we could easily solve
    # this problem by keeping track of our current position in each column
    # in each iteration, we'd take the smallest value report it, and then
    # move down in that column. This works because the values must increase
    # as we move down the column. That means the current set of values
    # under consideration must include the lowest value not yet reported

    # To extend this to infinite columns, at any point we always track a finite
    # number of columns. The last column current tracked is always in the top row
    # if it moves down from the top row, we add a new column which starts at the top row
    # because the values are increasing as we move to the right, we know that
    # this last column is always lower then any columns that come after it





    # Due to infinities, we need to keep track of all
    # items we've ever seen. So we put them in this list
    # The list contains the first part of the incoming iterators that
    # we have explored
    left_items = [next(left)]
    right_items = [next(right)]

    # we use a heap data structure, it allows us to efficiently
    # find the lowest of all value under consideration
    heap = []

    def add_value(left_index, right_index):
        """
        Add the value result from combining the indexed attributes
        from the two iterators. Assumes that the values have already
        been copied into the lists
        """
        value = fn( left_items[left_index], right_items[right_index] )
        # the value on the heap has the index and value.
        # since the value is first, low values will be "first" on the heap
        heapq.heappush( heap, (value, left_index, right_index) )

    # we know that every other value must be larger then 
    # this one. 
    add_value(0,0)

    # I assume the incoming iterators are infinite
    while True:
        # fetch the lowest of all values under consideration
        value, left_index, right_index = heapq.heappop(heap)

        # produce it
        yield value

        # add moving down the column
        if left_index + 1 == len(left_items):
            left_items.append(next(left))

        add_value(left_index+1, right_index)

        # if this was the first row in this column, add another column
        if left_index == 0:
            right_items.append( next(right) )
            add_value(0, right_index+1)






def fib():
    a = 1
    b = 1
    while True:
        yield a
        a,b = b,a+b



r = increasing(operator.add, fib(), itertools.count() )
for x in range(100):
    print next(r)

Ответ 2

Определите последовательности как:

a1 <= a2 <= a3 ...
b1 <= b2 <= b3 ...

Пусть a1b1 означает op(a1,b1) для краткости.

Основываясь на ваших допустимых предположениях (очень важно), вы знаете следующее:

max(a1, b1) <= a1b1 <= a1b2 <= a1b3 ...
   <=
max(a2, b1) <= a2b1 <= a2b2 <= a2b3 ...
   <=
max(a3, b1) <= a3b1 <= a3b2 <= a3b3 ...
    .     .
    .      .
    .       .

Вам нужно будет сделать что-то вроде:

Создать a1b1. Вы знаете, что если вы продолжите увеличивать переменные b, вы получите только более высокие значения. Теперь вопрос: есть ли меньшее значение, увеличивая переменные a? Ваша нижняя граница min(a1, b1), поэтому вам нужно увеличить значения a до min(ax,b1) >= a1b1. Как только вы нажмете эту точку, вы можете найти наименьшее значение из anb1 где 1 <= n <= x и обеспечить это безопасно.

Тогда у вас будет несколько горизонтальных цепей, которые вам нужно будет отслеживать. Каждый раз, когда у вас есть значение, которое проходит мимо min(ax,b1), вам нужно увеличить x (добавив больше цепей) до тех пор, пока min(ax,b1) не станет больше, чем безопасно его испускать.

Просто отправная точка... У меня нет времени, чтобы закодировать ее в данный момент.

РЕДАКТИРОВАТЬ: О, это то, что у вас уже было. Ну, без дополнительной информации, это все, что вы можете сделать, так как я уверен, что математически это необходимо.

EDIT2: Что касается вашего "приемлемого" решения: вы можете просто получить a1bn в порядке возрастания n, возвращая min(a1,b1) как n= P. Вы должны быть более конкретными. Вы говорите так, как будто у вас есть эвристика того, что вы обычно хотите видеть, общий способ, которым вы хотите продвигаться по обоим итерам, но не сообщая нам, что это такое, я не знаю, как можно сделать лучше.

UPDATE: Уинстон хорош, но делает предположение, что плакат не упомянул: op(a,c) > op(b,c), если b>a. Однако мы знаем, что op(a,b)>=a и op(a,b)>=b.

Вот мое решение, которое принимает второе предположение, но не тот, который взял Уинстон. Тем не менее, реквизит для него структуры кода:

def increasing(fn, left, right):
    left_items = [next(left)]
    right_items = [next(right)]

    #columns are (column value, right index)
    columns = [(fn(left_items[0],right_items[0]),0)]

    while True:
        #find the current smallest value
        min_col_index = min(xrange(len(columns)), key=lambda i:columns[i][0])

        #generate columns until it impossible to get a smaller value
        while right_items[0] <= columns[min_col_index][0] and \
              left_items[-1] <= columns[min_col_index][0]:
            next_left = next(left)

            left_items.append(next_left)
            columns.append((fn(next_left, right_items[0]),0))

            if columns[-1][0] < columns[min_col_index][0]:
                min_col_index = len(columns)-1

        #yield the smallest value
        yield columns[min_col_index][0]

        #move down that column
        val, right_index = columns[min_col_index]

        #make sure that right value is generated:
        while right_index+1 >= len(right_items):
            right_items.append(next(right))

        columns[min_col_index] = (fn(left_items[min_col_index],right_items[right_index+1]),
                                  right_index+1)
        #repeat                

Для (патологического) ввода, который демонстрирует разницу, рассмотрите:

def pathological_one():
    cur = 0
    while True:
        yield cur
        cur += 100

def pathological_two():
    cur = 0
    while True:
        yield cur
        cur += 100

lookup = [
    [1,   666, 500],
    [666, 666, 666],
    [666, 666, 666],
    [666, 666, 666]]

def pathological_op(a, b):
    if a >= 300 or b >= 400: return 1005
    return lookup[b/100][a/100]

r = increasing(pathological_op, pathological_one(), pathological_two())
for x in range(15):
    print next(r)

Ответ Winston дает:

>>> 
1
666
666
666
666
500
666
666
666
666
666
666
1005
1005
1005

Пока мой дает:

>>> 
1
500
666
666
666
666
666
666
666
666
666
666
1005
1005
1005

Ответ 3

Итак, вы в основном хотите взять две монотонно возрастающие последовательности, а затем (лениво) вычислить таблицу умножения (или добавление или другую операцию) между ними, которая представляет собой двухмерный массив. Затем вы хотите поместить элементы этого 2-D массива в отсортированный порядок и выполнить итерацию через них.

В общем, это невозможно. Однако, если ваши последовательности и операции таковы, что вы можете получить определенные гарантии относительно строк и столбцов таблицы, вы можете добиться определенного прогресса. Например, допустим, что ваши последовательности являются монотонно возрастающими последовательностями только положительных целых чисел и что операция является умножением (как в вашем примере). В этом случае мы знаем, что каждая строка и столбец массива является монотонно возрастающей последовательностью. В этом случае вам не нужно вычислять весь массив, а только его части. В частности, вы должны отслеживать следующее:

• Сколько строк вы когда-либо использовали
• Количество элементов, которые вы выбрали из каждой используемой строки
• Каждый элемент из любой входной последовательности, которую вы когда-либо использовали, плюс еще один из каждого

Чтобы вычислить следующий элемент в вашем итераторе, вы должны сделать следующее:

• Для каждой строки, которую вы когда-либо использовали, вычислите значение "next" в этой строке. Например, если вы использовали 5 значений из строки 1, тогда вычислите 6-е значение (i = 1, j = 6), взяв 1-е значение из первой последовательности и 6-е значение из второй последовательности (обе из которых у вас есть кэшируется) и применяет к ним операцию (умножение). Кроме того, вычислите первое значение в первой неиспользуемой строке.
• Возьмите минимум всех вычисленных значений. Допустим это значение в качестве следующего элемента в вашем итераторе.
• Увеличьте счетчик для строки, из которой вы выбрали элемент на предыдущем шаге. Если вы взяли элемент из новой неиспользуемой строки, вы должны увеличить счетчик количества строк, которые вы использовали, и вы должны создать новый счетчик для этой строки, инициализированной до 1. При необходимости вы также должны вычислить больше значений одна или обе входные последовательности.

Этот процесс является довольно сложным и, в частности, замечает, что для вычисления значений N вы должны в худшем случае сохранить количество состояний, пропорциональное квадрату корня N. (Изменить: sqrt (N) на самом деле является лучшим случаем.) Это резко контрастирует с типичным генератором, который требует только постоянного пространства для итерации через его элементы независимо от длины.

Таким образом, вы можете сделать это при определенных предположениях, и вы можете предоставить ему подобный генератору интерфейс, но это невозможно сделать "потоковым" способом, поскольку вам нужно сохранить много состояний, чтобы итерации через элементы в правильном порядке.

Ответ 4

Позвольте мне начать с примера, как я буду решать это интуитивно.

Поскольку чтение кода inline немного утомительно, я введу некоторые обозначения:

нотации

• i1 будет представлять iter1. i1 ₀ будет представлять первый элемент iter1. То же самое для iter2.
• ※ будет представлять оператор op

Интуитивное решение

Используя упрощающее предположение 2, мы знаем, что i1 ₀ ※ i2 ₀ - наименьший элемент, который когда-либо будет получен из вашего окончательного итератора. Следующий элемент будет меньше i1 ₀ ※ i2 ₁ и i1 ₁ ※ i2 ₀.

Предполагая, что i1 ₀ ※ i2 ₁ меньше, вы получите этот элемент. Затем вы получите меньше i1 ₁ ※ i2 ₀, i1 ₁ ※ i2 ₀, а i1 ₁ ※ i2 ₁.

Выражение как обход DAG

У вас здесь проблема обхода графика. Во-первых, подумайте о проблеме как о дереве. Корнем дерева является i1 ₀ ※ i2 ₀. Этот node, и каждый node ниже него имеет двух детей. Двумя дочерними элементами i1 _x ※ i2 _y являются следующие: Один из них - i1 _{x + 1} ※ i2 _y, а другой - i1 _x ※ i2 _{y + 1}. Исходя из вашего второго предположения, мы знаем, что i1 _x ※ i2 _y меньше, чем оба его дочерних элемента.

(Фактически, как упоминает Райан в комментарии, это ориентированный ациклический граф или DAG. Некоторые "родители" делят "дети" с другими "родительскими" узлами.)

Теперь нам нужно сохранить границу - набор узлов, которые могут быть возвращены. После возврата node мы добавим его дочерние элементы на границу. Чтобы выбрать следующий node для посещения (и возврата из вашего нового итератора), мы сравниваем значения всех узлов на границе. Мы берем node с наименьшим значением и возвращаем его. Затем мы снова добавляем оба его дочерних узла к границе. Если ребенок уже находится на границе (добавлен как дочерний элемент какого-либо другого родителя), просто игнорируйте его.

Сохранение границы

Поскольку вы в первую очередь заинтересованы в значении узлов, имеет смысл хранить эти узлы, индексированные по значению. Таким образом, может потребоваться использование dict. Ключами в этом dict должны быть значения узлов. Значения в этом dict должны быть списками, содержащими отдельные узлы. Поскольку единственной идентифицирующей информацией в node является пара операндов, вы можете сохранить отдельные узлы в виде двухкортежей операндов.

На практике после нескольких итераций ваша граница может выглядеть следующим образом:

>>> frontier
{1: [(2, 3), (2, 4)], 2: [(3, 5), (5, 4)], 3: [(1, 6)], 4: [(6, 3)]}

Другие примечания по реализации

Поскольку итераторы не поддерживают произвольный доступ, вам нужно будет придерживаться значений, созданных вашими двумя итераторами, до тех пор, пока они больше не понадобятся. Вы узнаете, что значение все еще необходимо, если на него ссылаются любые значения на вашей границе. Вы узнаете, что значение больше не требуется, если все узлы в пограничных опорных значениях позже/больше, чем вы сохранили. Например, i1 ₂₀ больше не требуется, если только узлы в вашей пограничной ссылке i1 ₂₁, i1 ₂₅, i1 ₃₃,...

Как упоминалось Райаном, каждое значение от каждого итератора будет использоваться бесконечно много раз. Таким образом, каждое полученное значение нужно будет сохранить.

Непрактично

К сожалению, чтобы гарантировать, что элементы возвращаются только в порядке возрастания, граница будет расти без ограничений. Ваши мемуаризованные значения , вероятно, также занимают значительное количество места, также растут без ограничений. Это может быть то, что вы можете решить, сделав вашу проблему менее общей, но это должно быть хорошей отправной точкой.

Ответ 5

Используйте generators, которые являются просто итераторами, написанными как функции, которые дают результаты. В этом случае вы можете написать генераторы для iter1 и iter2 и другого генератора, чтобы обернуть их и дать свои результаты (или выполнить вычисления с ними или историю их результатов) по ходу.

Из моего чтения вопроса вы хотите что-то вроде этого, которое будет вычислять каждый элемент первого итератора с каждым элементом следующего, используя указанную операцию, вы также заявляете, что хотите каким-то образом обернуть "iter1", "iter2" и "op" в итерабельном, что само по себе дает значения в монотонно возрастающем выходе. Я предлагаю генераторы предложить простое решение этой проблемы.

import itertools

def prime_gen():
    D, q = {}, 2
    while True:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q += 1

def infinite_gen(op, iter1, iter2):
    while True:
        yield op(iter1.next(), iter2.next())

>>> gen = infinite_gen(operator.mul, prime_gen(), itertools.count())

>>> gen.next()
<<< 0

>>> gen.next()
<<< 3

>>> gen.next()
<<< 10

Генераторы предлагают большую гибкость, поэтому довольно легко написать iter1 и iter2 в качестве генераторов, которые возвращают нужные значения в том порядке, в котором вы хотите. Вы также можете использовать сопрограммы, которые позволяют отправлять значения в генератор.

Ответ 6

Обсуждение в других ответах указывает, что существует потенциально бесконечное хранилище, независимо от того, какой алгоритм, так как каждый a[n] должен оставаться доступным для каждого нового b[n]. Если вы удалите ограничение на то, что на входе должно быть два итератора, и вместо этого требуется только, чтобы они были последовательностями (индексируемыми или просто тем, что может быть повторно регенерировано), я полагаю, что все ваше состояние внезапно падает до одного числа: последнее значение, которое вы вернули. Зная последнее значение результата, вы можете искать выходное пространство в поисках следующего. (Если вы хотите правильно выбрасывать дубликаты, вам может потребоваться также отслеживать, сколько раз результат был возвращен)

С парой последовательностей у вас есть простое рекуррентное соотношение:

result(n) = f(seq1, seq1, result(n-1))

где f(seq1, seq1, p) выполняет поиск минимального значения в выходном пространстве q так, что q > p. С практической точки зрения, вы, вероятно, создадите последовательности memoized функций и выберите свой алгоритм поиска, чтобы избежать избиения пула memoized элементов.