複数のリストからpythonの最小範囲

Question

各リストから少なくとも1つの要素を使用して、整数リストのグループから最小の範囲を見つける必要があります。これは3つのリストから値391、395及び398を覆うので、：

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

この例では、最小の範囲は[398 391]であろう。

各リストには、少なくとも1つの値を持つことになり、より多くのリストの範囲を見つけるための最速、計算方法だろう何

があるだろうか？

Answer 1

入力リストがソートされているので、マージソートを使用することができ、マージされる次の値が最後のリストと異なるリストから来たときに範囲をテストするだけで済みます。各リストで最後に確認した値を追跡し、最も低い値と現在の値の範囲を計算します。これはO(N)線形時間アプローチです。ここで、Nはすべての入力リストの要素の合計数です。

アプローチ次実装：

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 

デモ：リストは、多くの/大得るが、それはリストが事前にソートされた入力を負いませんので、このソリューションはかなり遅くなり

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

：

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

USAGE：

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

PRINTS：

（391、398）