我正在尝试生成所有可能的方式来交织Python中的任意两个任意字符串.
I am trying to generate all possible ways to interleave any two arbitrary strings in Python.
例如:如果两个字符串是'ab'和'cd',我希望得到的输出是:
For example: If the two strings are 'ab' and 'cd', the output I wish to get is:
['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']请参见a总是在b之前(并且c在d之前).我正在努力寻找解决方案.我已经尝试过itertools,如下所示:
See a is always before b (and c before d). I am struggling to find a solution to this. I have tried itertools as shown below:
import itertools def shuffle(s,t): string = s+t for i in itertools.permutations(string): print(''.join(i)) shuffle('ab','cd')但是,正如预期的那样,这将返回所有可能的排列,而与a和b(以及c和d)的顺序无关.
But as expected, this returns all possible permutations disregarding order of a and b (and c and d).
推荐答案想法
让您要插入的两个字符串为s和t.我们将使用递归生成所有可能的方式来交织这两个字符串.
The Idea
Let the two strings you want to interleave be s and t. We will use recursion to generate all the possible ways to interleave these two strings.
如果在任何时候我们已经将s的前i个字符和t的前j个字符进行交织,以创建某些字符串res,那么我们可以通过两种方式对它们进行交织下一步-
If at any point of time we have interleaved the first i characters of s and the first j characters of t to create some string res, then we have two ways to interleave them for the next step-
我们继续进行递归,直到两个字符串的所有字符均已使用,然后将结果存储在字符串lis的列表中,如下代码所示.
We continue this recursion till all characters of both the strings have been used and then we store this result in a list of strings lis as in the code below.
def interleave(s, t, res, i, j, lis): if i == len(s) and j == len(t): lis.append(res) return if i < len(s): interleave(s, t, res + s[i], i + 1, j, lis) if j < len(t): interleave(s, t, res + t[j], i, j + 1, lis) l = [] s = "ab" t = "cd" interleave(s, t, "", 0, 0, l) print l输出
['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']由于我们从未两次生成相同的字符串,因此这种实现方式(至少渐近地)具有尽可能高的效率.
This implementation is as efficient as we can get (at least asymptotically) since we never generate the same string twice.
更多推荐
交织两个字符串的所有可能方法
发布评论