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

问题是打印两个给定字符串的所有可能的交错。所以我用 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 and cd，它打印出abcd, acbd, cdab, cabd, etc. p1 and 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

你的问题可以简化为创建所有unique特定列表的排列。说A and B是字符串的长度arr1 and arr2， 分别。然后构造一个像这样的列表：

[0] * A + [1] * B

从该列表的唯一排列到两个字符串的所有可能的交错，存在一一对应关系（双射）arr1 and 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'

I found this http://mail.python.org/pipermail/tutor/2009-December/073567.htmlpython 邮件列表中的问题询问如何有效地解决这个问题。答案建议使用 Knuth 中描述的算法计算机编程艺术，第 4 卷，分册 2：生成所有排列。我找到了一份在线 pdf 草稿here http://www.cs.utsa.edu/%7Ewagner/knuth/fasc2b.pdf。该算法也在本文中进行了描述维基百科文章 http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order.

这是我自己带注释的实现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 = list(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 https://stackoverflow.com/questions/4973077/the-amortized-complexity-of-stdnext-permutation问题，但根据下面评论的 rici 的说法，只有所有数字都是唯一的情况才会出现这种情况，而在这种情况下肯定不是这样。

无论如何，收益率的数量提供了时间复杂度的下限，它由下式给出

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

然后，为了找到实时复杂度，我们需要将每个产量的平均复杂度与基于排列构造结果字符串的复杂度相加。如果我们将此总和与上面的公式相乘，我们就得到了总时间复杂度。