Какой есть алгоритм для оптимальной перегруппировки множеств (массивов)?

Question

[nikitakls]

Есть такой массив:

[18, 17, 48, 47] => A1
[18, 17, 14] => A2,
[48, 47] => A3
[18, 17, 48, 47, 42,] => A4
[32, 33] => A5
[18, 17, 48, 47] => A6
[14, 32, 33] => A7
[18, 14, 17, 47, 48] => A8
[17, 15, 14, 48, 32, 33, 47, 18] => A9
[14, 42] => A10
[42] => A11
[42] => A12

Нужно перегруппировать, чтобы получилось наименьшее количество множеств. И в них было максимальное количество элелементов
Должно получится так:

[48, 47] => [A1, A3, A4, A6, A8, A9],
[18, 17] => [A1, A2, A4, A6, A8, A9]
[32, 33] => [A5, A7, A9]
[15, 14] => A9
[42] => [A4, A10, A11, A12]
[14] => [A2, A7,  A8, A10]

Comments

[Akina]

Ну по сути эти твои массивы - это обычная битовая матрица (элементы массивов - подписи строк, имена массивов - подписи столбцов, или наоборот, вхождение элемента в массив - единичка, иначе нолик). Которую надо "повернуть".

И сдаётся мне, что задачка переборная.

Можно попытаться представить, что это матрица смежности, и попробовать алгоритмы кластеризации. Хотя навскидку не могу сообразить, насколько это оно.

Нужно перегруппировать, чтобы получилось наименьшее количество множеств. И в них было максимальное количество элементов

Вы уж определитесь, что ли. Критерий должен быть один, пусть и сложный, но никак не два.

[Wataru]

Ничего непонятно. Что значит перегрупировать? Как примерный вывод соответствует вводу? Любая пара число-АN, встречающаяся во входе должна быть в выводе, и строк должно быть минимальное количество?

[mayton2019]

наименьшее количество множеств. И в них было максимальное количество элелементов

Сдается мне здесь не будет единого решения. Как будто-бы не хватает еще одного критерия.

Вообще критений должен быть один. Некая вещественная функция которая дает уровень качества решения.
Как фитнес в ГА.

Вот где у нас тут чортов фитнес? Тут две величины. И как мы эту пару будем сравнивать с другими кандидатами?

[nikitakls]

Akina, Наверное если оставить одно условие - то должно быть наменьшее количество групп (группа это [48, 47] => [A1, A3, A4, A6, A8, A9]

Самому сложно объяснить что нужно заказчику, мне хотя бы найти как называется подобные задачи, чтобы можно было поискать варианты решения.

mayton2019, Согласен что не будет одного решения. Хотелось бы хотя б получить в какую сторону копать, чтобы можно было решить эту задачу

Wataru, должно быть минимальное количество групп.

[mayton2019]

Нарисуй себе в клеточной тетради матрицу. По вертикали - числа. По горизонтали буквы A1... e.t.c.
И поставь единички на пересечениях где есть атрибут.

И глазами увидешь что решений у тебя - много. Я не могу тебе пока ничего посоветовать.

Тут проблема - нечеткая постановка.

[Wataru]

nikitakls, И нельзя новые пары включать? А то, минимальное решение из одной группы можно сделать [17, 18, 47,48... (все числа)] => [A1,...,A12].

Вообще, если не удается четко сформулировать задачу, давайте исходную задачу. Что это за числа, что за группы? Какой у них смысл? Может вам вообще не то нужно, что вы спрашиваете. А так это что-то среднее между задачей о покрытии множеств и задачей упаковки.

[Akina]

nikitakls, ситуация, когда автор вопроса на просьбу уточнить постановку задачи отвечает "наверное" - это нонсенс. Тебе и правда пофиг, какую именно задачу решать?

[nikitakls]

mayton2019, Wataru, Akina, спасибо за идеи. Проблема в том что мне самому задачу нечетко поставили. И сейчас непонятно как ее можно четко сформулировать.
Посмотрел задачу о покрытии и задачу о назначении минимального количества исполнителей - возможно больше на них похоже, чем на другие

[Akina]

nikitakls,

Проблема в том что мне самому задачу нечетко поставили. И сейчас непонятно как ее можно четко сформулировать.

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

Answer 1

[Adamos]

Перебрать исходную кашу. Набрать массив

[14] => [A2, A7,  A8, A9, A10],
[15] => [A9],
[17] => [A1, A2, A4, A6, A8, A9],
[18] => [A1, A2, A4, A6, A8, A9],
[32] => [A5, A7, A9],
[33] => [A5, A7, A9],

...
И объединить ключи у тех, у которых одинаковый набор значений.

Comments

[Wataru]

Если я правильно понял, и задача состоит в том, чтобы разбить битовую матрицу на наименьшее количество единичных подматриц (вычеркивая строки и столбцы), то ваше решение не будет оптимальным.

[Adamos]

Wataru, зато оно позволяет обойтись без перебора, парой проходов.
А учитывая мутно сформулированную задачу - возможно, идеальный оптимум ТС и не нужен.

[mayton2019]

Битовая матрица - пушка. Стрельнет хорошо. Только надо прикинуть чтоб хватило памяти. Тут пахнет олимпиадными задачами. А они вечно дизайнят так чтоб ресурсы на грани были.