如何交错或创建两个字符串的唯一排列(无递归) [英] How can I interleave or create unique permutations of two strings (without recursion)
问题描述
问题是打印两个给定字符串的所有可能交错.所以我用 Python 编写了一个工作代码，它运行如下:
def inter(arr1,arr2,p1,p2,arr):thisarr = 复制(arr)如果 p1 == len(arr1) 和 p2 == len(arr2):打印(thisarr)elif p1 == len(arr1):thisarr.extend(arr2[p2:])打印(thisarr)elif p2 == len(arr2):thisarr.extend(arr1[p1:])打印(thisarr)别的:thisarr.append(arr1[p1])间(arr1，arr2，p1+1，p2，thisarr)del thisarr[-1]thisarr.append(arr2[p2])间(arr1，arr2，p1，p2+1，thisarr)返回它出现在字符串中的每个点，然后对于一次递归调用，它认为当前元素属于第一个数组，而在下一次调用中，属于另一个数组.所以如果输入字符串是 ab 和 cd，它会打印出 abcd, acbd, cdab、cabd 等.p1 和 p2 是指向数组的指针(因为 Python 字符串是不可变的，所以我使用的是数组！).谁能告诉我，这段代码的复杂度是多少，是否可以改进?我写了一个类似的代码来打印给定数组中长度 k 的所有组合:
def kcomb(arr,i,thisarr,k):thisarr = 复制(thisarr)j,n = len(thisarr),len(arr)如果n-i＜k-j或j＞k:返回如果 j==k:打印(thisarr)返回如果我==n:返回thisarr.append(arr[i])kcomb(arr,i+1,thisarr,k)del thisarr[-1]kcomb(arr,i+1,thisarr,k)返回这也是同样的原理.那么总的来说，如何找到这些函数的复杂度，以及如何优化它们?DP可以做这些吗?第一个问题的输入输出示例:
<预><代码>>>>arr1 = ['a','b','c']>>>arr2 = ['d','e','f']>>>间(arr1,arr2,0,0,[])abcdefabdcefabdecfabdefc头孢菌素阿德贝夫阿德贝克德比阿德布克阿德福布克头孢菌素达贝克夫达贝夫daebcfdaebfc大夫死角死神聋哑人删除您的问题可以简化为创建特定列表的所有唯一排列.假设A 和B 分别是字符串arr1 和arr2 的长度.然后构造一个这样的列表:
[0] * A + [1] * B从这个列表的唯一排列到两个字符串 arr1 和 arr2 的所有可能交错存在一一对应(双射).这个想法是让排列的每个值指定从哪个字符串中获取下一个字符.下面是一个示例实现，展示了如何从排列构造交错:
我在 python 邮件列表中发现了这个问题它询问如何以有效的方式解决这个问题.答案建议使用 Knuth 的计算机编程艺术，第 4 卷，分册 2:生成所有排列中描述的算法.我在这里找到了草案的在线pdf.此维基百科文章中也描述了该算法.
这是我自己的 next_permutation 算法的注释实现，作为 python 生成器函数.
def unique_permutations(seq):"以有效的方式仅产生 seq 的唯一排列.Knuth 的算法 L"的 Python 实现，也从C++ 的 std::next_permutation 函数，作为置换算法纳拉亚那班智达."# 预先计算我们将迭代的索引以提高速度i_indices = list(range(len(seq) - 1, -1, -1))k_indices = i_indices[1:]# 算法指定从排序版本开始seq = 排序(seq)而真:产量序列# 从最后一个索引开始向后工作， k# 我们找到价值第一次下降的指数.0 0 1 0 1 1 1 0对于 k_indices 中的 k:如果 seq[k] <序列[k + 1]:休息别的:# 介绍稍微不为人知的python for-else 语法:# else 仅在从未到达 break 语句时执行.# 如果是这种情况，则 seq 弱递减，我们就完成了.返回# 只从序列中获取项目一次，以提高速度k_val = seq[k]# 从最后一项开始向后工作， k i# 找到第一个大于 k 0 0 1 0 1 1 1 0对于 i_indices 中的 i:如果 k_val <序列[i]:休息# 以最有效的方式交换它们(seq[k], seq[i]) = (seq[i], seq[k]) # k i# 0 0 1 1 1 1 0 0# 反转k之后但不是k的部分# 包括 k，也很有效.0 0 1 1 0 0 1 1序列[k + 1:] = 序列[-1:k:-1]根据 ，算法的每个收益都有 O(1) 的摊销复杂度这个问题，但根据下面评论的rici的说法，只有所有数字都是唯一的情况下才会出现这种情况，而在这种情况下肯定不是.
无论如何，yield 的数量提供了时间复杂度的下限，由下式给出
<前>(A + B)！/(A！* B！)然后为了找到实时复杂度，我们需要将每个收益的平均复杂度与基于排列构造结果字符串的复杂度相加.如果我们将这个总和与上面的公式相乘，我们就会得到总时间复杂度.
The question is to print all possible interleavings of two given strings. So I wrote a working code in Python which runs like this:
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
It comes at each point in a string, then for one recursive call, it considers the current element as belonging to the first array, and in the next call, belonging to the other array. So if the input strings are ab and cd, it prints out abcd, acbd, cdab, cabd, etc. p1 and p2 are pointers to the arrays (Because Python strings are immutable, I am using arrays!). Can anybody tell me, what is this code's complexity, and if it can be improved or not? I have written a similar code to print all combinations of length k from a given array:
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
This too, works on the same principle. So in general, how to find the complexity of such functions, and how do I optimize them? Is it possible to do these by DP? Sample input-output for the first problem:
>>> 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
Your problem can be reduced to that of creating all unique permutations of a particular list. Say A and B are the lengths of the strings arr1 and arr2, respectively. Then construct a list like this:
[0] * A + [1] * B
There exists a one-to-one correspondence (a bijection) from the unique permutations of this list to all the possible interleavings of the two strings arr1 and arr2. The idea is to let each value of the permutation specify which string to take the next character from. Here is an example implementation showing how to construct an interleaving from a permutation:
>>> 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 question in the python mailing list which asks how to solve this problem in an efficient manner. The answers suggest using an algorithm which is described in Knuth's The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Permutations. I found an online pdf of the draft here. The algorithm is also described in this wikipedia article.
Here's my own annotated implementation of the next_permutation algorithm, as a python generator function.
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]
Each yield of the algorithm has an amortized complexity of O(1), according to this question, but according to rici who commented below, this is only the case if all numbers are unique, which they are definately not in this case.
In any case, the number of yields provides a lower bound for the time complexity, and it is given by
(A + B)! / (A! * B!)
Then to find the real time complexity we need to sum the average complexity of each yield with the complexity of constructing the resulting string based on the permutation. If we multiply this sum with the above formula we get the total time complexity.
这篇关于如何交错或创建两个字符串的唯一排列(无递归)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
