Quelle est la meilleure approche pour faire correspondre/joindre des éléments dans deux listes python non triées non identiques de différentes longueurs?

Question

je par exemple les listes de python suivantes:

a = [1,2,1,3,2,1,1,1,2,1,1,1,1,1,3,1,2] 
b = [1,1,2,1,3,1,1,1,1,2,2,1,1,1,1,3,1,2] 

et je voudrais obtenir les tuples des indices des éléments qui peuvent être en toute confiance égale, tels que:

[(0,0), (1,2), (2,3), (3,4), (8,9), (14,15), (15,16), (16,17)] 

Les données représenter les tailles des groupes de personnes enregistrées arrivant et laissant une file d'attente, mais les données ne sont pas parfaites non plus, donc les sommes de a et b ne correspondent pas, et les gens n'ont pas toujours besoin de partir dans l'ordre arrivée. Je me rends compte que cela dépend de plusieurs variables (ou paramètres de seuil), mais je suis à la recherche de suggestions sur la meilleure façon d'aborder le problème. Je suis heureux d'utiliser Pandas/Numpy/Scipy pour faire le travail. Je me suis rendu compte que c'est assez difficile à expliquer. À l'oeil, il est facile pour moi de faire correspondre les séquences partielles, telles que 1,2,1,3. Ne pas trouver si facile de mettre au point une bonne approche algorithmique.

Answer 1

I Python finalement réalisé a difflib bibliothèque pour ce genre de chose!

a = [1, 2, 1, 3, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 2] 
b = [1, 1, 2, 1, 3, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 1, 2] 

from difflib import SequenceMatcher 

s = SequenceMatcher(None, a, b, autojunk=False) 

matched_element_indices = [] 
for m in s.get_matching_blocks(): 
    matched_element_indices += [(m.a+i,m.b+i) for i in range(m.size)] 

Il produit ceci:

In : matched_element_indices 
Out: [(0, 1), (1, 2), (2, 3), (3, 4), (5, 6), (6, 7), (7, 8), (8, 9), 
      (10, 11), (11, 12), (12, 13), (13, 14), (14, 15), (15, 16), (16, 17)] 

Answer 2

Je ne comprends pas bien votre sortie, mais pour obtenir les indices d'élément correspondant dans l'ordre:

a = [1, 2, 1, 3, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 2] 
b = [1, 1, 2, 1, 3, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 1, 2] 
from collections import defaultdict, deque 

d = defaultdict(deque) 
for i, j in enumerate(b): 
    d[j].append(i) 

print([(i, d[j].popleft()) for i, j in enumerate(a)]) 

La seule façon que je peux correspondre à votre sortie est si l'on considère les éléments qui ne sont pas des séquences:

from itertools import groupby 
from operator import itemgetter 

def pairs(a, b): 
    for (k, v) in (groupby(enumerate(a), key=itemgetter(1))): 
     data = next(v) 
     if not next(v, None): 
      ind, val = data 
      if b[ind] == val: 
       yield (ind, ind) 
      elif val == b[ind + 1]: 
       yield (ind, ind + 1) 

print(list(pairs(a, b))) 

qui vous donnerait:

[(0, 0), (1, 2), (2, 3), (3, 4), (8, 9), (14, 15), (15, 16), (16, 17)]