सूचियों की एक जोड़ी से न्यूनतम जोड़े की सूची

Question

पूर्णांक की दो सूचियों को देखते हुए, जोड़े की सबसे छोटी सूची उत्पन्न करें जहां दोनों सूचियों में प्रत्येक मान मौजूद है। प्रत्येक जोड़ी का पहला भाग पहली सूची से एक मान होना चाहिए, और प्रत्येक जोड़ी का दूसरा भाग दूसरी सूची से एक मान होना चाहिए। प्रत्येक जोड़ी का पहला जोड़ी के दूसरे से कम होना चाहिए।

सूचियां अलग-अलग लंबाई होती हैं, या यदि प्रत्येक सूची में एक ही स्थिति में एक ही पूर्णांक मौजूद होता है तो एक साधारण zip काम नहीं करेगा। यहाँ

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 

और एक साधारण परीक्षण दिनचर्या है:

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

यहाँ मैं अब तक के साथ आ सकता है

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

वास्तविक:

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

मैं जबकि केवल एक बार प्रत्येक सूची के प्रत्येक तत्व को देखकर यह किया जा सकता है, लगता है तो जटिलता O(len(up) + len(down)) में। मुझे लगता है कि यह प्रत्येक सूची के लिए अद्वितीय संख्या तत्वों पर निर्भर करता है।

संपादित करें: मुझे यह जोड़ना चाहिए कि हम इन सूचियों को पहले सबसे छोटे पूर्णांक के साथ क्रमबद्ध करने की उम्मीद कर सकते हैं।

संपादित करें: 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 था इसलिए मैं वास्तव में इसे समझना चाहता था ;-)

वैसे भी, समाधान तब आया जब मैंने इसे सीधे करने पर छोड़ दिया और ग्राफ के बारे में ग्राफ बनाना शुरू किया matchings। मैं आपकी पहली सूची में बस अंतराल को परिभाषित करता है लगता है और आप आइटम है कि उन्हें में गिर जाते हैं के लिए देख रहे:

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 अजगर 2. x में izip_longest कहा जाता है

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