How to efficiently analyze all possible combinations of 2 large lists in python?

Question

Let's imagine we have 2 lists, each list having about 18 totally unique numbers under 1,000.

Now, we want to calculate all possible combinations of numbers inside each list (r from 1 to 18).

Then, we want to calculate all possible pairs of those combinations from the lists (pair is made out of one combination from list A, and another combination from the list B).

And finally, let's say we want to calculate the difference between those pairs by summing up all numbers within each side of the pair and then dividing the 1st part of the pair by the second part. Finally, we look at the result of each subtraction and pick the pair that produced the largest number.

I have tried to load all pairs into one big list, and then just do for pair in list:, but there are just too many possible pairs to load it all into one list. Therefore, we have to fort and analyze pairs in chunks. However, I am not sure what would be the most time and resource-efficient way to do it.

Here is an example of the code I tried to use:

from itertools import combinations, product
import random

list_A = random.sample(range(100, 250), 18)
list_B = random.sample(range(300, 450), 18)

# All possible combinations of items in list A
i = 1
all_list_A_combos = []
while i <= 18:
    all_list_A_combos_temp = combinations(list_A, i)
    all_list_A_combos.extend(all_list_A_combos_temp)
    i += 1

# All possible combinations of items in list B
i = 1
all_list_B_combos = []
while i <= 18:
    all_list_B_combos_temp = combinations(list_B, i)
    all_list_B_combos.extend(all_list_B_combos_temp)
    i += 1

# Executing this line crashes the program due to too many possible pairs
all_possible_pairs = list(product(all_list_A_combos, all_list_B_combos))

# Calculating products of division for each pair
list_of_all_differences = []
for pair in all_possible_pairs:

    side_A_sum = 0
    for number in pair[0]:
        side_A_sum += number
    side_B_sum = 0
    for number in pair[1]:
        side_B_sum += number

    difference = side_A_sum / side_B_sum
    list_of_all_differences.append(difference)

# Finding best pair
best_pair = all_possible_pairs[list_of_all_differences.index(max(list_of_all_differences))]
print(best_pair)

I understand that you can "cheat" by knowing that sum of all items in list A divided by the smallest number in list B is the correct answer, but I gave the product of division as just an example of the task. In my real case, analysis is a bit more complicated and you need to scan each possible pair to know for sure.

Answer 1

itertools is generator based. You seldom need to gather the results into lists. Just make your own generator:

import itertools

def subset_pairs(list_a,list_b):
    """iterator over all pairs of subsets, (s,t), with s drawn from list_a and t drawn from list_b"""
    for i in range(1+len(list_a)):
        for j in range(1+len(list_b)):
            for s in itertools.combinations(list_a,i):
                for t in itertools.combinations(list_b,j):
                    yield s,t

Here is a simple test (with the print as a stand-in for your processing):

for s,t in subset_pairs(['a','b','c'],[1,2]):
    print(s,"and",t)

Output:

() and ()
() and (1,)
() and (2,)
() and (1, 2)
('a',) and ()
('b',) and ()
('c',) and ()
('a',) and (1,)
('a',) and (2,)
('b',) and (1,)
('b',) and (2,)
('c',) and (1,)
('c',) and (2,)
('a',) and (1, 2)
('b',) and (1, 2)
('c',) and (1, 2)
('a', 'b') and ()
('a', 'c') and ()
('b', 'c') and ()
('a', 'b') and (1,)
('a', 'b') and (2,)
('a', 'c') and (1,)
('a', 'c') and (2,)
('b', 'c') and (1,)
('b', 'c') and (2,)
('a', 'b') and (1, 2)
('a', 'c') and (1, 2)
('b', 'c') and (1, 2)
('a', 'b', 'c') and ()
('a', 'b', 'c') and (1,)
('a', 'b', 'c') and (2,)
('a', 'b', 'c') and (1, 2)