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
Все возможные способы чередования двух строк