一对列表中的最小对列表

Question

给定两个整数列表,生成最短的对列表,其中两个列表中的每个值都存在.每对中的第一个必须是第一个列表中的值,每对中的第二个必须是第二个列表中的值.每对中的第一个必须小于该对中的第二个.

zip如果列表长度不同,或者每个列表中的同一位置存在相同的整数,则简单将无效.

def gen_min_pairs(uplist, downlist):
    for pair in zip(uplist, downlist):
        yield pair

到目前为止,我可以提出以下建议:

def gen_min_pairs(uplist, downlist):
    up_gen = iter(uplist)
    down_gen = iter(downlist)

    last_up = None
    last_down = None

    while True:
        next_out = next(up_gen, last_up)
        next_down = next(down_gen, last_down)

        if (next_up == last_up and
            next_down == last_down):
            return

        while not next_up < next_down:
            next_down = next(down_gen, None)
            if next_down is None:
                return
        yield next_up, next_down

        last_up = next_up
        last_down = next_down

这是一个简单的测试程序:

if __name__ == '__main__':
    from pprint import pprint

    datalist = [
        {
            'up': [1,7,8],
            'down': [6,7,13]
        },
        {
            'up': [1,13,15,16],
            'down': [6,7,15]
        }
    ]

    for dates in datalist:    
        min_pairs = [pair for pair in
                     gen_min_pairs(dates['up'], dates['down'])]
        pprint(min_pairs)

该程序为第一组日期生成期望输出,但第二组日期失败.

预期:

[(1, 6), (7, 13), (8, 13)]
[(1, 6), (1, 7), (13, 15)]

实际:

[(1, 6), (7, 13), (8, 13)]
[(1, 6), (13, 15)]

我认为这可以在仅查看每个列表的每个元素时完成,因此在复杂性方面O(len(up) + len(down)).我认为这取决于每个列表唯一的数字元素.

编辑:我应该补充一点,我们可以期望这些列表首先使用最小的整数进行排序.

编辑:uplist并且downlist只是任意名称.不那么混乱的任意人可能是A和B.

此外,这是一个更强大的测试例程:

from random import uniform, sample
from pprint import pprint

def random_sorted_sample(maxsize=6, pop=31):
    size = int(round(uniform(1,maxsize)))
    li = sample(xrange(1,pop), size)
    return sorted(li)

if __name__ == '__main__':
    A = random_sorted_sample()
    B = random_sorted_sample()

    min_pairs = list(gen_min_pairs(A, B))

    pprint(A)
    pprint(B)
    pprint(min_pairs)

这会生成随机的实际输入,计算输出,并显示所有三个列表.以下是正确实现将产生的示例:

[11, 13]
[1, 13, 28]
[(11, 13), (13, 28)]

[5, 15, 24, 25]
[3, 13, 21, 22]
[(5, 13), (15, 21), (15, 22)]

[3, 28]
[4, 6, 15, 16, 30]
[(3, 4), (3, 6), (3, 15), (3, 16), (28, 30)]

[2, 5, 20, 24, 26]
[8, 12, 16, 21, 23, 28]
[(2, 8), (5, 12), (5, 16), (20, 21), (20, 23), (24, 28), (26, 28)]

[3, 4, 5, 6, 7]
[1, 2]
[]

Answer 1

虽然不是完整的答案（即没有代码），但您是否尝试过查看 numpy“where”模块？