Как качественно проанализировать все возможные комбинации 2-х больших списков в python? - PullRequest
Новая
       124

Как качественно проанализировать все возможные комбинации 2-х больших списков в python?

1 голос
/ 14 июля 2020

Давайте представим, что у нас есть 2 списка , каждый список содержит около 18 полностью уникальных номеров меньше 1000.

Теперь мы хотим вычислить все возможные комбинации чисел внутри каждого списка (r от 1 до 18).

Затем мы хотим вычислить все возможные пары этих комбинаций из списков (пара состоит из одной комбинации из списка A, и другая комбинация из списка B).

И, наконец, допустим, мы хотим вычислить разницу между этими парами , суммируя все числа на каждой стороне пары и затем разделив 1-я часть пары второй частью. Наконец, мы смотрим на результат каждого вычитания и выбираем пару, которая произвела наибольшее число .

Я попытался загрузить все пары в один большой список, а затем просто for pair in list:, но существует слишком много возможных пар, чтобы загрузить все в один список. Следовательно, мы должны сформировать и проанализировать пары порциями . Однако я не уверен, какой способ сделать это наиболее эффективно и с точки зрения затрат времени и ресурсов.

Вот пример кода, который я пытался использовать: 

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)

Я понимаю что вы можете «обмануть», зная, что сумма всех элементов в списке A, деленная на наименьшее число в списке B, является правильным ответом, но я привел произведение деления как просто пример задачи. В моем реальном случае анализ немного сложнее, и вам нужно просканировать каждую возможную пару, чтобы знать наверняка.

1 Ответ

1 голос
/ 14 июля 2020

itertools основано на генераторе. Редко нужно собирать результаты в списки. Просто создайте свой собственный генератор: 

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

Вот простой тест (с print в качестве замены для вашей обработки): 

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

Вывод: 

() 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)
...