交织两个字符串的所有可能方法

本文介绍了交织两个字符串的所有可能方法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试生成所有可能的方式来交织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-

将s的第i+1个字符附加到res

将t的第j+1个字符附加到res

Append the i+1 th character of s to res

Append the j+1 th character of t to res

我们继续进行递归，直到两个字符串的所有字符均已使用，然后将结果存储在字符串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.