How get the permutation of two lists but the elements of each list remain in the same order? So if I have lst1 = [a, b] and lst2 = [x, y] the result would be:

[x, y, a, b]
[x, a, y, b]
[x, a, b, y]
[a, x, y, b]
[a, x, b, y]
[a, b, x, y]


I'm thinking about doing something recursive where I take the first element of a list, place it at the start, then recursively take the next element of that list and shift it through each position (and on each shift go through all remaining elements of that list).

But I'm wondering if there may be a nicer way to do this?

edit: Some more elaborate info here
Generate a string chi with len(lst1) 0s and len(lst2) 1s, e.g. for lst1 = [x, y] and lst2 = [a, b, c], you generate chi = [0, 0, 1, 1, 1].  Then you shuffle chi to obtain your "characteristic vector".  This new list will dictate the order in which to output elements from lst1 and lst2.

I hope this Python program speaks for itself:

from random import shuffle

def permutation(lst1, lst2, chi):
    idx1 = 0
    idx2 = 0
    for i in range(len(lst1) + len(lst2)):
        if chi[i] == '0':
            yield lst1[idx1]
            idx1 += 1
        else:
            yield lst2[idx2]
            idx2 += 1

lst1 = 'xy'
lst2 = 'abc'

chi = list('0' * len(lst1) + '1' * len(lst2))
shuffle(chi)
print(''.join(chi))
print(''.join(list(permutation(lst1, lst2, chi))))


Outputs:

11001
abxyc

10011
axybc

00111
xyabc