如何以 Python 中的最大对顺序遍历两个排序列表

Question

我有两个排序的可迭代对象，例如：

a = [C, B, A]
b = [3, 2, 1]

我想生成所有可能对的列表，首先组合最大（最低索引）对。最大意味着元素 < 1 的所有组合首先（对于两个可迭代对象），然后是索引 < 2 的所有组合，等等。期望的结果：

combine(a, b)
>> ((C, 3), (B, 3), (C, 2), (B, 2), (A, 3), (A, 2), (C, 1), (B, 1), (A, 1))

我查看了 itertools.product()，但这会以错误的顺序生成对。

由于输入是可迭代的（不一定是列表），我更喜欢可以处理可迭代的库函数。可迭代对象可能很长（数百万个元素），因此最好避免将它们全部存储在内存中。同理，生成顺序错误再排序也是不可取的。

输出应该是一个生成器，这样即使不是所有组合都需要，也不必遍历所有组合。

Answer 1

如果您对顺序不太挑剔，根据评论，目标只是“均匀”考虑输入的惰性生成：这是两个输入的简单方法。只需跟踪到目前为止从每个输入“看到”的元素，同时迭代两个输入 in round-robin fashion (also see the recipes in the documentation)。对于每个新元素，产生它与来自其他输入的元素的对。

不过，为了实现这一点，我们需要知道我们在 round-robin 迭代中从哪个源中提取数据。我们可以修改 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 来查找涉及刚刚从一个输入中获取的元素并从所有其他输入中看到的元素的所有可能性。）

Answer 2

使用 Karl 提到的 roundrobin 食谱（从 recipes, could also import it from more-itertools 逐字复制）。我认为这会更快，因为所有艰苦的工作都是在各种 itertools 的 C 代码中完成的。

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))

输出（Try it online!）：

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

具有两个 2000 个元素的可迭代对象的基准 (Try it online!)：

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

或者，如果两个可迭代对象可以迭代多次，我们不需要保存我们已经看到的(Try it online!):

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()))

（稍后将添加到基准测试中......应该比我的第一个解决方案慢一点。）

一个极端的 map/itertools 版本 (Try it online!):

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))
    ))

如何以 Python 中的最大对顺序遍历两个排序列表

How to iterate over two sorted lists in largest pairs order in Python

python

iterator

itertools