Python najmniejszy zakres z wielu list

Question

Potrzebuję znaleźć najmniejszy zakres z grupy list całkowitych za pomocą co najmniej jednego elementu z każdej listy.

list1=[228, 240, 254, 301, 391] 
list2=[212, 345, 395] 
list3=[15, 84, 93, 103, 216, 398, 407, 488] 

W tym przykładzie najmniejszy zakres byłby [391: 398], ponieważ obejmuje wartości 391, 395 i 398 z trzech list.

Każda lista będzie miała co najmniej jedną wartość i nie może być wiele więcej wykazów

Jaki byłby najszybszym sposobem na znalezienie obliczeniowo zakres?

Answer 1

Ponieważ listy wejściowe są sortowane, można użyć sortowania scalonego i wystarczy przetestować zakres, gdy następna wartość, która jest łączona, pochodzi z innej listy niż poprzednia. Śledź ostatnią wyświetloną wartość na każdej z list i oblicz zakresy między najniższą wartością a bieżącą. Jest to metoda liniowa czasu O(N), gdzie N to całkowita liczba elementów wszystkich list wejściowych.

następujące narzędzia takie podejście:

def smallest_range(*lists): 
    iterables = [iter(it) for it in lists] 
    iterable_map = {} 
    for key, it in enumerate(iterables): 
     try: 
      iterable_map[key] = [next(it), key, it] 
     except StopIteration: 
      # empty list, won't be able to find a range 
      return None 
    lastvalues, lastkey = {}, None 
    candidate, candidatediff = None, float('inf') 

    while iterable_map: 
     # get the next value in the merge sort 
     value, key, it = min(iterable_map.values()) 
     lastvalues[key] = value 

     if len(lastvalues) == len(lists) and lastkey != key: 
      minv = min(lastvalues.values()) 
      difference = value - minv 
      if candidatediff > difference: 
       candidate, candidatediff = (minv, value), difference 
     lastkey = key 

     try: 
      iterable_map[key][0] = next(it) 
     except StopIteration: 
      # this iterable is empty, remove it from consideration 
      del iterable_map[key] 

    return candidate 

Demo:

>>> list1 = [228, 240, 254, 301, 391] 
>>> list2 = [212, 345, 395] 
>>> list3 = [15, 84, 93, 103, 216, 398, 407, 488] 
>>> smallest_range(list1, list2, list3) 
(391, 398) 

Answer 2

Rozwiązanie to znacznie spowalnia jak wykazy uzyskać duży/wielu, ale nie zakładamy wejście listy są presorted:

from itertools import product 

def smallest_range(*arrays): 

    result = min((sorted(numbers) for numbers in product(*arrays)), key=lambda n: abs(n[0] - n[-1])) 

    return (result[0], result[-1]) 

list1 = [228, 240, 254, 301, 391] 
list2 = [212, 345, 395] 
list3 = [15, 84, 93, 103, 216, 398, 407, 488] 

print(smallest_range(list1, list2, list3)) 

ZASTOSOWANIE:

list1 = [228, 240, 254, 301, 391] 
list2 = [212, 345, 395] 
list3 = [15, 84, 93, 103, 216, 398, 407, 488] 

print(smallest_range(list1, list2, list3)) 

wyświetli:

(391, 398)