Python - Calculate combinations of different values as a sum

Question

Given a list of tuples as following:

values = [
    ('a', 'b', 'c'),
    ('d', 'e'),
    ('f', 'g', 'h')
]

I'd like to calculate different combinations of those values, but not as a cartesian product, rather as a sum on some custom rules. To clarify, if we calculate the cartesian product between those tuples, we will get 3*2*3 = 18 different combinations. But my desire is to get something like this:

combinations = [
    ('a', 'd', 'f'),
    ('a', 'e', 'g'),
    ('a', 'e', 'h'),
    ('b', 'd', 'f'),
    ('b', 'e', 'g'),
    ('b', 'e', 'h'),
    ('c', 'd', 'f'),
    ('c', 'e', 'g'),
    ('c', 'e', 'h')
]

So the resulting list contains 9 different combinations instead of 18. Example with 4 tuples:

values = [
    ('a', 'b', 'c'),
    ('d', 'e'),
    ('f', 'g', 'h'),
    ('i', 'j', 'k', 'l')
]

The result would be

combinations = [
    ('a', 'd', 'f', 'i'),
    ('a', 'e', 'g', 'j'),
    ('a', 'e', 'h', 'k'),
    ('a', 'e', 'h', 'l'),
    ('b', 'd', 'f', 'i'),
    ('b', 'e', 'g', 'j'),
    ('b', 'e', 'h', 'k'),
    ('b', 'e', 'h', 'l'),
    ('c', 'd', 'f', 'i'),
    ('c', 'e', 'g', 'j'),
    ('c', 'e', 'h', 'k'),
    ('c', 'e', 'h', 'l'),

]

To Explain the logic for the outputs further:

In both inputs, the first tuple is behaving as it would in a cartesian product. However, all the other tuples except the first are being iterated (or zipped) together. Additionally, if one of the tuples being iterated together "runs out of values" so to speak, we use the last value in the tuple instead.

What would be the efficient way to achieve this?

are there any rules for your combinations? For example, why `('a', 'e' ,'f')` is not there ? — Omri Attiya, Aug 19 '19 at 11:12
Wrong -> Possible duplicate of [Get the cartesian product of a series of lists?](https://stackoverflow.com/questions/533905/get-the-cartesian-product-of-a-series-of-lists) — tituszban, Aug 19 '19 at 11:13
@tituszban OP specifically says they don't want a Cartesian product — DeepSpace, Aug 19 '19 at 11:14
I think I understand the rule here. Take an element from the first list, then pair elm0 from list 2 with elm0 from list 3, then elm 1 from list 2 and elm 1 from list 3 etc, until you run out at list 2, then keep going with the last element of list 2 for the remainder of list three... — Neil, Aug 19 '19 at 11:15
Don't know how that will generalise though. Sorry to be a pain OP, but "what is the real problem?" maybe could help us. — Neil, Aug 19 '19 at 11:16
What is the behavior if the second list is longer than the first and third list @Neil? — Richard K Yu, Aug 19 '19 at 11:18
What *does* the OP want? This is unclear, because the logic for the output is not clarified by the OP at all. — Paritosh Singh, Aug 19 '19 at 11:18
I also want to know @RichardKYu. I don't know how to generalize. I don't know what the OP wants to achieve. — Neil, Aug 19 '19 at 11:19
@RichardKYu then it will keep grabbing the last elements from the first and last lists until it reaches the end of the second list — Hidayat Rzayev, Aug 19 '19 at 11:21
Sorry for not quite clear explanation. I was trying my best to explain in details what I need, I guess the question is a bit strange.. — Hidayat Rzayev, Aug 19 '19 at 11:26
@HidayetRzayev Do you want to write the logic for only lists of 3 tuples, or can there be more/less? If you want a generalized solution, can you show how it would behave with 4 tuples? — Paritosh Singh, Aug 19 '19 at 11:27
`for i in values[0]: for j in values[1]: if j=='d': print((i, 'd', 'f')) else: for k in values[2][1:]: print((i, j, k))` — ComplicatedPhenomenon, Aug 19 '19 at 11:27
@ParitoshSingh I edited the question and added the example with 4 tuples — Hidayat Rzayev, Aug 19 '19 at 11:33
I think the way to solve this is to make all the lists equal in length by adding the last character of all lists smaller than the max length list, then iterating through? — Richard K Yu, Aug 19 '19 at 11:41
@HidayetRzayev Alright, i have made a few edits to the question itself. Can you please check if there are any issues? — Paritosh Singh, Aug 19 '19 at 12:33
@ParitoshSingh everything seems to be fine. I also changed the title of the question a bit to not confuse those who can come across with a similar problem in the future — Hidayat Rzayev, Aug 19 '19 at 13:15

score 4 · Accepted Answer · answered Aug 19 '19 at 11:57

With the extra example provided, we can figure out how the logic will look. Essentially, the first row is being treated specially and used in the normal "cartesian product" sense.

However, the rest of the rows are being effectively extended to the largest length, and being zipped together. Coding that up, it can look something like follows:

from itertools import product


def extend_to_max_len(tup, length):
    '''extends a tuple to a specified length by
    filling the empty spaces with last element of given tuple
    '''
    fill_count = length - len(tup)
    return (*tup, *[tup[-1]]*fill_count)


def non_cartesian_sum(values):
    '''Expects a list of tuples.
    gives the output according to the custom rules:
    top: first row: to be used for cartesian product with zip of remaining rows
    bottom: remaining rows: extended to longest length before zipping
    '''
    if len(values) < 2:
        print("Check length of input provided")
        return None
    top = values[0]
    bottom = values[1:]
    max_len = max(len(row) for row in bottom)
    bottom = [extend_to_max_len(row, max_len) for row in bottom]
    out = [(first, *rest) for first, rest in product(top, zip(*bottom))]
    return out


values = [
    ('a', 'b', 'c'),
    ('d', 'e'),
    ('f', 'g', 'h'),
    ('i', 'j', 'k', 'l')
]

out = non_cartesian_sum(values)
print(out)

Output:

[('a', 'd', 'f', 'i'),
 ('a', 'e', 'g', 'j'),
 ('a', 'e', 'h', 'k'),
 ('a', 'e', 'h', 'l'),
 ('b', 'd', 'f', 'i'),
 ('b', 'e', 'g', 'j'),
 ('b', 'e', 'h', 'k'),
 ('b', 'e', 'h', 'l'),
 ('c', 'd', 'f', 'i'),
 ('c', 'e', 'g', 'j'),
 ('c', 'e', 'h', 'k'),
 ('c', 'e', 'h', 'l')]

Note that you may want to add more input validation as required, before using this function for your use case.

Thank you so much!! This works exactly as I wanted. Very smart solution — Hidayat Rzayev, Aug 19 '19 at 12:37

score 0 · Answer 2 · edited Aug 19 '19 at 11:30

This works for the data provided.

values = [
    ('a', 'b', 'c'),
    ('d', 'e'),
    ('f', 'g', 'h')
]


length_of_1 = len(values[1])
length_of_2 = len(values[2])

output = []
for item0 in values[0]:
    for i in range(max(length_of_1, length_of_2)):
        if i >= length_of_1:
            item1 = values[1][-1]
        else:
            item1 = values[1][i]
        if i >= length_of_2:
            item2 = values[2][-1]
        else:
            item2 = values[2][i]

        triple = (item0, item1, item2)
        output.append(triple)

for tup in output:
    print(tup)

Output:

('a', 'd', 'f')
('a', 'e', 'g')
('a', 'e', 'h')
('b', 'd', 'f')
('b', 'e', 'g')
('b', 'e', 'h')
('c', 'd', 'f')
('c', 'e', 'g')
('c', 'e', 'h')

score -4 · Answer 3 · answered Aug 19 '19 at 11:20

-4

Try this

values = [
    ('a', 'b', 'c'),
    ('d', 'e'),
    ('f', 'g', 'h')
]
combination = [(a,b,c) for a in values[0] for b in values[1] for c in values[2]]
print(combination)

answered Aug 19 '19 at 11:20

Sushant Nair

83
7

2

This is also cartesian product. – Neil Aug 19 '19 at 11:21

Python - Calculate combinations of different values as a sum

3 Answers3