множества

[thedeemon]

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

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

Comments

[thedeemon.livejournal.com]

В общих чертах: есть множество сменяющих друг друга состояний, в которых возможны разные множества событий. Когда в некотором состоянии какое-то событие происходит первый раз, это "дорого", а если оно в этом состоянии уже происходило раньше, это "дешевле", причем чем меньше множество возможных событий в этом состоянии, тем "дешевле". Хочется объединить некоторые состояния, тем самым уменьшив число случаев, когда событие происходит впервые.

Подробнее не могу вдаваться, это секретный проект для ВМФ Монголии. :)

[wizzard]

Context mixing, поди