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.

`[[[1,3], [2,4]], [[1,4], [2,3]]]` Why a list of lists of lists? Why not a list of lists? What are the criteria? When does an item go in the 1st or 2nd list? I would expect the expected result to be `[[1,3], [2,4], [1,4], [2,3]]` — Tim, Sep 07 '15 at 12:12
That's pretty much what itertools.product is giving me (just a list of tuples instead of a list of list). I'm not trying to find all the possible combinations of items on both lists, but all the possible lists I can produce by merging the two. I'm going to add another edit to try to explain in more plain English instead of just expected code output. — GeoJunkie, Sep 07 '15 at 12:17
Do you want all the possible interweavings of the two lists? Like what would happen during shuffling of cards. So the example `[1, 2], [3, 4]` would result in the sequences or so: `1 2 3 4 / 1 3 2 4 / 1 3 4 2 / 3 4 1 2 / 3 1 4 2 / 3 1 2 4`. — Dan D., Sep 07 '15 at 12:24
Padraic, not necessarily. I can always do sorts on the output list if needed. — GeoJunkie, Sep 07 '15 at 12:28
Dan, close to it, but there's no assumption that the same values - or even types - are in both lists. (In other words, this should work even if the lists are [1,2] and ['d', 'e']. — GeoJunkie, Sep 07 '15 at 12:29
If so, see http://stackoverflow.com/questions/15306231/how-to-calculate-all-interleavings-of-two-lists the definition `slot_combinations` computes that result. — Dan D., Sep 07 '15 at 12:42
Padraic, it appears there is an issue with what you provided in pastebin. It only outputs pairs, so when list1 = [1, 2, 3, 4] and list2 = [5, 6, 7, 8], then it produces output like: ((1, 5), (1, 6)) ((1, 7), (1, 8)) — GeoJunkie, Sep 07 '15 at 12:49
Yes, you need * len of the list http://pastebin.com/Bsjx4n6U — Padraic Cunningham, Sep 07 '15 at 12:56
what should the output for `list1 = [1, 2, 3];list2 = [5, 6, 7]` be, almost all the answers below return different output than your accepted answer so it is not clear what you actually want, the product or premutations — Padraic Cunningham, Sep 07 '15 at 13:03
The output from that would be: [[(1, 5), (2, 6), (3, 7)], [(1, 5), (2, 7), (3, 6)], [(1, 6), (2, 5), (3, 7)], [(1, 6), (2, 7), (3, 5)], [(1, 7), (2, 5), (3, 6)], [(1, 7), (2, 6), (3, 5)]] I had the tuples inside coming out as lists in my original request, but that's not really import since I don't need them to be mutable. — GeoJunkie, Sep 08 '15 at 16:31

pacholik · Accepted Answer · 2018-04-23T08:37:27.147

28

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)]

edited Apr 23 '18 at 08:37

answered Sep 07 '15 at 12:31

pacholik

8,138
9
46
52

5

What if the lists are of different lengths? This code doesn't work =0 – Alex Lenail Nov 23 '15 at 20:55
It is not clear what it should do if the list are asymmetric. Does it work for you if `b` is the longer? – pacholik Nov 24 '15 at 08:19

score 19 · Answer 2 · answered Sep 07 '15 at 16:29

19

The accepted answer can be simplified to

a = [1, 2, 3]
b = [4, 5, 6]
[list(zip(a, p)) for p in permutations(b)]

(The list() call can be omitted in Python 2)

answered Sep 07 '15 at 16:29

Peter Otten

406
2
3

score 14 · Answer 3 · answered Sep 13 '17 at 13:15

14

As @pacholik s answer does not cover lists of different length, here is my solution, using a list comprehension with two variables:

first_list = [1, 2, 3]
second_list = ['a', 'b']

combinations = [(a,b) for a in first_list for b in second_list]

The output looks like this:

[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b'), (3, 'a'), (3, 'b')]

answered Sep 13 '17 at 13:15

René Jahn

1,088
10
24

Which method is the fastest? Like if you have a large list and big sample set. If say 40million combinations which method produces that the fastest? – Jonathan Holloway Sep 16 '17 at 02:23
1

Covers lists of different lengths but does something completely different. This just produces a product. – pacholik Sep 19 '17 at 19:15
you are right, seems like I was too tired while reading the question... – René Jahn Sep 20 '17 at 07:03

score 12 · Answer 4 · answered Sep 07 '15 at 12:41

12

Try to use list generator to create the nested lists:

>>> [[[x,y] for x in list1] for y in list2]
[[[1, 3], [2, 3]], [[1, 4], [2, 4]]]
>>>

Or, if you want one-line list, just delete brackets:

>>> [[x,y] for x in list1 for y in list2]
[[1, 3], [1, 4], [2, 3], [2, 4]]

answered Sep 07 '15 at 12:41

Sdwdaw

1,029
7
14

As I understand the question, this does not answer it. – anderstood Jan 07 '19 at 22:37

Joe Smart · Answer 5 · 2015-09-07T12:31:33.147

2

Edited my code to give you your desired output.

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

for a in list1:
    new_list = []
    for b in list2:
        new_list.append([a, b])
    combined.append(new_list)

print combined

edited Sep 07 '15 at 12:31

answered Sep 07 '15 at 12:16

Joe Smart

731
3
7
28

Semih Yagcioglu · Answer 6 · 2015-09-07T12:50:21.617

2

You can create a list by constructing all the permutations of two list members with this, containing the list combinations.

lst1 = [1,2]
lst2 = [3,4]

#lst = [[j,k] for j in lst1 for k in lst2] # [[1,3],[1,4],[2,3],[2,4]]
lst = [[[j,k] for j in lst1] for k in lst2] # [[[1,3],[2,3]],[[1,4],[2,4]]]
print lst

edited Sep 07 '15 at 12:50

answered Sep 07 '15 at 12:16

Semih Yagcioglu

3,903
1
25
43

Padriac is right. That doesn't match what I'm looking for. It does match what itertools.product gives me, but isn't what I want. – GeoJunkie Sep 07 '15 at 12:24
I've revised mine below, I think it gives what you want now – Joe Smart Sep 07 '15 at 12:32

score 1 · Answer 7 · edited Sep 07 '15 at 13:30

1

Try this:

combos=[]
for i in list1:
      for j in list2:
          combos.append([i,j])
print combos

edited Sep 07 '15 at 13:30

Matthew Murdoch

30,004
30
91
126

answered Sep 07 '15 at 12:17

Luke Borowy

1,690
1
16
26

3

Formatting tip: you can indent your code with 4 extra leading spaces to make it a neat code block like in the other answers. – Lynn Sep 07 '15 at 12:20

Python merging two lists with all possible permutations

7 Answers7

Linked