python: weird list elements combination

Question

I have the two following lists:

l1 = [1, 2, ,3]  
l2 = [x, y]  

And would like to have all lists of 5 elements keeping the order of l1 only. Say:

[x, y, 1, 2, 3],  
[x, 1, y, 2, 3],  
[x, 1, 2, y, 3],  
[x, 1, 2, 3, y],  
[y, x, 1, 2, 3],  
[y, 1, x, 2, 3],  
[y, 1, 2, x, 3],  
[y, 1, 2, 3, x],  
[1, x, y, 2, 3],  
[1, x, 2, y, 3],  
[1, x, 2, 3, y],  
[1, y, x, 2, 3],  
[1, y, 2, x, 3],  
[1, y, 2, 3, x],  
...  
[1, 2, 3, y, x],  
...  
[1, 2, 3, x, y]  

Observe that the order of l1 is important and l2 is not. l2 elements run over l1+l2 positions but only the order of l1 is important. I'm struggling with this. Any help is appreciated.

Answer 1

I call this interspersing l1 with (the permutations of l2). You can do this in two steps: picking the positions, then permuting the positions. For insertion points, you can use a mask-based approach (permutations([True,True,False,False,False])) or an index-based approach (product(*[range(5)]*2)). Haven't gotten the latter technique to work yet.

from itertools import *

def interspersings(l1,l2):
    for mask in set(permutations([0]*len(l1) + [1]*len(l2))):  # sadly inefficient
        iters = [iter(l1), iter(l2)]
        yield [next(iters[which]) for which in mask]

for perm in permutations(l2):
    for interspersing in interspersings(l1,perm):
        print(interspersing)

Demo:

[1, 2, 'x', 'y', 3]
['x', 'y', 1, 2, 3]
[1, 2, 'x', 3, 'y']
[1, 2, 3, 'x', 'y']
['x', 1, 'y', 2, 3]
[1, 'x', 'y', 2, 3]
[1, 'x', 2, 'y', 3]
['x', 1, 2, 'y', 3]
[1, 'x', 2, 3, 'y']
['x', 1, 2, 3, 'y']
[1, 2, 'y', 'x', 3]
['y', 'x', 1, 2, 3]
[1, 2, 'y', 3, 'x']
[1, 2, 3, 'y', 'x']
['y', 1, 'x', 2, 3]
[1, 'y', 'x', 2, 3]
[1, 'y', 2, 'x', 3]
['y', 1, 2, 'x', 3]
[1, 'y', 2, 3, 'x']
['y', 1, 2, 3, 'x']

edit: Ah, the latter technique I mentioned was correctly implemented by Mark Longair at https://stackoverflow.com/a/10655695/711085 (it is much more efficient than this technique)

Answer 2

One way of doing this is to use itertools.combinations to pick out the indices of the final list into which you're going to put the elements of l1. Then, for each of those choices, use itertools.permutations to find all permutations of items in the second list. Then go through both of those lists, picking off of the front of either depending on whether the index is one that's supposed to be for an element for l1 or l2.

from itertools import combinations, permutations

l1 = [1, 2, 3]
l2 = ["x", "y"]

n = len(l1) + len(l2)

for c in combinations(range(0, n), len(l1)):
    cs = set(c)
    for p in permutations(l2):
        l1i = iter(l1)
        l2i = iter(p)
        print [ l1i.next() if i in cs else l2i.next() for i in range(0,n) ]

The output would be:

[1, 2, 3, 'x', 'y']
[1, 2, 3, 'y', 'x']
[1, 2, 'x', 3, 'y']
[1, 2, 'y', 3, 'x']
[1, 2, 'x', 'y', 3]
[1, 2, 'y', 'x', 3]
[1, 'x', 2, 3, 'y']
[1, 'y', 2, 3, 'x']
[1, 'x', 2, 'y', 3]
[1, 'y', 2, 'x', 3]
[1, 'x', 'y', 2, 3]
[1, 'y', 'x', 2, 3]
['x', 1, 2, 3, 'y']
['y', 1, 2, 3, 'x']
['x', 1, 2, 'y', 3]
['y', 1, 2, 'x', 3]
['x', 1, 'y', 2, 3]
['y', 1, 'x', 2, 3]
['x', 'y', 1, 2, 3]
['y', 'x', 1, 2, 3]