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.

Answer 2

Several other solutions have already been posted, but most of them generate the full list of interleaved strings (or something equivalent to it) in memory, making their memory usage grow exponentially as a function of the input length. Surely there must be a better way.

Enumerating all ways to interleave two sequences, of length a and b respectively, is basically the same as enumerating all a+b bit integers with exably b bits set. Each such integer corresponds to a distinct way to interleave the sequences, obtained by replacing every 0 bit with an element of the first sequence, and every 1 bit with an element of the second sequence.

Conveniently, there's a clever and efficient way to calculate the next integer with the same number of bits set, which we can use to generate all such integers. So let's do that first:

def bit_patterns(m, n):
    """Generate all m-bit numbers with exactly n bits set, in ascending order.
    See http://www.geeksforgeeks.org/next-higher-number-with-same-number-of-set-bits/
    """
    patt = (1 << int(n)) - 1
    if patt == 0: yield 0; return  # loop below assumes patt has at least one bit set!
    while (patt >> m) == 0:
        yield patt
        lowb = patt & -patt  # extract the lowest bit of the pattern
        incr = patt + lowb   # increment the lowest bit
        diff = patt ^ incr   # extract the bits flipped by the increment
        patt = incr + ((diff // lowb) >> 2)  # restore bit count after increment

Now we can use this generator to generate all ways to interleave any two sequences:

def interleave(a, b):
    """Generate all possible ways to interleave two sequences."""
    m = len(a) + len(b)
    n = len(a)
    for pattern in bit_patterns(m, n):
        seq = []
        i = j = 0
        for k in range(m):
            bit = pattern & 1
            pattern >>= 1
            seq.append(a[i] if bit else b[j])
            i += bit
            j += 1-bit
        yield seq

Note that, in order to try to be as generic as possible, this code takes arbitrary sequence types and returns lists. Strings are sequences in Python, so you can pass them in just fine; to convert the generated lists back into strings, you can concatenate their elements e.g. with "".join(), like this:

foo = "ABCD"
bar = "1234"
for seq in interleave(foo, bar):
    print("".join(seq))

There we go: a fully non-recursive efficient generator-based solution that uses very little memory even for long inputs, and only generates each output once (thus requiring no inefficient duplicate elimination step). And it even works in both Python 2 and 3.

Answer 3

Highly inefficient but working:

def shuffle(s,t):
    if s=="":
        return [t]
    elif t=="":
        return [s]
    else:
        leftShuffle=[s[0]+val for val in shuffle(s[1:],t)]
        rightShuffle=[t[0]+val for val in shuffle(s,t[1:])]
        leftShuffle.extend(rightShuffle)
        return leftShuffle

print(shuffle("ab","cd"))

Answer 4

You only need to compare the index of a to b and c to d then filter out those elements where index of a is greater than index of b and index of c is greater than index of d.

def interleave(s, t):
    mystring = s + t
    return [el for el in [''.join(item) for item in permutations(mystring) if  item.index('a') < item.index('b') and item.index('c') < item.index('d')]]

Demo:

>>> from itertools import permutations
>>> s = 'ab'
>>> t = 'cd'
>>> [el for  el in [''.join(item) for item in permutations(s+t) if item.index('a') < item.index('b') and item.index('c') < item.index('d')]]
['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']

Answer 5

Just for sports

a solution without explicit conditionals or predicates

(i.e., without any if keywords):

from itertools import chain, repeat, permutations
from copy import deepcopy


def shuffle(*strings):
    # Treat the strings as pools from which to draw elements in order.
    # Convert the strings to lists, so that drawn items can be removed:
    pools = (list(string) for string in strings)

    # From each pool, we have to draw as many times as it has items:
    pools_to_draw_from = chain.from_iterable(
        repeat(pool, len(pool)) for pool in pools
    )

    # Because itertools.permutations treats elements as unique based on their
    # position, not on their value and because pools_to_draw_from has repeated
    # repeated items, we would get repeated permutations, if we would not
    # filter them out with `unique`.
    possible_drawing_orders = unique(permutations(pools_to_draw_from))

    # For each drawing order, we want to draw (and thus remove) items from our
    # pools. Subsequent draws within the same drawing order should get the
    # respective next item in the pool, i.e., see the modified pool. But we don't
    # want the pools to be exhausted after processing the first drawing ordering.
    #
    # Deepcopy preserves internal repetition and thus does exactly what we need.
    possible_drawing_orders = (deepcopy(pdo) for pdo in possible_drawing_orders)

    # Draw from the pools for each possible order,
    # build strings and return them in a list:
    return [''.join(_draw(p)) for p in possible_drawing_orders]


def _draw(drawing_order):
    return (pool_to_draw_from.pop(0) for pool_to_draw_from in drawing_order)

We need a helper function for this:

from operator import itemgetter
from itertools import groupby

def unique(iterable, key=None):
    # Other than unique_everseen from
    # https://docs.python.org/3/library/itertools.html#itertools-recipes, this
    # works for iterables of non-hashable elements, too.
    return unique_justseen(sorted(iterable, key=key), key)


def unique_justseen(iterable, key=None):
    """
    List unique elements, preserving order. Remember only the element just seen.
    """
    # from https://docs.python.org/3/library/itertools.html#itertools-recipes
    return map(next, map(itemgetter(1), groupby(iterable, key)))

If the number of non-unique permutations is large, this is probably rather inefficient, due to the call to sorted. For alternatives to obtain unique permutations of non-unique values, see permutations with unique values.

TL;DR?

No problem. We can boil this approach down to this abomination:

from itertools import chain, repeat, permutations
from copy import deepcopy

def shuffle(*strings):
    return list({''.join(l.pop(0) for l in deepcopy(p)) for p in permutations(chain.from_iterable(repeat(list(s), len(s)) for s in strings))})

(Using a set comprehension on the result instead of ensuring uniqueness earlier.)