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

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'

我在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!)

然后,为了找到实时复杂度,我们需要将每个产量的平均复杂度与基于置换构造结果字符串的复杂性相加.如果我们将这个总和乘以上面的公式,我们得到总时间复杂度.