from itertools import combinations, count
 
def interleave(a, b):
    empty = object()
    n = len(a) + len(b)
    # enumerate placements of a's items into n seats
    for a_indices in combinations(range(n), len(a)):
        L = [empty] * n
        for i, x in zip(a_indices, a): # put a's items into place
            L[i] = x
        it = iter(b)
        for i, x in enumerate(L): # fill empty seats with b's items
            if x is empty:
                L[i] = next(it)
        yield L
 
print(list(interleave([1,2], [3,4])))
 
def where(a, b, a_indices):
    """Yield a+b's items putting a's items at a_indices positions."""
    a, b, a_indices = iter(a), iter(b), iter(a_indices)
    ia = next(a_indices, -1)
    for i in count():
        if i == ia:
            yield next(a)
            ia = next(a_indices, -1)
        else:
            yield next(b)
 
def interleave_where(a, b):
    for a_indices in combinations(range(len(a) + len(b)), len(a)):
        yield where(a, b, a_indices)
 
print([list(g) for g in interleave_where([1,2], [3,4])])

ZnJvbSBpdGVydG9vbHMgaW1wb3J0IGNvbWJpbmF0aW9ucywgY291bnQKCmRlZiBpbnRlcmxlYXZlKGEsIGIpOgogICAgZW1wdHkgPSBvYmplY3QoKQogICAgbiA9IGxlbihhKSArIGxlbihiKQogICAgIyBlbnVtZXJhdGUgcGxhY2VtZW50cyBvZiBhJ3MgaXRlbXMgaW50byBuIHNlYXRzCiAgICBmb3IgYV9pbmRpY2VzIGluIGNvbWJpbmF0aW9ucyhyYW5nZShuKSwgbGVuKGEpKToKICAgICAgICBMID0gW2VtcHR5XSAqIG4KICAgICAgICBmb3IgaSwgeCBpbiB6aXAoYV9pbmRpY2VzLCBhKTogIyBwdXQgYSdzIGl0ZW1zIGludG8gcGxhY2UKICAgICAgICAgICAgTFtpXSA9IHgKICAgICAgICBpdCA9IGl0ZXIoYikKICAgICAgICBmb3IgaSwgeCBpbiBlbnVtZXJhdGUoTCk6ICMgZmlsbCBlbXB0eSBzZWF0cyB3aXRoIGIncyBpdGVtcwogICAgICAgICAgICBpZiB4IGlzIGVtcHR5OgogICAgICAgICAgICAgICAgTFtpXSA9IG5leHQoaXQpCiAgICAgICAgeWllbGQgTAogCnByaW50KGxpc3QoaW50ZXJsZWF2ZShbMSwyXSwgWzMsNF0pKSkKCmRlZiB3aGVyZShhLCBiLCBhX2luZGljZXMpOgogICAgIiIiWWllbGQgYStiJ3MgaXRlbXMgcHV0dGluZyBhJ3MgaXRlbXMgYXQgYV9pbmRpY2VzIHBvc2l0aW9ucy4iIiIKICAgIGEsIGIsIGFfaW5kaWNlcyA9IGl0ZXIoYSksIGl0ZXIoYiksIGl0ZXIoYV9pbmRpY2VzKQogICAgaWEgPSBuZXh0KGFfaW5kaWNlcywgLTEpCiAgICBmb3IgaSBpbiBjb3VudCgpOgogICAgICAgIGlmIGkgPT0gaWE6CiAgICAgICAgICAgIHlpZWxkIG5leHQoYSkKICAgICAgICAgICAgaWEgPSBuZXh0KGFfaW5kaWNlcywgLTEpCiAgICAgICAgZWxzZToKICAgICAgICAgICAgeWllbGQgbmV4dChiKQoKZGVmIGludGVybGVhdmVfd2hlcmUoYSwgYik6CiAgICBmb3IgYV9pbmRpY2VzIGluIGNvbWJpbmF0aW9ucyhyYW5nZShsZW4oYSkgKyBsZW4oYikpLCBsZW4oYSkpOgogICAgICAgIHlpZWxkIHdoZXJlKGEsIGIsIGFfaW5kaWNlcykKCnByaW50KFtsaXN0KGcpIGZvciBnIGluIGludGVybGVhdmVfd2hlcmUoWzEsMl0sIFszLDRdKV0p