множества

[thedeemon]

А вот задачка, может кто подскажет, как такие решаются.
Есть набор из 65000 множеств, в каждом множестве от 1 до 35000 элементов (элементы - 16-битные целые числа), причем распределение размеров весьма неравномерное: среднее число элементов около 50, медианное - 13, т.е. большая часть множеств имеет менее 20 элементов, но есть и содержащие десятки тысяч. Мне нужно уменьшить этот набор путем объединения "похожих" множеств так, чтобы минимизировать сумму размеров множеств, но с таким ограничением: объединение множеств A,В,С... в некое Х возможно лишь тогда, когда размер получающегося Х не более чем в К раз (скажем, К=4) больше, чем размер каждого из А,В,С... Т.е., например, нельзя объединять множество из 10 элементов с множеством из 100. Объединять непересекающиеся множества нет смысла, а чем сильнее множества пересекаются ("похожи"), тем выгоднее их объединить.

Самое оптимальное решение не требуется, можно предлагать эвристики. Наивные переборные решения многовато операций и/или памяти требуют. Желательно уложиться в 2 гига памяти и час процессорного времени.

Comments

[sleepy-drago.livejournal.com]

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

[thedeemon.livejournal.com]

Пример 1:
На входе набор множеств A=[1,2,3], B=[1,3,5], C=[4]. Параметр К=4.
На выходе набор А'=[1,2,3,5], C=[4] и указание, что A'=A+B.

Пример 2:
http://stuff.thedeemon.com/lj/sample.json.gz
Требование: сказать, какие множества объединить, чтобы в получившемся наборе множеств сумма их размеров получилась минимальной. С ограничением для К=3, например.

[sleepy-drago.livejournal.com]

первые впечатления 0)поглотить все подмножества. Дальше локальный критерий который выбирает пару текущих на объединение. Ограничение (K) заданное на исходные выглядит весьма произвольно и таким образом может создавать локальные минимумы ... Надо бы тренироваться на кошках чтобы понять. Правда сейчас после пары месяцев овертаймов нам разрешили побыть дома и это явно не один день =)
В сторону в очередной раз скачал golang и его парсер json мне пожаловался на последнюю запятую. Рукалицо. К тому же они не могут разобрать неполный объект и когда весь датасет это один объект ... =)