Restricted Permutations of Strings in Python

Question

How can I do the following in Python?

Given two strings. Print all the interleavings of the two strings. Interleaving means that the if B comes after A, it should also come after A in the interleaved string. ex- AB and CD ABCD ACBD ACDB CABD CADB CDAB

Answer 1

This is effectively a tree-walking problem (namely, the decision tree of whether to advance along one string or the other). Oftentimes, the simplest way to approach a tree-walking problem is a recursive solution.

---

Here's an example:

def ordered_permutations(str1, str2):
    perms = []
    if len(str1) + len(str2) == 1:
        return [str1 or str2]
    if str1:
        for item in ordered_permutations(str1[1:], str2):
            perms.append(str1[0] + item)
    if str2:
        for item in ordered_permutations(str1, str2[1:]):
            perms.append(str2[0] + item)
    return perms

Answer 2

Hats off to @Amber for recognizing the problem and giving a very elegant solution to it.

Here's my two cents worth (just printing out the answers):

def interleave(L1, L2, answer=None):
    if answer is None:
        answer = ''
    if not L1 and not L2:
        print answer
    else:
        if L1:
            a = answer + L1[0]
            interleave(L1[1:], L2, a)
        if L2:
            ans = answer + L2[0]
            interleave(L1, L2[1:], and)

>>> interleave('ab', 'cd')
abcd
acbd
acdb
cabd
cadb
cdab

Hope this helps