Я ищу алгоритм, который сокращает список циклических циклов, восстанавливая данный набор как шаблон.
Каждый кортеж содержит id и набор, например (1, {'xy'})
.
пример
query = {'xyz'}
my_dict = [(1, {'x'}), (2, {'yx'}), (3, {'yz'}),
(4, {'z'}), (5, {'x'}), (6, {'y'}),
(7, {'xyz'}), (8, {'xy'}), (9, {'x'}),]
Цель состоит в том, чтобы как можно чаще воссоздать шаблон xyz
учитывая второе значение кортежей в my_dict
. Остальные элементы, из которых набор запросов не может быть полностью реконструирован, должны быть обрезаны, поэтому "уменьшить".
my_dict
содержит в общей сложности: 6 раз x
, 5 раз y
, 3 раза z
.
Учитывая my_dict
, действительными решениями будут, например:
result_1 = [(7, {'xyz'}), (8, {'xy'}), (4, {'z'}), (1, {'x'}), (3, {'yz'})]
result_2 = [(7, {'xyz'}), (2, {'yx'}), (4, {'z'}), (1, {'x'}), (3, {'yz'})]
result_3 = [(7, {'xyz'}), (9, {'x'}), (6, {'y'}), (4, {'z'}), (1, {'x'}), (3, {'yz'})]
Порядок кортежей в списке НЕ важен, я отсортировал их в порядке шаблона запроса xyz
с целью иллюстрации.
Цель
Цель состоит в том, чтобы иметь список кортежей, где общее количество вхождений элементов из набора запросов наиболее оптимально равномерно распределено.
result_1
, result_2
и result_3
содержат всего: 3 раза x
, 3 раза y
, 3 раза z
.
Кто-нибудь знает способ/подход, как это сделать?
Спасибо за вашу помощь!
В зависимости от вашего контекста приложения может потребоваться наивный подход грубой силы: используя функцию powerset
из этого SO-ответа,
def find_solutions(query, supply):
for subset in powerset(supply):
if is_solution(query, subset):
yield subset
Вам нужно будет реализовать функцию is_solution(query, subset)
которая возвращает True
когда данное подмножество поставки (my_dict.values()
) является допустимым решением для данного запроса.