У меня есть список, который выглядит следующим образом:
[(A1,B1), (A1,B2), (A2, B3),...]
Я хочу разделить его на N подмножеств (например, N = 5), с не более чем E элементами, такими, чтобы сумма числа уникальных значений в каждом подмножестве является минимальным. Значение является элементом кортежа в списке.
Например, если N = 3, E = 3, а список выглядит следующим образом:
[(1, a), (1 ,b), (2, a), (2, b), (2, c), (3, d), (4, d), (3, b)]
Решение будет :
[(1, a), (1 ,b)] -> 3 unique values (1, a, b)
[(2, a), (2, b), (2, c)] -> 4 unique values (2, a, b, c)
[(4, d), (3, b), (3, d)] -> 4 unique values (3, 4, b, d)
Конечно, я ищу heuristi c.
РЕДАКТИРОВАТЬ:
Мне пришло в голову, что эта проблема может быть приведен как проблема графа. Если вы видите каждое «значение» (A1, B1 и т. Д. c. В 1-м примере) как вершину, а каждый кортеж как ребро, это равносильно разбиению ребер.