Sort distributed couples from two lists

Question

Having two lists, I want to get all the possible couples. (a couple can be only one element from list 1 and another from list 2)

If I do a double "foreach" statement, I get it immediately (I am using python):

couples = []
for e1 in list_1:
    for e2 in list_2:
        couples.append([l1, l2])

How can I sort couples list in a way that elements be placed in a more distributed way? for example:

list_1 = [a,b,c]
list_2 = [1,2]

I will get:

[a, 1]
[a, 2]
[b, 1]
[b, 2]
[c, 1]
[c, 2]

And expect to be sorted to something like this:

[a, 1]
[b, 2]
[c, 1]
[a, 2]
[b, 1]
[c, 2]

What algorithm should I use to get this results?

Answer 1

To do the the way you want and you could flip the values:

>>> z = [[k, l] for l in x for k in y]
>>> z
[[1, 'a'], [2, 'a'], [3, 'a'], [1, 'b'], [2, 'b'], [3, 'b'], [1, 'c'], [2, 'c'], [3, 'c']]
>>> z.sort()
>>> z
[[1, 'a'], [1, 'b'], [1, 'c'], [2, 'a'], [2, 'b'], [2, 'c'], [3, 'a'], [3, 'b'], [3, 'c']]
>>> T = [[x[1], x[0]] for x in z]
>>> T
[['a', 1], ['b', 1], ['c', 1], ['a', 2], ['b', 2], ['c', 2], ['a', 3], ['b', 3], ['c', 3]]

Answer 2

You should check out itertools.product() from the stdlib.

Edit: I meant product(), not permutations().

import itertools

list_1 = ['a','b','c']
list_2 = [1,2]

# To pair list_1 with list_2 
paired = list(itertools.product(list_1, list_2))
# => [('a', 1), ('a', 2), ('b', 1), ('b', 2), ('c', 1), ('c', 2)]

# To get the sorting you desired:
wanted = sorted(paired, key=lambda x: x[1])
# [('a', 1), ('b', 1), ('c', 1), ('a', 2), ('b', 2), ('c', 2)]

Since product() returns an iterator, you don't need to cast it to a list() (and with large lists you probably shouldn't.) I just added that for illustration in this example should decide to test it yourself and want to print the values.

Answer 3

In pseudo code (not pretty sure about python's syntax) :

given list_1 of size n, and list_2 of size m:

couples = []
for i=0 to n-1
   for j=0 to m-1
      couples.append( [ list_1[i], list_2[ (i+j) % m] ] )

Answer 4

from itertools import islice, izip, cycle

list_1 = ['a','b','c']
list_2 = [1,2]

list(islice(izip(cycle(list_1), cycle(list_2)), len(list_1)*len(list_2)))

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