Lista de pares mínimos de un par de listas

Question

Dadas dos listas de enteros, genere la lista más corta de pares donde cada valor en ambas listas esté presente. El primero de cada par debe ser un valor de la primera lista, y el segundo de cada par debe ser un valor de la segunda lista. El primero de cada par debe ser menor que el segundo del par.

Un simple zip no funcionará si las listas son de diferentes longitudes, o si existe el mismo número entero en la misma posición en cada lista.

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

Aquí es lo que puedo llegar a hasta el momento:

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 

Y aquí es una sencilla rutina de prueba:

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) 

El programa produce la salida de esperar que para el primer conjunto de fechas, pero falla para el segundo.

esperado:

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

real:

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

creo que esto se puede hacer mientras que sólo mirar a cada elemento de cada lista de una vez, por lo que en la complejidad O(len(up) + len(down)). Creo que depende de los elementos numéricos exclusivos de cada lista.

EDITAR: Debería añadir que podemos esperar que estas listas se ordenen primero con el número entero más pequeño.

EDIT: uplist y downlist eran solo nombres arbitrarios. Los arbitrarios menos confusos pueden ser A y B.

Además, aquí es una más robusta rutina de prueba:

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) 

Esto genera entradas realistas al azar, calcula la salida, y muestra las tres listas. He aquí un ejemplo de lo que produciría una implementación correcta:

[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

Aunque no es un completo respuestas (es decir, sin código), ¿ha intentado mirar el numpy "donde" módulo?

Answer 2

Tuve muchas ideas para resolver esto (ver el historial de edición; - /) pero ninguna de ellas funcionó o lo hizo en tiempo lineal. Me tomó un tiempo verlo, pero tenía a similar problem before, así que realmente quería resolver esto ;-)

De todos modos, al final la solución llegó cuando dejé de hacerlo directamente y comencé a dibujar gráficos sobre la emparejamientos Creo que su primera lista simplemente define intervalos y que está buscando para los artículos que caen en ellas:

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 se llama izip_longest en 2.x. pitón

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