我怎样才能交错或创建两个叮咬独特的排列（无递归） [英] How can I interleave or create unique permutations of two stings (without recursion)
问题描述
现在的问题是打印两个给定的字符串的所有可能的交错。所以我写了一个工作code在Python它运行是这样的：
高清跨（ARR1，ARR2，P1，P2，编曲）：
thisarr =拷贝（ARR）
如果P1 = = LEN（ARR1）和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）
其他：
thisarr.append（ARR1 [P1]）
国际米兰（ARR1，ARR2，P1 + 1，P2，thisarr）
德尔thisarr [-1]
thisarr.append（ARR2 [P2]）
间（ARR1，ARR2，P1，P2 + 1，thisarr）
返回
有正值在一个字符串中的每个点，那么对于1递归调用，则认为当前元素为属于第一阵列，并在接下来的呼叫，属于其他阵列。因此，如果输入的字符串 AB 和光盘，它打印出 ABCD ， ACBD ， CDAB ， CABD 等P1 。 P2 是指向数组（因为Python字符串是不可变的，我使用数组！）。谁能告诉我，这是什么code的复杂性，如果它可以改善或没有？我写了一个类似的code打印长度的所有组合 K 从给定的数组：
高清kcomb（ARR，我，thisarr，K）：
thisarr =拷贝（thisarr）
J，N = LEN（thisarr），LEN（ARR）
如果n-I＆LT; K-J或J＆GT; K：
返回
在j == K：
printarr（thisarr）
返回
如果我== N：
返回
thisarr.append（ARR [I]）
kcomb（ARR，I + 1，thisarr，K）
德尔thisarr [-1]
kcomb（ARR，I + 1，thisarr，K）
返回
这也适用同样的原则。因此，在一般情况下，如何找到这些功能的复杂性，以及如何对其进行优化？是否有可能通过DP做这些？样品输入输出的第一个问题：
＆GT;＆GT;＆GT; ARR1 = ['一'，'B'，'C']
＆GT;＆GT;＆GT; ARR2 = ['D'，'E'，'F']
＆GT;＆GT;＆GT;国际米兰（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 ，分别。然后构造这样一个列表：
[0] * A + [1] * B
存在一个到一从这个名单中的两个字符串的所有可能的交错的独特排列对应关系（双射） ARR1 和 ARR2 。我们的想法是让置换的每个值指定从采取下一个字符该字符串。下面是一个示例实现示出如何从一个排列构造的交织：
＆GT;＆GT;＆GT;高清make_interleave（ARR1，ARR2，排列）：
... iters = [国际热核实验堆（ARR1），ITER（ARR2）
...回报。加入（以置换iters [I]。接下来（）对我）
...
＆GT;＆GT;＆GT; make_interleave（AB，CDE，[1，0，0，1，1]）
cabde
我发现在Python邮件列表这个问题，这询问如何解决这个问题以有效的方式。这些问题的答案建议你使用它在Knuth的描述算法的计算机程序设计，第4卷的艺术，分册2：生成所有排列的。我发现
这里的 next_permutation 算法我自己的注解实现，作为一个python发生器功能。
高清unique_permutations（SEQ）：
收率以次只有独特排列以有效的方式。
Python实现了Knuth的算法L，也从已知
C ++的标准:: next_permutation功能，并作为置换算法
的纳拉亚纳班智达。
＃precalculate我们将迭代速度指数
i_indices =范围（LEN（SEQ） - 1，-1，-1）
k_indices = i_indices [1：]
＃算法规定开始与排序版本
SEQ =排序（SEQ）
而真正的：
收益率序列
＃从最后但酮标k工作向后
＃我们发现在值的第一减小的索引。 0 0 1 0 1 1 1 0
对于k在k_indices：
如果序列[K]＆LT;以次[K + 1]：
打破
其他：
＃介绍小幅未知蟒蛇换别的语法：
＃否则只执行，如果break语句从未达到。
＃如果是这样的话，以次弱减少，我们就大功告成了。
返回
＃获取项目从序列只有一次，速度
k_val =序列[K]
＃向后工作开始的最后一个项目，K I
＃找到比所述一个所述第一大一个将k 0 0 1 0 1 1 1 0
因为我在i_indices：
如果k_val＆LT;以次[我]：
打破
＃交换他们的最有效的方法
（SEQ [k]的，以次[I]）=（SEQ [I]，以次[k]的）＃K I
＃0 0 1 1 1 1 0 0
＃后反转的一部分，但不是k
＃包括K，也有效。 0 0 1 1 0 0 1 1
以次[K + 1：] =序列[-1：K：-1]
算法的每产量有O（1）摊销的复杂性，根据<一href="http://stackoverflow.com/questions/4973077/the-amortized-complexity-of-stdnext-permutation">this的问题，但根据RICI谁评论下面，这是仅当所有编号是唯一的，这是它们绝对不是在这种情况下的情况。
在任何情况下，产率的数目提供了一个下界的时间复杂度，并且它是由
定（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 = 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屋！
