Come posso intercalare o creare permutazioni uniche di due stringhe (senza ricorsione)

Question

La domanda è di stampare tutti i possibili intrecci di due stringhe date. Così ho scritto un codice di lavoro in Python che viene eseguito in questo modo:

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 

Si tratta in ogni punto in una stringa, poi per una chiamata ricorsiva, si considera l'elemento corrente come appartenente alla prima matrice e nel prossima chiamata, appartenente all'altro array. Quindi, se le stringhe di input sono ab e cd, esso stampa abcd, acbd, cdab, cabd, ecc p1 e p2 sono puntatori alle matrici (perché le stringhe di Python sono immutabili, sto usando gli array!). Qualcuno può dirmi, qual è la complessità di questo codice e se può essere migliorata o no? Ho scritto un codice simile per stampare tutte le combinazioni di lunghezza k da un dato array:

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 

Anche questo, funziona sullo stesso principio. Quindi, in generale, come trovare la complessità di tali funzioni e come ottimizzarle? È possibile farlo da DP? input-output di esempio per il primo 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

il problema può essere ridotto a quello di creare tutte le uniche permutazioni di una particolare lista. Dire A e B sono le lunghezze delle stringhe arr1 e arr2, rispettivamente. Quindi creare una lista come questa:

[0] * A + [1] * B 

Esiste una corrispondenza uno-a-uno (una biiezione) dalle permutazioni uniche di questo elenco di tutte le possibili interleavings delle due stringhe arr1 e arr2. L'idea è di lasciare che ogni valore della permutazione specifichi da quale stringa prendere il carattere successivo. Ecco un esempio di implementazione che mostra come costruire un interlacciamento da una permutazione:

>>> 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' 

ho trovato this domanda sulla mailing list di pitone che chiede come risolvere questo problema in modo efficiente. Le risposte suggeriscono di utilizzare un algoritmo descritto in Knuth The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Permutations. Ho trovato un pdf online della bozza here. L'algoritmo è anche descritto in questo wikipedia article.

Ecco la mia implementazione annotata dell'algoritmo next_permutation, come funzione di generatore di 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] 

Ogni resa dello algoritmo ha una complessità ammortizzato di O (1), secondo la this domanda, ma secondo rici che ha commentato di seguito, questo è solo il caso se tutti i numeri sono unici, che sono sicuramente non in questo caso.

In ogni caso, il numero di rendimenti fornisce un limite inferiore per la complessità temporale, ed è dato da

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

Poi trovare la vera complessità tempo necessario per sommare la complessità media di ogni rendimento con la complessità della costruzione della stringa risultante basata sulla permutazione. Se moltiplichiamo questa somma con la formula precedente, otteniamo la complessità totale del tempo.

Answer 2

Does permutations lavoro per voi? O è questa pratica di codifica?

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

Questo è ciò che penso che stai cercando di fare:

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

ok, dopo un po 'di lavoro, e si prega di inviare un consiglio da altre risposte. principalmente lazyr. (E hanno ora trasformato in una classe) i __all_perms è da: 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) 

e qui è l'utilizzo:

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

inoltre, è possibile accedere ai membri della classe come:

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