如何交错或创建两个字符串的独特排列（无递归）

Question

问题是要打印两个给定字符串的所有可能的交错。所以我写在Python它运行一个像这样的工作代码：

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 

它是在字符串中的每一个点，那么对于一个递归调用，它认为当前元素为属于第一阵列，并在下一个电话，属于另一个阵列。因此，如果输入的字符串是ab和cd，它打印出abcd，acbd，cdab，cabd等p1和p2是指向数组（因为Python中的字符串是不可改变的，我使用数组！）。任何人都可以告诉我，这段代码的复杂性是什么，如果可以改进或者不改善？我已经写了类似的代码从给定的阵列打印长度k的所有组合：

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 

这也适用同样的原则。所以一般来说，如何找到这些功能的复杂性，以及如何优化它们？ DP可以做到这些吗？第一个问题的示例输入输出：

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

你的问题可以简化与创建特定列表中的所有独特排列。假设A和B分别是字符串arr1和arr2的长度。然后构建一个列表如下：

[0] * A + [1] * B 

存在着一一一对应（双射）从该列表中的独特排列的两个字符串arr1和arr2的所有可能的交错。这个想法是让排列的每个值指定从哪个字符串取下一个字符。这里是展示如何从排列构造交错的范例：

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

我发现this问题，其中问到如何以有效的方式解决这一问题的蟒蛇邮件列表。答案建议使用Knuth的计算机编程艺术，第4卷，分册2：生成所有排列中描述的算法。我找到了草稿here的在线pdf。该算法也在此wikipedia article中描述。

这是我自己注释的next_permutation算法的实现，作为一个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] 

算法的每一个产量为O（1）的摊销复杂，根据this的问题，但根据RICI谁下面评论，这是只有当所有的数字都是独特的，他们是肯定的情况下不是在这种情况下。

在任何情况下，收益率的数量提供了一个下界的时间复杂度，它是由

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

给予然后找到真正的时间复杂度，我们需要总结每种收益的平均复杂度与基于置换构造结果字符串的复杂性相关。如果我们将这个总和乘以上面的公式，我们就可以得到总的时间复杂度。

Answer 2

请问permutations是否适合您？或者，这种编码习惯？

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

这是我认为你正在试图做的：

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

好的，经过一些工作，并从其他答案的建议。主要是懒惰。 （和现在已经把它转换成一个类）的__all_perms为：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) 

和这里的用法：

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

还，您可以访问类的成员，如：

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