Учитывая N цветов и размер набора K. Все найденные группы наборов должны содержать все N цветов.
У меня есть алгоритм, который создает все (N выбирают K) различных наборов с K различными цветами в конкретном приказ. Цвета определены как перечисление и поэтому имеют определенный порядок среди них. Допустим, этот порядок начинается с заполнителя
None, Red = 1, Yellow, Green, Blue, Magenta, Orange, ...
Если, например, при N = 6 и K = 3 мой алгоритм создаст
List<HashSet<color>> {
(Red, Yellow, Green), (Red, Yellow, Blue), (Red, Yellow, Magenta), (Red, Yellow, Orange),
(Red, Green, Blue), (Red, Green, Magenta), (Red, Green, Orange),
(Red, Blue, Magenta), (Red, Blue, Orange),
(Red, Magenta, Orange),
(Yellow, Green, Blue), (Yellow, Green, Magenta), (Yellow, Green, Orange),
(Yellow, Blue, Magenta), (Yellow, Blue, Orange),
(Yellow, Magenta, Orange),
(Green, Blue, Magenta), (Green, Blue, Orange),
(Green, Magenta, Orange)
(Blue, Magenta, Orange)
}
С этими различными наборами возможно составить amount_of_groups = ((N выберите K) / (N / K)) с (N / K) = sets_per_group каждая, где для каждой группы цвета в каждом наборе не пересекаются и поэтому их объединение приведет к набору ровно всех N цветов. Так как я не мог придумать идею для создания этих групп самостоятельно, я пытаюсь перебрать полный список наборов и переместить их в группы, которые являются
List<List<HashSet<color>>>
, я попробовал два жадных подхода уже. Первый пытался составить одну полную группу за другой. Проблема, с которой я столкнулся, заключалась в том, что для задач, где sets_per_group> 2, алгоритм может попытаться построить группы таким образом, чтобы одна группа нуждалась в наборе, который уже используется в другой группе, и не выполняется. IE: для (6 выберите 2) алгоритм может выбрать:
{(Red, Yellow), (Green, Blue), (Magenta, Orange)} for group1
{(Red, Green), (Yellow, Blue)} for group2
=> the union of set1 and set2 are equal
=> algo fails to complete group2 because (Magenta, Orange) can't be chosen again and there is no other disjoint set left for group2 to pick.
Второй пытался начать все группы с начальных наборов, где все стартовые наборы имеют один цвет (ie. Все наборы, содержащие RED), а затем l oop по всем группам и в каждой итерации добавьте один пока непересекающийся набор в текущую группу, ЕСЛИ объединение пока не будет идентичным ни к одному объединению (за исключением последней итерации, конечно, где все группы союзов должны быть всех цветов). Проблема заключалась в том, что даже если это сработало для (6 выбирают 2) и (6 выбирают 3), начиная с (9 выбирают 3), группы начали блокировать друг друга от завершения, выбрав набор, который является единственным возможным последним набором для другой группы. как набор где-то в середине строительства. IE: для (9 выберите 3) = 84 различных набора (=> 28 групп по 3 набора в каждой) с перечислением цветов
None, Red = 1, Yellow, Green, Blue, Magenta, Orange, Cyan, Teal, Maroon, ...
алгоритм будет работать нормально для групп с 1 по 17, но для группы 18 и 19 и некоторые другие, следующие за проблемными группами c, выглядят следующим образом.
{(Red, Blue, Teal) , (Yellow, Cyan, Maroon)} //group 18 after the 2nd iteration. Can only be completed by (Green, Magenta, Orange)
{(Red, Blue, Maroon) , (Green, Magenta, Orange)} //group 19 after the 2nd iteration. Takes away (Green, Magenta, Orange) and prevents group 18's completion.
Затем я попытался изменить жадный подход # 2, чтобы проверить, имеет ли несвязанный набор, найденный во второй и последней итерации, все еще это соответствует закрывающему набору. Если это так, выделите его для его группы, которая будет добавлена позже (так что я все еще могу проверить объединение цветов до сих пор). В противном случае попробуйте отбросить непересекающийся набор и продолжить поиск другого возможного непересекающегося набора, все еще доступного.
В этом случае я все еще захожу в тупик, когда group18 обнаруживает, что все непересекающиеся наборы, которые он может попробовать в у второй до последней итерации больше нет доступных им замыканий.
Так что теперь мне нужно было бы либо вернуться назад / смотреть дальше, чем просто на последнюю итерацию, ИЛИ я мог бы попытаться, чтобы group18 потребовала другую группу «отбрасывать» это замыкание, а другой - как средство для выхода из тупиков, где свойство всех групп, имеющих замыкание всех цветов, уже не может быть удовлетворено. Подход с требуемыми отбрасываниями, вероятно, потребует способа сохранить, какая группа требует, какая другая группа, какое замыкание отбрасывать, чтобы предотвратить бесконечные циклы. Это уже звучит неловко сложно.
Кто-нибудь пытался решить подобную проблему? Я пытаюсь решить NP-сложную проблему? Пожалуйста помоги. Если вы решили рассмотреть мой код со мной, то это очень ценится.