Python merging two lists with all possible permutations

Question

I'm trying to figure out the best way to merge two lists into all possible combinations. So, if I start with two lists like this:

list1 = [1, 2]
list2 = [3, 4]

The resulting list will look like this:

[[[1,3], [2,4]], [[1,4], [2,3]]]

That is, it basically produces a list of lists, with all the potential combinations between the two.

I've been working through itertools, which I'm pretty sure holds the answer, but I can't come up with a way to make it act this way. The closest I came was:

list1 = [1, 2, 3, 4]
list2 = [5, 6, 7, 8]
print list(itertools.product(list1, list2))

Which produced:

[(1, 5), (1, 6), (1, 7), (1, 8), (2, 5), (2, 6), (2, 7), (2, 8), (3, 5), (3, 6), (3, 7), (3, 8), (4, 5), (4, 6), (4, 7), (4, 8)]

So it does all the possible combinations of items in each list, but not all the possible resulting lists. How do I get that to happen?

EDIT: The end goal is to be able to individually process each list to determine efficiency (the actual data I'm working with is more complex). So, in the original example above, it would work something like this:

list1 = [1, 2]
list2 = [3, 4]

Get first merged list: [[1,3], [2, 4]]
    Do stuff with this list
Get second merged list: [[1,4], [2, 3]]
    Do stuff with this list

If I got the "list of lists of lists" output I described above, then I could put it into a for loop and process on. Other forms of output would work, but it seems the simplest to work with.

Answer 1

repeat the first list, permutate the second and zip it all together

>>> from itertools import permutations, repeat
>>> a = [1, 2, 3]
>>> b = [4, 5, 6]
>>> list(list(zip(r, p)) for (r, p) in zip(repeat(a), permutations(b)))
[[(1, 4), (2, 5), (3, 6)],
 [(1, 4), (2, 6), (3, 5)],
 [(1, 5), (2, 4), (3, 6)],
 [(1, 5), (2, 6), (3, 4)],
 [(1, 6), (2, 4), (3, 5)],
 [(1, 6), (2, 5), (3, 4)]]

EDIT: As Peter Otten noted, the inner zip and the repeat are superfluous.

[list(zip(a, p)) for p in permutations(b)]