अजगर एकाधिक सूचियों

Question

से छोटी से छोटी रेंज मैं प्रत्येक सूची में से कम से कम एक तत्व का उपयोग कर पूर्णांक सूचियों के एक समूह से छोटी से छोटी रेंज खोजने की जरूरत है। ,: [398 391] क्योंकि यह मान 391, 395 और 398 तीन सूचियों से शामिल किया गया है

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

इस उदाहरण में छोटी से छोटी रेंज होगा।

प्रत्येक सूची कम से कम एक मूल्य है और वहाँ कई और अधिक सूचियों

श्रृंखला मिल का सबसे तेज computationally तरीका होगा क्या हो सकता है?

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

यह समाधान नीचे काफी धीमा कर देती है के रूप में सूचियों बड़े/कई मिलता है, लेकिन यह इनपुट सूचियों 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)) 

उपयोग:

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

प्रिंट:

(391, 398)