gpt4 book ai didi

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

转载 作者:太空狗 更新时间:2023-10-29 19:34:50 25 4
gpt4 key购买 nike

问题是打印两个给定字符串的所有可能交错。所以我用 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

它出现在字符串中的每个点,然后对于一次递归调用,它认为当前元素属于第一个数组,而在下一次调用中,属于另一个数组。因此,如果输入字符串是 abcd,它会打印出 abcdacbdcdab, cabd 等。 p1p2 是指向数组的指针(因为 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

最佳答案

您的问题可以简化为创建特定列表的所有唯一 排列。假设 AB 分别是字符串 arr1arr2 的长度。然后构造一个这样的列表:

[0] * A + [1] * B

从该列表的唯一排列到两个字符串 arr1arr2 的所有可能交错存在一一对应关系(双射)。这个想法是让排列的每个值指定从哪个字符串中获取下一个字符。下面是一个示例实现,展示了如何从排列构造交错:

>>> 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 python 邮件列表中的问题询问如何以有效的方式解决此问题。答案建议使用 Knuth 的 计算机编程艺术,第 4 卷,分册 2:生成所有排列 中描述的算法。我找到了草稿的在线 pdf here .此 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 = 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]

根据 this,算法的每个 yield 的摊销复杂度为 O(1)问题,但根据在下面发表评论的 rici 所说,只有所有数字都是唯一的情况才会出现这种情况,而在这种情况下肯定不是。

在任何情况下, yield 的数量提供了时间复杂度的下限,由下式给出

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

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

关于python - 如何交错或创建两个字符串的唯一排列(无递归),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12836385/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com