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

What have you tried? Do you have any code of your own yet, which you can show us? — Blckknght
– Blckknght, Commented Oct 26, 2012 at 23:03

Amber · Accepted Answer · 2012-10-26 23:19:01Z

8

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

edited Oct 26, 2012 at 23:19

answered Oct 26, 2012 at 23:04

Amber

531k89 gold badges643 silver badges558 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user1778424 Over a year ago

thank you, but it is returning an empty list when I run it...any ideas why? I am new to coding!

Amber Over a year ago

Was missing a base case. Fixed now. However, I'd suggest trying to figure out exactly how it's working so you can learn from it, rather than just asking other people to write your code for you.

inspectorG4dget · Accepted Answer · 2012-10-27 00:16:32Z

1

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

answered Oct 27, 2012 at 0:16

inspectorG4dget

115k30 gold badges159 silver badges253 bronze badges

Collectives™ on Stack Overflow

Restricted Permutations of Strings in Python

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related