Определение комбинации вариантов выбора из списка наборов, которая даст максимальное количество уникальных чисел. ⇐ Python

[Anonymous]

Определение комбинации выборок из списка наборов, которая даст максимальное количество уникальных чисел.
Рассмотрим массив наборов, каждый из которых содержит произвольное количество целых чисел.< /p>

Код: Выделить всё

A = {1,2,3}
B = {1,3,4,5,6}
C = {4,5,6,10}
SETS = [A, B, C]

Каждому набору также присваивается соответствующее произвольное число, меньшее количества элементов в наборе. Назовем его номером выбора или Set_x.

Код: Выделить всё

A_x = 1
B_x = 4
C_x = 3
SELECTION_NUMS = [A_x, B_x, C_x]

Мне нужно выбрать номер Set_x любой комбинации элементов из каждого набора (например, любой 1 элемент из набора A, любые 4 элемента из набора B и т. д.), чтобы я мог выбрать наибольшее количество уникальных элементов в общей сложности. Как это можно сделать наиболее эффективным способом?
Например. если я выберу {1} ​​из A, {1,3,4,5} из B и {4,5,6} из C, то всего я бы выбрал {1,3,4,5,6} , или 5 уникальных элементов.
Но выбор {2} из A, {1,3,4,5} из B и {4,6,10} из C дает {1,2,3,4, 5,6,10} или 7 уникальных элементов. Это максимальное количество уникальных элементов, которые можно получить (как вычислено методом грубой силы ниже), и, следовательно, возможное решение моей проблемы.
(Дальнейшее расширение:
Теперь каждое целое число имеет соответствующее свойство, назовем его звездами, и может иметь значение от 1 до 5 звезд. Например, 1 соответствует 5 звездам, 2 — 3 звездам. Теперь Set_x будет критерием общего количества звезд, которые можно выбрать. т. е. {1,2} можно выбрать из набора D, при этом D_x = 8.)
Подход грубой силы:

Код: Выделить всё

import itertools
def brute_force(SETS, SELECTION_NUMS):
NUM_SETS = len(SETS)
all_perms = list()
for i in range(NUM_SETS):
all_perms_per_set = list()
for perm in itertools.permutations(SETS[i], r=SELECTION_NUMS[i]):
perm = set(perm)
all_perms_per_set.append(perm)
all_perms.append(all_perms_per_set)

MAX_NUM_ELEMENTS = sum(SELECTION_NUMS)
most_num_elements = 0
most_combined_set = set()
for combination in itertools.product(*all_perms):
combined_set = set().union(*combination)
if len(combined_set) > most_num_elements:
most_num_elements = len(combined_set)
most_combined_set = combined_set
if len(combined_set) == MAX_NUM_ELEMENTS:  #all selections are unique
break

return most_num_elements, most_combined_set

Некоторые возможные идеи, на которых я застрял:

• Подсчитайте вхождения каждого числа, например

  Код: Выделить всё

  count = {1: 2, 2: 1, 3: 2, 4: 2, 5: 2, 6: 2, 7: 0, 8: 0, 9: 0, 10: 1}

  Затем выберите элемент с наименьшим количеством вхождений, удалите его из всех наборов и повторите процесс. Но я не могу быть уверен, что это полностью надежно, например, в случае, когда наименьшее число встречается в нескольких наборах, какие критерии я использую, чтобы выбрать, из какого набора его выбрать?
• Изменение выборок в одном наборе за раз — путем создания уникальных выборок по одному набору за раз, пока не возникнет конфликтующий выбор; в этом случае мы изменяем выборку в одном из конфликтующих наборов. наборы. Я не уверен, сможет ли этот итерационный метод охватить все комбинации и достичь наиболее оптимальной комбинации; это также усложняется моей неспособностью определить теоретическое максимальное количество уникальных элементов, которые можно выбрать.

Подробнее здесь: https://stackoverflow.com/questions/791 ... -yield-the