Список минимальных пар из пары списков

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)). Я думаю, что это зависит от количества элементов, уникальных для каждого списка.

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

EDIT: 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

У меня было много идей, чтобы решить эту проблему (см. Историю редактирования; - /), но ни одна из них не сработала и не сделала это за линейное время. Мне потребовалось некоторое время, чтобы увидеть это, но у меня была подобная проблема до , поэтому я действительно хотел выяснить это; -)

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

def intervals(seq):
    seq = iter(seq)
    current = next(seq)
    for s in seq:
        yield current,s
        current = s
    yield s, float("inf")

def gen_min_pairs( fst, snd):
    snd = iter(snd)
    s = next(snd)
    for low, up in intervals(fst):
        while True:
            # does it fall in the current interval
            if low < s <= up:
                yield low, s
                # try with the next
                s = next(snd)
            else:
                # nothing in this interval, go to the next
                break

Answer 2

zip_longest в Python 2.x называется izip_longest.

import itertools    

def MinPairs(up,down):
    if not (up or down):
        return []
    up=list(itertools.takewhile(lambda x:x<down[-1],up))
    if not up:
        return []
    down=list(itertools.dropwhile(lambda x:x<up[0],down))
    if not down:
        return []
    for i in range(min(len(up),len(down))):
        if up[i]>=down[i]:
            up.insert(i,up[i-1])
    return tuple(itertools.zip_longest(up,down,fillvalue=(up,down)[len(up)>len(down)][-1]))

Answer 3

Несмотря на то, что ответы не полные (т. Е. Нет кода), вы пытались взглянуть на обалденный модуль «где»?