7

I have a list L = [a, b, c] and I want to generate a list of tuples :

[(a,a), (a,b), (a,c), (b,a), (b,b), (b,c)...]

I tried doing L * L but it didn't work. Can someone tell me how to get this in python.

Xavier Ho
  • 17,011
  • 9
  • 48
  • 52
Schitti
  • 25,489
  • 8
  • 24
  • 21
  • This kind of "product" is also called a "Cartesian product" or "direct product" (I'm not sure if one term or the other is more appropriate here but the Python doc itself uses "Cartesian product.") – Tyler Jan 31 '10 at 05:20

7 Answers7

22

You can do it with a list comprehension:

[ (x,y) for x in L for y in L]

edit

You can also use itertools.product as others have suggested, but only if you are using 2.6 onwards. The list comprehension will work will all versions of Python from 2.0. If you do use itertools.product bear in mind that it returns a generator instead of a list, so you may need to convert it (depending on what you want to do with it).

Dave Kirby
  • 25,806
  • 5
  • 67
  • 84
15

The itertools module contains a number of helpful functions for this sort of thing. It looks like you may be looking for product:

>>> import itertools
>>> L = [1,2,3]
>>> itertools.product(L,L)
<itertools.product object at 0x83788>
>>> list(_)
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285
7

Take a look at the itertools module, which provides a product member.

L =[1,2,3]

import itertools
res = list(itertools.product(L,L))
print(res)

Gives:

[(1,1),(1,2),(1,3),(2,1), ....  and so on]
Alexander Gessler
  • 45,603
  • 7
  • 82
  • 122
3

Two main alternatives:

>>> L = ['a', 'b', 'c']
>>> import itertools
>>> list(itertools.product(L, L))
[('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'b'), ('b', 'c'), ('c', 'a'), ('c', 'b'), ('c', 'c')]
>>> [(one, two) for one in L for two in L]
[('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'b'), ('b', 'c'), ('c', 'a'), ('c', 'b'), ('c', 'c')]
>>>

the former one needs Python 2.6 or better -- the latter works in just about any Python version you might be tied to.

Alex Martelli
  • 854,459
  • 170
  • 1,222
  • 1,395
  • Using itertools seems odd to me if you're just going to convert directly to a list anyway. The list comprehension is probably more efficient, just as readable and probably more maintainable in that there are tweaks you can do directly to the expression. More abstraction can mean more inflexibility, and the whole point is to hide details which you *hope* (but can't be sure) you'll never need to worry about again. –  Jan 31 '10 at 02:14
0

x = [a,b,c] y = [] for item in x: for item2 in x: y.append((item, item2))

Maybe not the Pythonic way but working

Ilian Iliev
  • 3,217
  • 4
  • 26
  • 51
0

Ok I tried :

L2 = [(x,y) for x in L for x in L] and this got L square.

Is this the best pythonic way to do this? I would expect L * L to work in python.

Schitti
  • 25,489
  • 8
  • 24
  • 21
0

The most old fashioned way to do it would be:

def perm(L):
    result = []
    for i in L:
        for j in L:
            result.append((i,j))
    return result

This has a runtime of O(n^2) and is therefore quite slow, but you could consider it to be "vintage" style code.

inspectorG4dget
  • 110,290
  • 27
  • 149
  • 241
  • All approaches to this have O(n^2) runtime at best, the reason being they all have to generate O(n^2) tuples. Using an iterator such as itertools allows you to defer some of that work, but you can't avoid it completely. Your approach may even be O(n^3) - appending to lists may well be O(n) rather than O(1) because of memory reallocation issues, though I don't remember for sure. I *think* the Python list uses a resizable array - *not* a linked list. There could be some kind of append optimisation, though. A list comprehension *probably* preallocates the whole array at the start. –  Jan 31 '10 at 02:03