您的问题可以简化为创建特定列表的所有 唯一 排列的问题。说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'

我在python邮件列表中找到了这个问题，该列表询问如何以有效的方式解决此问题。答案建议使用一种算法，该算法在Knuth的
《计算机编程艺术》，第4卷，专着2：生成所有排列中进行了描述
。我在这里找到了该草稿的在线pdf文件。该维基百科文章中也描述了该算法。

这是我自己注释的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）的摊销复杂度，但是根据下面评论的rici，只有所有数字都是唯一的情况才是这种情况，但在这种情况下绝对不是。

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

（A + B）！/（A！* B！）

然后，要找到实时复杂度，我们需要将每个收益的平均复杂度与基于置换构造结果字符串的复杂度相加。如果将这个总和与上式相乘，我们将得出总的时间复杂度。