交织两个字符串的所有可能方法 [英] All possible ways to interleave two strings

问题描述

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

1. 将s的第i+1个字符附加到res
2. 将t的第j+1个字符附加到res

1. Append the i+1 th character of s to res
2. 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.

这篇关于交织两个字符串的所有可能方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！