Permutations between two lists of unequal length

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

Solution 1

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

Solution 2

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

Solution 3

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

Solution 4

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

Solution 5

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

View more solutions

Comments

[dm03514]

docs.python.org/library/itertools.html

[user1735075]

@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.

[interjay]

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.

[Bakuriu]

I agree with interjay. Please specify the result in the non-equal size case, otherwise it's not possible to provide a general solution.

[user1735075]

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.

[sloth]

How would the output look like for name = 'a', 'b', 'c' and number = 1, 2, 3?

[Bakuriu]

Is the order really important or is it enough to generate all of the "combinations" you want? Also A1 B2 == B2 A1?

[user1735075]

@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.

[ShadowRanger]

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? 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? 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).

[wim]

@ShadowRanger Just made the same mistake myself. I've now made an edit to remove fluff and misdirections from the question.

[user1735075]

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)

[sloth]

@user1735075 Have a look at the documentation

[Bakuriu]

@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.

[user1735075]

awesome..they document their algorithm. very helpful thank you interjay and mr. steak!

[interjay]

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.

[xpy]

@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.

[interjay]

@xpy The title is too short to explain everything. That's why you need to read the actual question.

[Philipp Schwarz]

Best solution! Thank you! Other solutions are either plain wrong or only work in specific cases like a > b etc.

[Dalker]

Most Pythonic solution! (and avoids unnecessary imports)

[m1nkeh]

i literally cannot get this to work, even with your example... all i get is a list of zip object.. :|

[Josh Friedlander]

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!

[Deepak Sharma]

Time complexity is O(n^2)

[Sabyasachi]

Bets solution!! Bare basics is the best way always

[Bernhard Wagner]

@logic provides what should be the accepted solution.

[toinbis]

Thanks, great answer!

[Mattwmaster58]

Sure, the time complexity is n^2, but surely this is completely unavoidable?