Python realization of permutation of 2 or more groups while keeping the ordering of the groups

Question

Having the exact same question like Permutation of 2 or more groups while keeping the ordering of the groups, I hope to write a function that could only keep those permutations that stay in order within groups.

However, I wonder if there is any manner to have the permutation on the fly. Currently, I am doing the exclusion in a post-hoc way, i.e. checking each generated permutation if it meets the group ordering criteria. You know, this is not quite scalable since takes so many unnecessary calculations: For two groups (c.f. size n and m), the operation number sums up to (m+n)! instead of (m+n)!/(n!·m!)).

Answer 1

Split up the permutations on which group the last element comes from. Then you can recursively intertwine the other groups and all but the last element of the chosen group, and add on the last element of the chosen group. This is a lift of (the generalization of) Pascal's identity for two groups: $$\binom{m + n}{m} = \binom{m + n - 1}{m - 1} + \binom{m + n - 1}{m}$$

Not very efficient python code for two lists (which should actually simplify a bit if you generalize to more than two):

def shuffle(a, b):
    if not a:
        yield b
        return
    if not b:
        yield a
        return
    x = a[-1]
    yield from (l + [x] for l in shuffle(a[:-1], b))
    x = b[-1]
    yield from (l + [x] for l in shuffle(a, b[:-1]))