如何交织或创建两个字符串的唯一置换（不递归） [英] How can I interleave or create unique permutations of two strings (without recursion)
问题描述
问题是打印两个给定字符串的所有可能的交织。所以我用Python编写了一个工作代码，运行方式如下：
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
它出现在字符串的每个点，然后对于一个递归调用，它将当前元素视为属于第一个数组，并且在下一个调用中，属于另一个数组。因此，如果输入字符串为 ab 和 cd ，则会打印出 abcd ， acbd ， cdab ， cabd 等。 p1 和 p2 是指向数组的指针（因为Python字符串是不可变的，所以我正在使用数组！）。有人可以告诉我，这段代码的复杂性是什么，是否可以改进？我已经编写了类似的代码来打印给定数组中所有长度 k 的组合：
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
这也基于相同的原理。因此，总的来说，如何找到此类功能的复杂性，以及如何对其进行优化？ DP可以做这些吗？第一个问题的示例输入输出：
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
推荐答案
您的问题可以简化为创建特定列表的所有唯一排列问题。假设 A 和 B 是字符串 arr1 的长度和 arr2 。然后构造一个像这样的列表：
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
从此列表的唯一排列到两个字符串的所有可能交织存在一对一的对应关系（双射） arr1 和 arr2 。这个想法是让排列的每个值指定从哪个字符串中提取下一个字符。这是一个示例实现，显示了如何根据排列构造交织：
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'
我在此问题中找到了python邮件列表，询问如何以有效方式解决此问题。答案暗示了使用一种算法，该算法在Knuth的计算机编程艺术，第4卷，专着2：生成所有排列中进行了描述。我在此处找到了在线pdf文件。此维基百科文章中也描述了该算法。
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.
这是我自己的 next_permutation 算法的注释实现，作为python生成器函数。
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 = 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]
根据这个问题，但是根据下面评论的rici所说，只有所有数字都是唯一的，这是唯一的情况，但在这种情况下肯定不是。
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屋！
