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

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

Actual:

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

Я думаю, что это можно сделать, только глядя на каждый элемент каждого списка один раз, так что в сложности O(len(up) + len(down)). Я думаю, это зависит от числа элементов, уникальных для каждого списка.

EDIT: Я должен добавить, что мы можем ожидать, что эти списки будут отсортированы с наименьшим целым первым.

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

Пока не полный ответ (т.е. нет кода), вы пробовали смотреть на NumPy «где» модуль?

Answer 2

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

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

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 3

zip_longest называются izip_longest в питоне 2.x.

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