Здравствуйте уважаемы программисты

Сегодня столкнулся с задачей, для решения которой не могу придумать алгоритм.
Вот упрощенная версия

Есть некий массив


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


Это был очень простой пример. Сложность начинается когда один элемент появляется в трех или более массивах. Сложно определить, какой элемент убрать из какого массива. Оптимальный результат - минимальное кол-во дубликатов (который нужно оставлять только в случае если без него получится пустой массив).

Почему то мне кажется что попахивает графами, но какими именно понять не могу.
Спасибо

Пример глупого алгоритма который я хочу избежать (шаг 1 - оставляем уникальные, шаг 2 - добавляем в пустые без какой либо логики, последовательно)

Задача недоопределена. Допускаю, что из всех возможных конечных вариантов можно выбрать любой, но что делать, если конечного варианта без дубликата не существует (напр., 3 массива с элементами 1 и 2)?

да



значит будет либо что-то вроде [1],[2],[1] или 1,2,2
Главное - минимальное кол-во дубликатов, и что бы все элементы присутсвовали хотя бы один раз

если объединить массивы в граф, то достаточно построить остовное дерево. элементы, образующие циклы, удалятся.

Можно поподробнее? Именно этот момент меня и путает. что здесь будет вершинами и что ребрами?

красным - удаляемые ребра. нужно следить, что бы в результате удаления средние узлы не превращались листья  (иначе получатся пустые массивы)

Понял, спасибо, попробую отпишусь  

Добавлено @ 18:28
Так проблема в том что тут же зависит от того в какой последовательности я парсю граф, вот у вас, явно было слева направо, так все получается правильно. А если пойти справа налево, то получится как у меня в примере.


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

Я чего то не понимаю да?

ЗЫ можно вас попросить в след. раз картинку на форум выкладывать (кроме как ссылкой) как прикрепленный файл, для меня если. На работе блокировка на неизвесные/непроверенные сайты

Это сообщение отредактировал(а) sQu1rr - 26.1.2015, 18:31

Давайте определим несколько моментов.
1) Задача - реальная или учебная?
2) Каково максимально возможное количество групп?
3) Каково максимально возможное количество элементов?
Дело в том, что есть подозрение, что задача-то - полненькая... при небольшом количестве элементов и групп вполне можно обойтись и полным перебором.

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


Разумеется можно, и, скорее всего, задача это подрузамевает. Но вопрос для меня - можно ли решить не перебором. Пусть не за полин. время, но и не за экспоненту

ага

вобщемто остовный граф тут скорее всего бесполезен, т.к. графов этих может быть много, а нужны только с определенными свойствами (числа всегда листья, листья только числа), которые через веса дуг никак не выразить. раз удалению подлежат определенные ребра, весь граф не требуется.

В принципе задачу можно перевести в матричную.
Есть прямоугольная матрица. Столбцы - элементы, строки - группы. Если элемент в группе - на пересечении 1, иначе 0. Задача - удалить (заменить нулями) максимально возможное количество единиц так, чтобы в каждом столбце и каждой строке осталось не менее одной единицы.

Добавлено через 3 минуты и 24 секунды
Эмпирически можно пойти приблизительно по такому пути (типа жадный алгоритм) - ищем единицу такую, чтобы суммарное количество единиц в её строке и её столбце было максимально по матрице, но по отдельности не было единичным. Заменяем на ноль. Повторяем до тех пор, пока удаётся удалять. Способ не гарантирует оптимума, но даст близкое к нему решение, и достаточно быстр.

Интересно, приду домой пораскину мозгами, спасибо

Решил так кому интересно. Можно оптимизировать, но решение думаю понятно (работает со всеми моими тестами по крайней мере). Приду домой опишу логику




Это сообщение отредактировал(а) sQu1rr - 29.1.2015, 15:35