Python cartesian product

Question

I have the following dictionary in Python:

{1: [('4', 0.761),
     ('6', 0.752),
     ('5', 0.741),
     ('15', 0.671),
     ('8', 0.657),
     ('1', 0.649),
     ('10', 0.649),
     ('11', 0.645),
     ('2', 0.637),
     ('7', 0.632),
     ('17', 0.632),
     ('19', 0.623),
     ('13', 0.623),
     ('20', 0.617),
     ('9', 0.617),
     ('3', 0.601),
     ('16', 0.601),
     ('14', 0.601),
     ('18', 0.594),
     ('12', 0.581)],
 2: [('4', 0.773),
     ('5', 0.755),
     ('6', 0.751),
     ('8', 0.666),
     ('11', 0.651),
     ('2', 0.642),
     ('12', 0.637),
     ('10', 0.637),
     ('17', 0.623),
     ('3', 0.617),
     ('16', 0.617),
     ('1', 0.612),
     ('18', 0.606),
     ('14', 0.606),
     ('13', 0.606),
     ('15', 0.599),
     ('7', 0.599),
     ('19', 0.599),
     ('9', 0.593),
     ('20', 0.562)]}

There are 2 keys in the dictionary (1 and 2). What i want to do is obtain the cartesian product between each combination of values... The first value in the tuple represent the number of an agent (e.g. '4') and the second value of the tuple represent the corresponding score.

Desired output is:

4,4, 0.767 (average between two values)

4,5 0,758

and so on...

Any idea to solve this?

Thanks.

OK, so what have you tried and what exactly is the problem with it? — jonrsharpe, Oct 13 '15 at 15:42
[Here](http://stackoverflow.com/questions/29451291/cartesian-product-in-c/29451414#29451414) is my `C++` implementation. Go ahead and try to understand what it does. Its relatively simple so you should be able to convert it to `Python` — sam, Oct 13 '15 at 15:44
I want to generate a final list of values, with the cartesian product considering 2 or more list in the dictionary. I tried with the itertools.product but i can't solve it yet... — M Arias, Oct 13 '15 at 15:47

score 0 · Answer 1 · answered Oct 13 '15 at 15:48

For this specific case (only two keys in the dictionary) the following should suffice:

[(x[0], y[0], (x[1]+y[1])/2) for x in d[1] for y in d[2]]

I'd include the full output, but it's 400 lines. Here's a portion of it.

[('4', '4', 0.767),
 ('4', '5', 0.758),
 ('4', '6', 0.756),
 ('4', '8', 0.7135),
 ('4', '11', 0.706),
 ('4', '2', 0.7015),

LetzerWille · Answer 2 · 2015-10-13T17:30:05.593

             import itertools
             from operator import  itemgetter
             # this a general solution and will compute cartesian product for
             # more than 2  lists in the dictionary 

        d = {1: [('4', 0.761),
                 ('6', 0.752),
                 ............
                 ('9', 0.593),
                 ('20', 0.562)]}

    # create product of tuples
    l = list(itertools.product(*d.values()))
    # use this to compute average
    avg = lambda x: (','.join(map(itemgetter(0),x)), float("{0:.3f}".format(sum(map(itemgetter(1),x)) / 2 )))
    print(*map(avg,l))

('4,4', 0.767) ('4,5', 0.758) ('4,6', 0.756) ('4,8', 0.714) ('4,11', 0.706) ('4,2', 0.702) ('4,12', 0.699) ('4,10', 0.699) ('4,17', 0.692) ('4,3', 0.689) ('4,16', 0.689) ('4,1', 0.686) ('4,18', 0.683) ('4,14', 0.683) ('4,13', 0.683) ('4,15', 0.68) ('4,7', 0.68) ('4,19', 0.68) ('4,9', 0.677) ('4,20', 0.661) ('6,4', 0.762) ('6,5', 0.754) ('6,6', 0.752) ('6,8', 0.709) ('6,11', 0.702) ('6,2', 0.697) ('6,12', 0.695) ('6,10', 0.695) ('6,17', 0.688) ('6,3', 0.684) ('6,16', 0.684) ('6,1', 0.682) ('6,18', 0.679) ('6,14', 0.679) ('6,13', 0.679) ('6,15', 0.675) ('6,7', 0.675) ('6,19', 0.675) ('6,9', 0.672) ('6,20', 0.657) ('5,4', 0.757) ('5,5', 0.748) ('5,6', 0.746) ('5,8', 0.704) ('5,11', 0.696) ('5,2', 0.692) ('5,12', 0.689) ('5,10', 0.689) ('5,17', 0.682) ('5,3', 0.679) ('5,16', 0.679) ('5,1', 0.676) ('5,18', 0.673) ('5,14', 0.673) ('5,13', 0.673) ('5,15', 0.67) ('5,7', 0.67) ('5,19', 0.67) ('5,9', 0.667) ('5,20', 0.651) ('15,4', 0.722) ('15,5', 0.713) ('15,6', 0.711) ('15,8', 0.669) ('15,11', 0.661) ('15,2', 0.657) ('15,12', 0.654) ('15,10', 0.654) ('15,17', 0.647) ('15,3', 0.644) ('15,16', 0.644) ('15,1', 0.641) ('15,18', 0.639) ('15,14', 0.639) ('15,13', 0.639) ('15,15', 0.635) ('15,7', 0.635) ('15,19', 0.635) ('15,9', 0.632) ('15,20', 0.617) ('8,4', 0.715) ('8,5', 0.706) ('8,6', 0.704) ('8,8', 0.661) ('8,11', 0.654) ('8,2', 0.649) ('8,12', 0.647) ('8,10', 0.647) ('8,17', 0.64) ('8,3', 0.637) ('8,16', 0.637) ('8,1', 0.635) ('8,18', 0.631) ('8,14', 0.631) ('8,13', 0.631) ('8,15', 0.628) ('8,7', 0.628) ('8,19', 0.628) ('8,9', 0.625) ('8,20', 0.61) ('1,4', 0.711) ('1,5', 0.702) ('1,6', 0.7) ('1,8', 0.657) ('1,11', 0.65) ('1,2', 0.645) ('1,12', 0.643) ('1,10', 0.643) ('1,17', 0.636) ('1,3', 0.633) ('1,16', 0.633) ('1,1', 0.631) ('1,18', 0.627) ('1,14', 0.627) ('1,13', 0.627) ('1,15', 0.624) ('1,7', 0.624) ('1,19', 0.624) ('1,9', 0.621) ('1,20', 0.606) ('10,4', 0.711) ('10,5', 0.702) ('10,6', 0.7) ('10,8', 0.657) ('10,11', 0.65) ('10,2', 0.645) ('10,12', 0.643) ('10,10', 0.643) ('10,17', 0.636) ('10,3', 0.633) ('10,16', 0.633) ('10,1', 0.631) ('10,18', 0.627) ('10,14', 0.627) ('10,13', 0.627) ('10,15', 0.624) ('10,7', 0.624) ('10,19', 0.624) ('10,9', 0.621) ('10,20', 0.606) ('11,4', 0.709) ('11,5', 0.7) ('11,6', 0.698) ('11,8', 0.655) ('11,11', 0.648) ('11,2', 0.643) ('11,12', 0.641) ('11,10', 0.641) ('11,17', 0.634) ('11,3', 0.631) ('11,16', 0.631) ('11,1', 0.629) ('11,18', 0.625) ('11,14', 0.625) ('11,13', 0.625) ('11,15', 0.622) ('11,7', 0.622) ('11,19', 0.622) ('11,9', 0.619) ('11,20', 0.604) ('2,4', 0.705) ('2,5', 0.696) ('2,6', 0.694) ('2,8', 0.651) ('2,11', 0.644) ('2,2', 0.639) ('2,12', 0.637) ('2,10', 0.637) ('2,17', 0.63) ('2,3', 0.627) ('2,16', 0.627) ('2,1', 0.625) ('2,18', 0.621) ('2,14', 0.621) ('2,13', 0.621) ('2,15', 0.618) ('2,7', 0.618) ('2,19', 0.618) ('2,9', 0.615) ('2,20', 0.6) ('7,4', 0.703) ('7,5', 0.694) ('7,6', 0.692) ('7,8', 0.649) ('7,11', 0.641) ('7,2', 0.637) ('7,12', 0.635) ('7,10', 0.635) ('7,17', 0.627) ('7,3', 0.625) ('7,16', 0.625) ('7,1', 0.622) ('7,18', 0.619) ('7,14', 0.619) ('7,13', 0.619) ('7,15', 0.615) ('7,7', 0.615) ('7,19', 0.615) ('7,9', 0.613) ('7,20', 0.597) ('17,4', 0.703) ('17,5', 0.694) ('17,6', 0.692) ('17,8', 0.649) ('17,11', 0.641) ('17,2', 0.637) ('17,12', 0.635) ('17,10', 0.635) ('17,17', 0.627) ('17,3', 0.625) ('17,16', 0.625) ('17,1', 0.622) ('17,18', 0.619) ('17,14', 0.619) ('17,13', 0.619) ('17,15', 0.615) ('17,7', 0.615) ('17,19', 0.615) ('17,9', 0.613) ('17,20', 0.597) ('19,4', 0.698) ('19,5', 0.689) ('19,6', 0.687) ('19,8', 0.645) ('19,11', 0.637) ('19,2', 0.633) ('19,12', 0.63) ('19,10', 0.63) ('19,17', 0.623) ('19,3', 0.62) ('19,16', 0.62) ('19,1', 0.617) ('19,18', 0.615) ('19,14', 0.615) ('19,13', 0.615) ('19,15', 0.611) ('19,7', 0.611) ('19,19', 0.611) ('19,9', 0.608) ('19,20', 0.593) ('13,4', 0.698) ('13,5', 0.689) ('13,6', 0.687) ('13,8', 0.645) ('13,11', 0.637) ('13,2', 0.633) ('13,12', 0.63) ('13,10', 0.63) ('13,17', 0.623) ('13,3', 0.62) ('13,16', 0.62) ('13,1', 0.617) ('13,18', 0.615) ('13,14', 0.615) ('13,13', 0.615) ('13,15', 0.611) ('13,7', 0.611) ('13,19', 0.611) ('13,9', 0.608) ('13,20', 0.593) ('20,4', 0.695) ('20,5', 0.686) ('20,6', 0.684) ('20,8', 0.641) ('20,11', 0.634) ('20,2', 0.629) ('20,12', 0.627) ('20,10', 0.627) ('20,17', 0.62) ('20,3', 0.617) ('20,16', 0.617) ('20,1', 0.615) ('20,18', 0.611) ('20,14', 0.611) ('20,13', 0.611) ('20,15', 0.608) ('20,7', 0.608) ('20,19', 0.608) ('20,9', 0.605) ('20,20', 0.59) ('9,4', 0.695) ('9,5', 0.686) ('9,6', 0.684) ('9,8', 0.641) ('9,11', 0.634) ('9,2', 0.629) ('9,12', 0.627) ('9,10', 0.627) ('9,17', 0.62) ('9,3', 0.617) ('9,16', 0.617) ('9,1', 0.615) ('9,18', 0.611) ('9,14', 0.611) ('9,13', 0.611) ('9,15', 0.608) ('9,7', 0.608) ('9,19', 0.608) ('9,9', 0.605) ('9,20', 0.59) ('3,4', 0.687) ('3,5', 0.678) ('3,6', 0.676) ('3,8', 0.633) ('3,11', 0.626) ('3,2', 0.621) ('3,12', 0.619) ('3,10', 0.619) ('3,17', 0.612) ('3,3', 0.609) ('3,16', 0.609) ('3,1', 0.607) ('3,18', 0.603) ('3,14', 0.603) ('3,13', 0.603) ('3,15', 0.6) ('3,7', 0.6) ('3,19', 0.6) ('3,9', 0.597) ('3,20', 0.582) ('16,4', 0.687) ('16,5', 0.678) ('16,6', 0.676) ('16,8', 0.633) ('16,11', 0.626) ('16,2', 0.621) ('16,12', 0.619) ('16,10', 0.619) ('16,17', 0.612) ('16,3', 0.609) ('16,16', 0.609) ('16,1', 0.607) ('16,18', 0.603) ('16,14', 0.603) ('16,13', 0.603) ('16,15', 0.6) ('16,7', 0.6) ('16,19', 0.6) ('16,9', 0.597) ('16,20', 0.582) ('14,4', 0.687) ('14,5', 0.678) ('14,6', 0.676) ('14,8', 0.633) ('14,11', 0.626) ('14,2', 0.621) ('14,12', 0.619) ('14,10', 0.619) ('14,17', 0.612) ('14,3', 0.609) ('14,16', 0.609) ('14,1', 0.607) ('14,18', 0.603) ('14,14', 0.603) ('14,13', 0.603) ('14,15', 0.6) ('14,7', 0.6) ('14,19', 0.6) ('14,9', 0.597) ('14,20', 0.582) ('18,4', 0.683) ('18,5', 0.674) ('18,6', 0.672) ('18,8', 0.63) ('18,11', 0.623) ('18,2', 0.618) ('18,12', 0.615) ('18,10', 0.615) ('18,17', 0.609) ('18,3', 0.605) ('18,16', 0.605) ('18,1', 0.603) ('18,18', 0.6) ('18,14', 0.6) ('18,13', 0.6) ('18,15', 0.597) ('18,7', 0.597) ('18,19', 0.597) ('18,9', 0.593) ('18,20', 0.578) ('12,4', 0.677) ('12,5', 0.668) ('12,6', 0.666) ('12,8', 0.623) ('12,11', 0.616) ('12,2', 0.611) ('12,12', 0.609) ('12,10', 0.609) ('12,17', 0.602) ('12,3', 0.599) ('12,16', 0.599) ('12,1', 0.597) ('12,18', 0.593) ('12,14', 0.593) ('12,13', 0.593) ('12,15', 0.59) ('12,7', 0.59) ('12,19', 0.59) ('12,9', 0.587) ('12,20', 0.572)

@MArias now it is more general, I have made ave func do not depend on number of tuple lists. — LetzerWille, Oct 13 '15 at 16:49

score 0 · Answer 3 · answered Oct 13 '15 at 18:01

Similar but using reduce to support arbitrary number of keys in the starting dict

from itertools import product

# this reduces a list of (agent, score) tuples into a tuple with
# ([list-of-agents], total_score)
reductor = lambda acc, element: (acc[0]+[element[0]], acc[1]+element[1])

# process one entry of the cartesian products
def process_product(product):
    (agents, total) = reduce(reductor, product, ([], 0.0))
    return "{0},{1:f}".format( ','.join(agents), total/len(agents) )

# product(*d.values()) returns the cartesian products - process+print 'm all
for x in map(process_product, product(*d.values())):
    print x

score 0 · Answer 4 · answered Mar 15 '16 at 22:03

If you prefer to generate the list manually, you can iterating over the index of the items in list L and increasing the indexes.

L = [2, 3, 4]

def generate_variant(L):
    index = [0] * len(L)
    while (index):
        print(index)
        index = next_index(index, L)

def next_index(index, L):
    n = len(index)
    i = n - 1
    while True:
        index[i] += 1
        if index[i] < L[i]:
            break
        index[i] = 0
        i -= 1
        if (i < 0):
            return None
    return index

generate_variant(L)


[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 0, 3]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
[0, 1, 3]
[0, 2, 0]
[0, 2, 1]
[0, 2, 2]
[0, 2, 3]
[1, 0, 0]
[1, 0, 1]
[1, 0, 2]
[1, 0, 3]
[1, 1, 0]
[1, 1, 1]
...
[1, 2, 3]

Python cartesian product

4 Answers4