How can I alternate or create unique permutations of two lines (without recursion)

Question

The question is to print all possible alternations of two given lines. So I wrote working code in Python that works like this:

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 

It arrives at every point in the line, then for one recursive call it considers the current element as belonging to the first array, and in the next call it belongs to another array. Therefore, if the input lines are ab and cd , it outputs abcd , acbd , cdab , cabd , etc. p1 and p2 are pointers to arrays (since Python strings are immutable, I use arrays!). Can someone tell me what the complexity of the code is, and if it can be improved or not? I wrote a similar code to print all combinations of length k from a given array:

 def kcomb(arr,i,thisarr,k): thisarr = copy(thisarr) j,n = len(thisarr),len(arr) if ni<kj 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 

This also works on the same principle. In general, how to find the complexity of such functions and how to optimize them? Is it possible to do this using DP? I / O example for the first problem:

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

Your problem can be reduced to the problem of creating all the unique permutations of a specific list. Say A and B are the lengths of the strings arr1 and arr2 respectively. Then create a list like this:

 [0] * A + [1] * B 

There is a one-to-one correspondence (bijection) from the only permutations of this list to all possible permutations of the two lines arr1 and arr2 . The idea is to allow each permutation value to indicate which line to take the next character from. Here is an implementation example showing how to construct an interlace from a permutation:

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

I found this question on the python mailing list which asks how to solve this problem effectively. The answers suggest using the algorithm described in Knuth Art of Computer Programming, Volume 4, Fascicle 2: Generating All Permutations. I found an online version of the project here . The algorithm is also described in this wikipedia article .

Here is my own annotated implementation of the next_permutation algorithm, as a function of the python generator.

 def unique_permutations(seq):  """  Yield only unique permutations of seq in an efficient way.  A python implementation of Knuth "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] 

Each output of the algorithm has the amortized complexity O (1), according to this question, but according to rici, who commented below, this is only the case if all numbers are unique, in which case they are not defined.

In any case, the number of outputs gives a lower estimate of the time complexity, and it is determined by the expression

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

Then, to find the real-time complexity, we need to summarize the average complexity of each output with the complexity of constructing the resulting row based on the permutation. If you multiply this amount by the above formula, we get the total time complexity.

Answer 2

OK, after some work, and use the recommendations of the other answers. mainly lazir. (and now converting it to a class) __all_perms: https://stackoverflow.com/a/377829/

 class Interleave(): def __init__(self, A, B): self.A = A self.B = B self.results = list(self.__interleave()) # from /questions/18346/how-to-generate-all-permutations-of-a-list-in-python/135972#135972 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) 

and here is the use:

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

you can also access class members, for example:

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

Answer 3

Does permutations for you? Or is it a coding practice?

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

Here is what I think you are trying to do:

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