生成器从压缩的iterables中产生间隙元组 [英] Generator to yield gap tuples from zipped iterables

问题描述

假设我有一个任意数量的iterables，所有这些都可以被假定为排序，并包含所有相同类型的元素（整数，为了说明的缘故）。

Let's say that I have an arbitrary number of iterables, all of which can be assumed to be sorted, and contain elements all of the same type (integers, for illustration's sake).

a = (1, 2, 3, 4, 5)
b = (2, 4, 5)
c = (1, 2, 3, 5)

我想编写一个生成函数，产生以下结果：

I would like to write a generator function yielding the following:

(1, None, 1)
(2, 2, 2)
(3, None, 3)
(4, 4, None)
(5, 5, 5)

其他单词，逐步产生带有间隙的排序元组，其中元素从输入迭代中缺失。

In other words, progressively yield sorted tuples with gaps where elements are missing from the input iterables.

推荐答案

我对此的看法，仅使用迭代器，而不是堆：

My take on this, using only iterators, not heaps:

a = (1, 2, 4, 5)
b = (2, 5)
c = (1, 2, 6)
d = (1,)
inputs = [iter(x) for x in (a, b, c, d)]

def minwithreplacement(currents, inputs, minitem, done):
    for i in xrange(len(currents)):
        if currents[i] == minitem:
            try:
                currents[i] = inputs[i].next()
            except StopIteration:
                currents[i] = None
                done[0] += 1
            yield minitem
        else:
            yield None

def dothing(inputs):
    currents = [it.next() for it in inputs]
    done = [0]
    while done[0] != len(currents):
        yield minwithreplacement(currents, inputs, min(x for x in currents if x), done)

print [list(x) for x in dothing(inputs)] #Consuming iterators for display purposes
>>>[[1, None, 1, 1], [2, 2, 2, None], [4, None, None, None], [5, 5, None, None], [None, None, 6, None]]

这篇关于生成器从压缩的iterables中产生间隙元组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！