Cómo puedo entrelazar o crear permutaciones únicas de dos cadenas (sin recurrencia)

Question

La cuestión es imprimir todos los entrelazados posibles de dos cadenas dadas. Así que escribí un código de trabajo en Python que funciona de esta manera:

def inter(arr1,arr2,p1,p2,arr): 
    thisarr = copy(arr) 
    if p1 == len(arr1) and p2 == len(arr2): 
     printarr(thisarr) 
    elif p1 == len(arr1): 
     thisarr.extend(arr2[p2:]) 
     printarr(thisarr) 
    elif p2 == len(arr2): 
     thisarr.extend(arr1[p1:]) 
     printarr(thisarr) 
    else: 
     thisarr.append(arr1[p1]) 
     inter(arr1,arr2,p1+1,p2,thisarr) 
     del thisarr[-1] 
     thisarr.append(arr2[p2]) 
     inter(arr1,arr2,p1,p2+1,thisarr) 
    return 

Viene en cada punto en una cadena, después durante una llamada recursiva, se considera el elemento actual como pertenecientes a la primera serie, y en el próxima llamada, que pertenece a la otra matriz. Así que si las cadenas de entrada son ab y cd, imprime abcd, acbd, cdab, cabd, etc. p1 y p2 son punteros a las matrices (porque las cadenas de Python son inmutables, que estoy usando matrices!). ¿Alguien me puede decir cuál es la complejidad de este código, y si puede mejorarse o no? He escrito un código similar para imprimir todas las combinaciones de longitud k de una matriz dada:

def kcomb(arr,i,thisarr,k): 
    thisarr = copy(thisarr) 
    j,n = len(thisarr),len(arr) 
    if n-i<k-j or j >k: 
     return 
    if j==k: 
     printarr(thisarr) 
     return 
    if i == n: 
     return 
    thisarr.append(arr[i]) 
    kcomb(arr,i+1,thisarr,k) 
    del thisarr[-1] 
    kcomb(arr,i+1,thisarr,k) 
    return 

Esto también funciona en el mismo principio. Entonces, en general, ¿cómo encontrar la complejidad de tales funciones y cómo las optimizo? ¿Es posible hacer esto por DP? Muestra de entrada-salida para el primer problema:

>>> arr1 = ['a','b','c'] 
>>> arr2 = ['d','e','f'] 
>>> inter(arr1,arr2,0,0,[]) 
abcdef 
abdcef 
abdecf 
abdefc 
adbcef 
adbecf 
adbefc 
adebcf 
adebfc 
adefbc 
dabcef 
dabecf 
dabefc 
daebcf 
daebfc 
daefbc 
deabcf 
deabfc 
deafbc 
defabc 

Answer 1

Su problema puede reducirse a la de la creación de todas las únicas permutaciones de una lista en particular. Diga A y B son las longitudes de las cadenas arr1 y arr2, respectivamente. A continuación, construir una lista como esta:

[0] * A + [1] * B 

Existe una correspondencia uno-a-uno (una biyección) de las permutaciones únicas de esta lista a todas las posibles intercalaciones de las dos cadenas arr1 y arr2. La idea es dejar que cada valor de la permutación especifique de qué cadena sacar el siguiente carácter. Aquí es una implementación de ejemplo que muestra cómo construir una intercalación de una permutación:

>>> def make_interleave(arr1, arr2, permutation): 
...  iters = [iter(arr1), iter(arr2)] 
...  return "".join(iters[i].next() for i in permutation) 
... 
>>> make_interleave("ab", "cde", [1, 0, 0, 1, 1]) 
'cabde' 

He encontrado this pregunta en la lista de correo pitón que se pregunta cómo resolver este problema de una manera eficiente. Las respuestas sugieren el uso de un algoritmo que se describe en Knuth's The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Permutations. Encontré un pdf en línea del borrador here. El algoritmo también se describe en este wikipedia article.

Aquí está mi propia implementación anotada del algoritmo next_permutation, como una función generadora de python.

def unique_permutations(seq): 
    """ 
    Yield only unique permutations of seq in an efficient way. 

    A python implementation of Knuth's "Algorithm L", also known from the  
    std::next_permutation function of C++, and as the permutation algorithm 
    of Narayana Pandita. 
    """ 

    # Precalculate the indices we'll be iterating over for speed 
    i_indices = range(len(seq) - 1, -1, -1) 
    k_indices = i_indices[1:] 

    # The algorithm specifies to start with a sorted version 
    seq = sorted(seq) 

    while True: 
        yield seq 

     # Working backwards from the last-but-one index,          k 
        # we find the index of the first decrease in value.  0 0 1 0 1 1 1 0 
        for k in k_indices: 
            if seq[k] < seq[k + 1]: 
                break 
        else: 
      # Introducing the slightly unknown python for-else syntax: 
      # else is executed only if the break statement was never reached. 
      # If this is the case, seq is weakly decreasing, and we're done. 
            return 

     # Get item from sequence only once, for speed 
        k_val = seq[k] 

        # Working backwards starting with the last item,        k     i 
        # find the first one greater than the one at k    0 0 1 0 1 1 1 0 
        for i in i_indices: 
            if k_val < seq[i]: 
                break 

        # Swap them in the most efficient way 
        (seq[k], seq[i]) = (seq[i], seq[k])            #       k     i 
                                              # 0 0 1 1 1 1 0 0 

     # Reverse the part after but not       k 
     # including k, also efficiently.      0 0 1 1 0 0 1 1 
     seq[k + 1:] = seq[-1:k:-1] 

Cada rendimiento del algoritmo tiene una complejidad amortizado de O (1), de acuerdo con this pregunta, pero de acuerdo con RICI que comentó más adelante, esto es sólo el caso si todos los números son únicos, que son sin duda no en este caso.

En cualquier caso, el número de los rendimientos proporciona un límite inferior para la complejidad del tiempo, y que viene dado por

 
(A + B)!/(A! * B!) 

Luego de encontrar la complejidad en tiempo real que necesitamos para resumir la complejidad media de cada rendimiento con la complejidad de construir la cadena resultante basada en la permutación. Si multiplicamos esta suma con la fórmula anterior obtenemos la complejidad total del tiempo.

Answer 2

¿El permutations trabajo para usted? O bien, ¿es esta práctica de codificación?

>>> from itertools import permutations 
>>> s1 = "ab" 
>>> s2 = "cd" 
>>> all_values = [c for c in s1 + s2] 
>>> ["".join(r) for r in permutations(all_values)] 
['abcd', 'abdc', 'acbd', 'acdb', 'adbc', 'adcb', 'bacd', 'badc', 'bcad', 'bcda', 'bdac', 'bdca', 'cabd', 'cadb', 'cbad', 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca', 'dcab', 'dcba'] 

Answer 3

Esto es lo que creo que estamos tratando de hacer:

from itertools import product, chain 

def interleave(a, b): 
    if len(b) > len(a): 
     a, b = b, a 

    boolean = (True, False) 
    for z in range(len(a) - len(b) + 1): 
     pairs = list(zip(a[z:], b)) 
     for vector in product(*[boolean] * max(map(len, (a, b)))): 
      permutation = (pair if i else reversed(pair) 
          for i, pair in zip(vector, pairs)) 
      yield a[:z] + ''.join(chain.from_iterable(permutation)) 

Answer 4

bien, después de un trabajo, y utilizar el consejo de otras respuestas. principalmente lazyr. (Y ahora se han convertido en una clase) los __all_perms es de: https://stackoverflow.com/a/104436/1561176

class Interleave(): 

    def __init__(self, A, B): 
     self.A = A 
     self.B = B 
     self.results = list(self.__interleave()) 

    # from https://stackoverflow.com/a/104436/1561176 
    def __all_perms(self, elements): 
     if len(elements) <=1: 
      yield elements 
     else: 
      for perm in self.__all_perms(elements[1:]): 
       for i in range(len(elements)): 
        #nb elements[0:1] works in both string and list contexts 
        yield perm[:i] + elements[0:1] + perm[i:] 

    def __sequences(self): 
     return list(sorted(set(
      ["".join(x) for x in self.__all_perms(['a'] * len(self.A) + ['b'] * len(self.B))]))) 

    def __interleave(self): 
     for sequence in self.__sequences(): 
      result = "" 
      a = 0 
      b = 0 
      for item in sequence: 
       if item == 'a': 
        result+=self.A[a] 
        a+=1 
       else: 
        result+=self.B[b] 
        b+=1 
      yield result 

    def __str__(self): 
     return str(self.results) 

    def __repr__(self): 
     return repr(self.results) 

y aquí es el uso de:

>>> A = ['a', 'b', 'c'] 
>>> B = ['d', 'e', 'f'] 
>>> Interleave(A, B) 
['abcdef', 'abdcef', 'abdecf', 'abdefc', 'adbcef', 'adbecf', 'adbefc', 'adebcf', 'adebfc', 'adefbc', 'dabcef', 'dabecf', 'dabefc', 'daebcf', 'daebfc', 'daefbc', 'deabcf', 'deabfc', 'deafbc', 'defabc'] 

También, puede acceder a los miembros de la Clase como:

>>> inter = Interleave(A, B) 
>>> inter.results 
['abcdef', 'abdcef', 'abdecf', 'abdefc', 'adbcef', 'adbecf', 'adbefc', 'adebcf', 'adebfc', 'adefbc', 'dabcef', 'dabecf', 'dabefc', 'daebcf', 'daebfc', 'daefbc', 'deabcf', 'deabfc', 'deafbc', 'defabc'] 
>>> inter.A 
['a', 'b', 'c'] 
>>> inter.B 
['d', 'e', 'f']