Как перебрать два отсортированных списка в наибольшем порядке пар в Python

Если вы не слишком придирчивы к порядку, согласно комментариям, и целью является просто ленивая генерация, которая рассматривает входы «равномерно»: вот простой подход для двух входов. Просто отслеживайте элементы, которые были «увидены» до сих пор из каждого входа, перебирая два входа по кругу (см. также рецепты в документации). С каждым новым элементом выдавайте пары, которые он образует с элементами из другого входа.

Однако, чтобы это работало, нам нужно знать, из какого источника мы извлекаем данные в циклической итерации. Мы могли бы изменить реализацию roundrobin так, чтобы yield эта информация была в какой-то закодированной форме; но я думаю, что для наших целей будет проще просто написать весь алгоритм напрямую, черпая оттуда вдохновение.

Таким образом:

def lazy_pairs(a, b):
    a_seen, b_seen = [], []
    a_active, b_active = True, True
    a_iter, b_iter = iter(a), iter(b)
    while a_active or b_active:
        if a_active:
            try:
                a_next = next(a_iter)
            except StopIteration:
                a_active = False
            else:
                for b_old in b_seen:
                    yield (a_next, b_old)
                a_seen.append(a_next)
        if b_active:
            try:
                b_next = next(b_iter)
            except StopIteration:
                b_active = False
            else:
                for a_old in a_seen:
                    yield (a_old, b_next)
                b_seen.append(b_next)

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

Используя рецепт roundrobin, о котором упомянул Карл (дословно скопировано из рецепты, можно также импортировать его из больше-itertools). Думаю, так будет быстрее, так как вся тяжелая работа выполняется в C-коде различных itertools.

from itertools import repeat, chain, cycle, islice

def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    # Recipe credited to George Sakkis
    num_active = len(iterables)
    nexts = cycle(iter(it).__next__ for it in iterables)
    while num_active:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            # Remove the iterator we just exhausted from the cycle.
            num_active -= 1
            nexts = cycle(islice(nexts, num_active))

def pairs(a, b):
    aseen = []
    bseen = []
    def agen():
        for aa in a:
            aseen.append(aa)
            yield zip(repeat(aa), bseen)
    def bgen():
        for bb in b:
            bseen.append(bb)
            yield zip(aseen, repeat(bb))
    return chain.from_iterable(roundrobin(agen(), bgen()))

a = ['C', 'B', 'A']
b = [3, 2, 1]
print(*pairs(a, b))

Выход (Попробуйте онлайн!):

('C', 3) ('B', 3) ('C', 2) ('B', 2) ('A', 3) ('A', 2) ('C', 1) ('B', 1) ('A', 1)

Тест с двумя итерациями по 2000 элементов в каждой (Попробуйте онлайн!):

 50 ms   50 ms   50 ms  Kelly
241 ms  241 ms  242 ms  Karl

В качестве альтернативы, если две итерации могут повторяться несколько раз, нам не нужно сохранять то, что мы видели (Попробуйте онлайн!):

def pairs(a, b):
    def agen():
        for i, x in enumerate(a):
            yield zip(repeat(x), islice(b, i))
    def bgen():
        for i, x in enumerate(b, 1):
            yield zip(islice(a, i), repeat(x))
    return chain.from_iterable(roundrobin(agen(), bgen()))

(Добавлю в тест позже... Должно быть немного медленнее, чем мое первое решение.)

Экстремальная версия карты/itertools (Попробуйте онлайн!):

def pairs(a, b):
    return chain.from_iterable(roundrobin(
        map(zip,
            map(repeat, a),
            map(islice, repeat(b), count())),
        map(zip,
            map(islice, repeat(a), count(1)),
            map(repeat, b))
    ))