Wie finde ich die längste Übereinstimmung aus einer Reihe von Listen in Python?

Question

Wenn ich eine Liste haben ähnliche

my_list = [1, 7, 3, 4, 2, 9, 6, 5, 8] 

Auch habe ich andere Listen der Länge kleiner als die Länge des my_list. Zum Beispiel lassen Sie uns sagen, ich habe zwei weitere Listen wie folgt:

my_other_list_1 = [1, 7, 3, 4, 2] 
my_other_list_2 = [1, 7, 4, 9, 8] 

Alle Listen haben verschiedene Elemente und die anderen Listen haben Elemente aus der ursprünglichen Liste.

Mein Problem ist es, die Liste zu finden (entweder my_other_list_1 oder my_other_list_2), die die längste Übereinstimmung in my_list hat. Zuerst möchte ich fragen, wie dieses Problem genannt wird? Dann bevorzuge ich die Länge der längsten Übereinstimmung jeder Liste. Wie mache ich das?

Im Beispiel würde ich my_other_list_1 zurückkehren, weil es eine Übereinstimmung der Länge 5 seit [1, 7, 3, 4, 2] hat bereits in my_list. Auch würde ich für my_other_list_2 zurückgeben, weil es eine Übereinstimmung der Länge 2 darin gibt, d.h. [1, 7].

Summieren, wenn ich einen Algorithmus A sind und die Eingänge sind my_list, my_other_list_1my_other_list_2 und, sollte der Algorithmus

my_other_list_1 has match 5 
my_other_list_2 has match 2 

NB zurück. Ich denke, das ist ein Problem, das so genannte längste gemeinsame Subsequenz (LCS) Problem, aber wie ich im LCS Problem verstehe, müssen die Subsequenzen nicht aufeinanderfolgend sein.

Answer 1

def longest_match(main_list, *other_lists, **options): 
    try: 
     if options: 
      ordered = options['ordered'] 
     else: 
      raise Exception 
    except: 
     ordered = False 

    best_match = 0 
    longest_match = 0 
    for index, list in enumerate(other_lists): 
     current_match = 0 
     if not ordered: 
      while True: 
       if list[:current_match] == main_list[:current_match]: 
        current_match += 1 
       else: 
        if current_match > longest_match: 
         longest_match = current_match 
         best_match = index 
        break 
     else: 
      for i, letter in enumerate(list): 
       current_match = i 
       if letter == main_list[0]: 
        current_match += 1 
        while True: 
         if list[i:current_match] == main_list[:current_match]: 
          current_match += 1 
         else: 
          if current_match > longest_match: 
           longest_match = current_match 
           best_match = index 
          break 
    return other_lists[best_match] 

print longest_match(my_list, my_other_list_1, my_other_list_2, ordered=True) #kwarg odered=True will allow for mid list comprehension 

Ich bin auf meinem Telefon und havnt getestet die folgenden, aber es sollte den Trick tun!

Answer 2

Ich wäre mehr als glücklich, helfen zu knospen! Hier gehts!

def matcher_algorithm_large(original_list, **kwargs): 
match_dict = {} 
for i in kwargs: 
    counter=0 
    for j in kwargs[i]: 
     if j == original_list[kwargs[i].index(j)]: 
      counter += 1 
     else: 
      break 
    match_dict[i]=counter 
for key,value in match_dict.items(): 
    print('{} has match {}'.format(key,value)) 

Das so im Grunde kann man sie stecken in etwa so:

my_list = [1, 7, 3, 4, 2, 9, 6, 5, 8] 
my_other_list_1 = [1, 7, 3, 4, 2] 
my_other_list_2 = [1, 7, 4, 9, 8] 

matcher_algorithm_large(my_list,my_other_list_1=my_other_list_1,my_other_list_2=my_other_list_2) 

Dies gibt Ihnen die folgende Ausgabe:

my_other_list_1 has match 5 
my_other_list_2 has match 2 

Ich hoffe, das hilft dir. Ich habe es so gemacht, dass Sie beliebig viele Listen einreichen können. Die Eingaben könnten viel sauberer gemacht werden, wenn Sie ein Diktat von Listen hätten, aber das liegt an Ihnen, wenn Sie es so haben möchten. Ich wäre mehr als glücklich, das zu schreiben. :)