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

• A simple rejection sampling can be much more efficient than the accepted answer if the sizes of two given lists are far from equal. It is almost as good in other cases. – Apass.Jack Mar 6 at 10:47
• A partial Fisher–Yates shuffle might be better, too. – Apass.Jack Mar 6 at 10:56

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

• I like it. You view it as picking from two lists and have a binary vector which decides from which you pick. Obvious in hindsight! – Nimitz14 Feb 19 at 14:58
• Doing a full shuffle requires distinct_permutations from more_itertools, just incase anyone else wonders how to do that – Nimitz14 Feb 19 at 15:30