All possible ways to interleave two strings

Question

I am trying to generate all possible ways to interleave any two arbitrary strings in Python.

For example: If the two strings are 'ab' and 'cd', the output I wish to get is:

['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']

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')

But as expected, this returns all possible permutations disregarding order of a and b (and c and d).

Answer 1

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.

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

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.

The Code

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

Output

['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.