How can I match up permutations of a long list with a shorter list (according to the length of the shorter list)?

Question

I’m having trouble wrapping my head around a algorithm I’m try to implement. I have two lists and want to take particular combinations from the two lists.

Here’s an example.

names = ['a', 'b']
numbers = [1, 2]

the output in this case would be:

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

I might have more names than numbers, i.e. len(names) >= len(numbers). Here's an example with 3 names and 2 numbers:

names = ['a', 'b', 'c']
numbers = [1, 2]

output:

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

@dm03514 I saw that, and found examples for somewhat similar goals using itertools but I'm prototyping in python but will write the final code in another language so I do not want to use any tools that are not avail elseway. — user1735075, Oct 17 '12 at 13:19
What you are asking for doesn't really make sense. If the first list contains A,B,C and the second contains 1,2, what result would you expect? It could be done if the example you gave had 4 different results of one letter and one number each (A1, A2, B1, B2), or if both lists had to have the same size. — interjay, Oct 17 '12 at 13:24
I agree with interjay. Please specify the result in the non-equal size case, otherwise it's not possible to provide a general solution. — Bakuriu, Oct 17 '12 at 13:25
Hi Everyone, I updated the answer to show the output with 3 names and 2 numbers..I thought I explained it well, not sure why the downvote. — user1735075, Oct 17 '12 at 13:27
How would the output look like for `name = 'a', 'b', 'c'` and `number = 1, 2, 3`? — sloth, Oct 17 '12 at 13:32
Is the order really important or is it enough to generate all of the "combinations" you want? Also `A1 B2 == B2 A1`? — Bakuriu, Oct 17 '12 at 13:33
@Mr.Steak it would look like the example I had above with 2 names and 2 numbers but instead of 4 results there would be more because there are 3 items in the number list. bakuriu The order does not really matter, trying to capture the combinations. — user1735075, Oct 17 '12 at 13:37
Note for future folks dup-ing questions to this one: There is a decent chance that [Get the cartesian product of a series of lists?](https://stackoverflow.com/q/533905/364696) is a better duplicate target (lots of stuff that should use `product` is being duplicated here, even though this question is not properly solved that way). In rarer cases, [All possible replacements of two lists?](https://stackoverflow.com/q/44593640/364696) may be better (when selecting a value from one of two lists at each index, which is a `product` solution again, with a `zip` prepass). — ShadowRanger, Mar 05 '19 at 19:16
@ShadowRanger Just made the same mistake myself. I've now made an edit to remove fluff and misdirections from the question. — wim, Nov 11 '20 at 19:02
As far as I can tell, what OP was **actually** trying to do is generate permutations **of the names, whose length matches the length of the numbers**, and then combine each permutation's elements with the corresponding elements (i.e., `zip`ped together) from the numbers. That's a one-liner (`[list(zip(n, numbers)) for n in itertools.permutations(names, len(numbers))]`), but it's also clearly multiple separate steps (and a task that relatively few people would have). — Karl Knechtel, Mar 02 '23 at 00:40
The question demonstrably needs more focus (since solving it is a straightforward matter of applying those two steps) and demonstrably is unclear (since a bunch of the top answers interpreted something completely different). This is not at all a usable canonical. — Karl Knechtel, Mar 02 '23 at 00:41
I went through and attempted to fix everything that was duped to here, and also dealt with some other questions that were linked to here. — Karl Knechtel, Mar 02 '23 at 03:23

score 699 · Answer 1 · edited Oct 19 '22 at 07:19

699

The simplest way is to use itertools.product:

a = ["foo", "melon"]
b = [True, False]
c = list(itertools.product(a, b))
>> [("foo", True), ("foo", False), ("melon", True), ("melon", False)]

edited Oct 19 '22 at 07:19

pixelistik

7,541
3
32
42

answered Dec 01 '15 at 23:57

DrIDK

7,642
2
14
14

17

OP wasn't asking for a Cartesian product, and this answer (as well as most of the others) doesn't give the expected result specified in the question. – interjay Jul 18 '17 at 14:49
32

@interjay you are very right but as too many people seem to find this answer as correct then I can only assume that the title of the question is lacking context. – xpy Jul 20 '17 at 09:11
3

@xpy The title is too short to explain everything. That's why you need to read the actual question. – interjay Jul 20 '17 at 09:18
29

OP wanted permuations, but Google sends anyone looking for combinations (like me) to this answer - glad to see it's got 8 times the votes! – Josh Friedlander Dec 24 '18 at 15:38
1

@JoshFriedlander most of the people asking for any of these things don't understand the terminology; therefore, there are tons of questions that use the wrong terminology. Even if we close duplicates aggressively and make sure everything points at the correct duplicate for OP's problem, we then still end up with search misdirections. – Karl Knechtel Mar 02 '23 at 00:35

logic · Answer 2 · 2020-05-10T03:20:16.857

230

May be simpler than the simplest one above:

>>> a = ["foo", "bar"]
>>> b = [1, 2, 3]
>>> [(x,y) for x in a for y in b]  # for a list
[('foo', 1), ('foo', 2), ('foo', 3), ('bar', 1), ('bar', 2), ('bar', 3)]
>>> ((x,y) for x in a for y in b)  # for a generator if you worry about memory or time complexity.
<generator object <genexpr> at 0x1048de850>

without any import

edited May 10 '20 at 03:20

answered Aug 21 '16 at 13:33

logic

2,457
1
12
5

3

Best solution! Thank you! Other solutions are either plain wrong or only work in specific cases like a > b etc. – Philipp Schwarz Feb 16 '18 at 10:09
8

Most Pythonic solution! (and avoids unnecessary imports) – Dalker Aug 04 '18 at 09:40
8

Time complexity is O(n^2) – Deepak Sharma Jan 26 '19 at 18:41
3

Bets solution!! Bare basics is the best way always – Sabyasachi Feb 23 '19 at 16:50
Sure, the time complexity is n^2, but surely this is completely unavoidable? – Mattwmaster58 Mar 12 '22 at 01:15

score 140 · Accepted Answer · edited Apr 05 '20 at 20:47

140

Note: This answer is for the specific question asked above. If you are here from Google and just looking for a way to get a Cartesian product in Python, itertools.product or a simple list comprehension may be what you are looking for - see the other answers.

Suppose len(list1) >= len(list2). Then what you appear to want is to take all permutations of length len(list2) from list1 and match them with items from list2. In python:

import itertools
list1=['a','b','c']
list2=[1,2]

[list(zip(x,list2)) for x in itertools.permutations(list1,len(list2))]

Returns

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

edited Apr 05 '20 at 20:47

Bill

10,323
10
62
85

answered Oct 17 '12 at 13:35

interjay

107,303
21
270
254

3

The result is exactly what I want, but is it possible to share the logic behind how to do it? If I convert my code to C or Java, I won't have access to zip or itertools(although they make life very very easy) – user1735075 Oct 17 '12 at 13:39
3

@user1735075 Have a look at the [documentation](http://docs.python.org/library/itertools.html#itertools.permutations) – sloth Oct 17 '12 at 13:40
2

@user1735075: do you know that python is open source? So you may simply download the sources and see what do they do. +1 to Mr. Steak for pointing out that the documentation actually has a sample implementation that does not use `zip` and similar. – Bakuriu Oct 17 '12 at 13:42
awesome..they document their algorithm. very helpful thank you interjay and mr. steak! – user1735075 Oct 17 '12 at 13:42
2

i literally cannot get this to work, even with your example... all i get is a list of zip object.. :| – m1nkeh Aug 07 '18 at 10:00
1

@logic provides what should be the accepted solution. – Bernhard Wagner Jun 14 '19 at 20:44
can some one explain how can we calculate the total number of combinations? which is basically the length of the resulting array. – Arootin Aghazaryan Jun 10 '22 at 09:05
@m1nkeh in Python 3.x, [`zip` returns a special iterator rather than a list](https://stackoverflow.com/questions/27431390). This answer was edited later to show the use of `list` to work around the issue. – Karl Knechtel Mar 02 '23 at 00:44
@ArootinAghazaryan that is a completely separate question. Of course you can trivially ask for the `len` of that list like any other list, but counting permutations can be done much more directly and efficiently: see e.g. [counting combinations and permutations efficiently](https://stackoverflow.com/questions/2096573). – Karl Knechtel Mar 02 '23 at 00:46

score 32 · Answer 4 · answered Nov 29 '16 at 21:52

I was looking for a list multiplied by itself with only unique combinations, which is provided as this function.

import itertools
itertools.combinations(list, n_times)

Here as an excerpt from the Python docs on itertools That might help you find what your looking for.

Combinatoric generators:

Iterator                                 | Results
-----------------------------------------+----------------------------------------
product(p, q, ... [repeat=1])            | cartesian product, equivalent to a 
                                         |   nested for-loop
-----------------------------------------+----------------------------------------
permutations(p[, r])                     | r-length tuples, all possible 
                                         |   orderings, no repeated elements
-----------------------------------------+----------------------------------------
combinations(p, r)                       | r-length tuples, in sorted order, no 
                                         |   repeated elements
-----------------------------------------+----------------------------------------
combinations_with_replacement(p, r)      | r-length tuples, in sorted order, 
                                         | with repeated elements
-----------------------------------------+----------------------------------------
product('ABCD', repeat=2)                | AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations('ABCD', 2)                  | AB AC AD BA BC BD CA CB CD DA DB DC
combinations('ABCD', 2)                  | AB AC AD BC BD CD
combinations_with_replacement('ABCD', 2) | AA AB AC AD BB BC BD CC CD DD

score 21 · Answer 5 · answered Jul 24 '19 at 09:07

21

the best way to find out all the combinations for large number of lists is:

import itertools
from pprint import pprint

inputdata = [
    ['a', 'b', 'c'],
    ['d'],
    ['e', 'f'],
]
result = list(itertools.product(*inputdata))
pprint(result)

the result will be:

[('a', 'd', 'e'),
 ('a', 'd', 'f'),
 ('b', 'd', 'e'),
 ('b', 'd', 'f'),
 ('c', 'd', 'e'),
 ('c', 'd', 'f')]

answered Jul 24 '19 at 09:07

Ishan Rastogi

808
2
8
17

Thanks, great answer! – toinbis Aug 27 '19 at 15:30

score 14 · Answer 6 · answered Jul 29 '19 at 17:50

14

Or the KISS answer for short lists:

[(i, j) for i in list1 for j in list2]

Not as performant as itertools but you're using python so performance is already not your top concern...

I like all the other answers too!

answered Jul 29 '19 at 17:50

Fletch F Fletch

411
5
7

Using `itertools` is not more complicated, and the performance difference is minor. – Karl Knechtel Mar 02 '23 at 00:52

score 12 · Answer 7 · answered Jan 10 '17 at 19:26

12

You might want to try a one line list comprehension:

>>> [name+number for name in 'ab' for number in '12']
['a1', 'a2', 'b1', 'b2']
>>> [name+number for name in 'abc' for number in '12']
['a1', 'a2', 'b1', 'b2', 'c1', 'c2']

answered Jan 10 '17 at 19:26

Idanmel

457
4
12

score 10 · Answer 8 · edited May 23 '17 at 12:18

a tiny improvement for the answer from interjay, to make the result as a flatten list.

>>> list3 = [zip(x,list2) for x in itertools.permutations(list1,len(list2))]
>>> import itertools
>>> chain = itertools.chain(*list3)
>>> list4 = list(chain)
[('a', 1), ('b', 2), ('a', 1), ('c', 2), ('b', 1), ('a', 2), ('b', 1), ('c', 2), ('c', 1), ('a', 2), ('c', 1), ('b', 2)]

reference from this link

score 6 · Answer 9 · edited Feb 23 '21 at 11:14

6

Without itertools as a flattened list:

[(list1[i], list2[j]) for i in range(len(list1)) for j in range(len(list2))]

or in Python 2:

[(list1[i], list2[j]) for i in xrange(len(list1)) for j in xrange(len(list2))]

edited Feb 23 '21 at 11:14

VirtualScooter

1,792
3
18
28

answered Mar 11 '16 at 11:32

user3684792

2,542
2
18
23

score 5 · Answer 10 · answered Mar 11 '18 at 10:11

Answering the question "given two lists, find all possible permutations of pairs of one item from each list" and using basic Python functionality (i.e., without itertools) and, hence, making it easy to replicate for other programming languages:

def rec(a, b, ll, size):
    ret = []
    for i,e in enumerate(a):
        for j,f in enumerate(b):
            l = [e+f]
            new_l = rec(a[i+1:], b[:j]+b[j+1:], ll, size)
            if not new_l:
                ret.append(l)
            for k in new_l:
                l_k = l + k
                ret.append(l_k)
                if len(l_k) == size:
                    ll.append(l_k)
    return ret

a = ['a','b','c']
b = ['1','2']
ll = []
rec(a,b,ll, min(len(a),len(b)))
print(ll)

Returns

[['a1', 'b2'], ['a1', 'c2'], ['a2', 'b1'], ['a2', 'c1'], ['b1', 'c2'], ['b2', 'c1']]

Steve Alexander · Answer 11 · 2019-08-05T19:11:44.173

The better answers to this only work for specific lengths of lists that are provided.

Here's a version that works for any lengths of input. It also makes the algorithm clear in terms of the mathematical concepts of combination and permutation.

from itertools import combinations, permutations
list1 = ['1', '2']
list2 = ['A', 'B', 'C']

num_elements = min(len(list1), len(list2))
list1_combs = list(combinations(list1, num_elements))
list2_perms = list(permutations(list2, num_elements))
result = [
  tuple(zip(perm, comb))
  for comb in list1_combs
  for perm in list2_perms
]

for idx, ((l11, l12), (l21, l22)) in enumerate(result):
  print(f'{idx}: {l11}{l12} {l21}{l22}')

This outputs:

0: A1 B2
1: A1 C2
2: B1 A2
3: B1 C2
4: C1 A2
5: C1 B2

How can I match up permutations of a long list with a shorter list (according to the length of the shorter list)?

11 Answers11

Linked