Algoritmo para unir 2 listas con comodines

Question

Estoy buscando una manera eficiente de unir 2 listas, una que contenga información completa y otra que contenga comodines. Pude hacer esto con comodines de longitud fija, pero ahora trato de hacerlo con comodines de longitud variable.

Por lo tanto:

match(['A', 'B', '*', 'D'], ['A', 'B', 'C', 'C', 'C', 'D']) 

regresarían cierto siempre y cuando todos los elementos están en el mismo orden en ambas listas.

Estoy trabajando con listas de objetos, pero utilicé las cadenas anteriores para simplificar.

Answer 1

[Editado para justificar ningún comentario RE después de la OP en los objetos que comparan]

Parece que no está utilizando cuerdas, sino más bien la comparación de objetos.Por lo tanto, estoy dando un algoritmo explícito: las expresiones regulares proporcionan una buena solución adaptada a las cadenas, no me malinterpreten, pero por lo que dices como un comentario a tus preguntas, parece que un algoritmo simple y explícito puede facilitarte las cosas .

Resulta que esto se puede solucionar con un algoritmo mucho más simple que this previous answer:

def matcher (l1, l2): 
    if (l1 == []): 
     return (l2 == [] or l2 == ['*']) 
    if (l2 == [] or l2[0] == '*'): 
     return matcher(l2, l1) 
    if (l1[0] == '*'): 
     return (matcher(l1, l2[1:]) or matcher(l1[1:], l2)) 
    if (l1[0] == l2[0]): 
     return matcher(l1[1:], l2[1:]) 
    else: 
     return False 

La idea clave es que cuando se encuentra con un comodín, se puede explorar dos opciones:

• ya sea avanzar en la lista que contiene el comodín (y considerar el comodín coincide con lo que había hasta ahora)
• o avanzar en la lista que no contiene el comodín (y considerar que lo que está en el encabezado de la lista debe coincidir con el comodín).

Answer 2

Estoy de acuerdo con el comentario sobre esto podría hacerse con expresiones regulares. Por ejemplo:

import re 

lst = ['A', 'B', 'C', 'C', 'C', 'D'] 
pattern = ['A', 'B', 'C+', 'D'] 

print re.match(''.join(pattern), ''.join(lst)) # Will successfully match 

Editar: Como ha señalado un comentario, que podría ser conocido de antemano sólo que algunos personaje tiene que ser igualado, pero no cuál. En ese caso, las expresiones regulares son útiles aún:

import re 

lst = ['A', 'B', 'C', 'C', 'C', 'D'] 
pattern = r'AB(\w)\1*D' 

print re.match(pattern, ''.join(lst)).groups() 

Answer 3

¿Qué hay de lo siguiente:

import re 

def match(pat, lst): 
    regex = ''.join(term if term != '*' else '.*' for term in pat) + '$' 
    s = ''.join(lst) 
    return re.match(regex, s) is not None 

print match(['A', 'B', '*', 'D'], ['A', 'B', 'C', 'C', 'C', 'D']) 

Utiliza expresiones regulares. Los comodines (*) se cambian a .* y todos los demás términos de búsqueda se mantienen como están.

Una advertencia es que si los términos de búsqueda pueden contener elementos que tengan un significado especial en el lenguaje de expresiones regulares, se debería tener el escape adecuado. Es bastante fácil manejar esto en la función match, simplemente no estaba seguro de si esto era algo que necesitabas.

Answer 4

lo recomiendo convertir ['A', 'B', '*', 'D'] a '^AB.*D$', ['A', 'B', 'C', 'C', 'C', 'D']-'ABCCCD', y luego usando el módulo re (expresiones regulares) que ver el partido.

Esto será válido si los elementos de sus listas tienen un solo carácter y si son cadenas.

algo como:

import(re) 
def myMatch(patternList, stringList): 
    # convert pattern to flat string with wildcards 
    # convert AB*D to valid regex ^AB.*D$ 
    pattern = ''.join(patternList) 
    regexPattern = '^' + pattern.replace('*','.*') + '$' 
    # perform matching 
    against = ''.join(stringList) # convert ['A','B','C','C','D'] to ABCCCD 
    # return whether there is a match 
    return (re.match(regexPattern,against) is not None) 

Si las listas contienen números o palabras, elegir un personaje que no se puede esperar a estar en cualquiera, por ejemplo #. A continuación, ['Aa','Bs','Ce','Cc','CC','Dd'] se puede convertir a Aa#Bs#Ce#Cc#CC#Dd, el patrón de comodín se podría convertir a ^Aa#Bs#.*#Dd$, y la coincidencia se realizó.

Hablando de manera práctica, esto significa que todos los ''.join(...) se convierten en '#'.join(...) en myMatch.

Answer 5

Estoy de acuerdo, las expresiones regulares suelen ser el camino a seguir con este tipo de cosas. Este algoritmo funciona, pero me parece intrincado. Fue divertido escribir sin embargo.

def match(listx, listy): 
    listx, listy = map(iter, (listx, listy)) 
    while 1: 
     try: 
      x = next(listx) 
     except StopIteration: 
      # This means there are values left in listx that are not in listy. 
      try: 
       y = next(listy) 
      except StopIteration: 
       # This means there are no more values to be compared in either 
       # listx or listy; since no exception was raied elsewhere, the 
       # lists match. 
       return True 
      else: 
       # This means that there are values in listy that are not in 
       # listx. 
       return False 
     else: 
      try: 
       y = next(listy) 
      except StopIteration: 
       # Similarly, there are values in listy that aren't in listx. 
       return False 
     if x == y: 
      pass 
     elif x == '*': 
      try: 
       # Get the value in listx after '*'. 
       x = next(listx) 
      except StopIteration: 
       # This means that listx terminates with '*'. If there are any 
       # remaining values of listy, they will, by definition, match. 
       return True 
      while 1: 
       if x == y: 
        # I didn't shift to the next value in listy because I 
        # assume that a '*' matches the empty string and well as 
        # any other. 
        break 
       else: 
        try: 
         y = next(listy) 
        except StopIteration: 
         # This means there is at least one remaining value in 
         # listx that is not in listy, because listy has no 
         # more values. 
         return False 
        else: 
         pass 
     # Same algorithm as above, given there is a '*' in listy. 
     elif y == '*': 
      try: 
       y = next(listy) 
      except StopIteration: 
       return True 
      while 1: 
       if x == y: 
        break 
       else: 
        try: 
         x = next(listx) 
        except StopIteration: 
         return False 
        else: 
         pass 

Answer 6

Tenía este código de código C++ que parece estar haciendo lo que está intentando hacer (las entradas son cadenas en lugar de matrices de caracteres, pero tendrá que adaptar las cosas de todos modos).

bool Utils::stringMatchWithWildcards (const std::string str, const std::string strWithWildcards) 
    PRINT("Starting in stringMatchWithWildcards('" << str << "','" << strWithWildcards << "')"); 
    const std::string wildcard="*"; 

    const bool startWithWildcard=(strWithWildcards.find(wildcard)==0); 
    int pos=strWithWildcards.rfind(wildcard); 
    const bool endWithWildcard = (pos!=std::string::npos) && (pos+wildcard.size()==strWithWildcards.size()); 

    // Basically, the point is to split the string with wildcards in strings with no wildcard. 
    // Then search in the first string for the different chunks of the second in the correct order 
    std::vector<std::string> vectStr; 
    boost::split(vectStr, strWithWildcards, boost::is_any_of(wildcard)); 
    // I expected all the chunks in vectStr to be non-empty. It doesn't seem the be the case so let's remove them. 
    vectStr.erase(std::remove_if(vectStr.begin(), vectStr.end(), std::mem_fun_ref(&std::string::empty)), vectStr.end()); 

    // Check if at least one element (to have first and last element) 
    if (vectStr.empty()) 
    { 
     const bool matchEmptyCase = (startWithWildcard || endWithWildcard || str.empty()); 
     PRINT("Match " << (matchEmptyCase?"":"un") << "successful (empty case) : '" << str << "' and '" << strWithWildcards << "'"); 
     return matchEmptyCase; 
    } 

    // First Element 
    std::vector<std::string>::const_iterator vectStrIt = vectStr.begin(); 
    std::string aStr=*vectStrIt; 
    if (!startWithWildcard && str.find(aStr, 0)!=0) { 
     PRINT("Match unsuccessful (beginning) : '" << str << "' and '" << strWithWildcards << "'"); 
     return false; 
    } 

    // "Normal" Elements 
    bool found(true); 
    pos=0; 
    std::vector<std::string>::const_iterator vectStrEnd = vectStr.end(); 
    for (; vectStrIt!=vectStrEnd ; vectStrIt++) 
    { 
     aStr=*vectStrIt; 
     PRINT("Searching '" << aStr << "' in '" << str << "' from " << pos); 
     pos=str.find(aStr, pos); 
     if (pos==std::string::npos) 
     { 
      PRINT("Match unsuccessful ('" << aStr << "' not found) : '" << str << "' and '" << strWithWildcards << "'"); 
      return false; 
     } else 
     { 
      PRINT("Found at position " << pos); 
      pos+=aStr.size(); 
     } 
    } 

    // Last Element 
    const bool matchEnd = (endWithWildcard || str.rfind(aStr)+aStr.size()==str.size()); 
    PRINT("Match " << (matchEnd?"":"un") << "successful (usual case) : '" << str << "' and '" << strWithWildcards); 
    return matchEnd; 
} 

    /* Tested on these values : 
    assert(stringMatchWithWildcards("ABC","ABC")); 
    assert(stringMatchWithWildcards("ABC","*")); 
    assert(stringMatchWithWildcards("ABC","*****")); 
    assert(stringMatchWithWildcards("ABC","*BC")); 
    assert(stringMatchWithWildcards("ABC","AB*")); 
    assert(stringMatchWithWildcards("ABC","A*C")); 
    assert(stringMatchWithWildcards("ABC","*C")); 
    assert(stringMatchWithWildcards("ABC","A*")); 

    assert(!stringMatchWithWildcards("ABC","BC")); 
    assert(!stringMatchWithWildcards("ABC","AB")); 
    assert(!stringMatchWithWildcards("ABC","AB*D")); 
    assert(!stringMatchWithWildcards("ABC","")); 

    assert(stringMatchWithWildcards("","")); 
    assert(stringMatchWithWildcards("","*")); 
    assert(!stringMatchWithWildcards("","ABC")); 
    */ 

No es algo de lo que esté realmente orgulloso, pero parece estar funcionando hasta ahora. Espero que lo encuentres útil.