Недавно искал алгоритм для расчета всех мультимножеств из заданного множества. Мультимножество удовлетворяет условию — сумма равна заданному числу. На самом деле нужно было перебрать все варианты периода времени от нескольких дней до недели, при условии, что весь период разбит на отрезки времени длиной в несколько часов (например 5,6, и 7).
Эти классы задач довольны известны: en.wikipedia.org/wiki/Subset_sum_problem
Что и привело меня к этому алгоритму: mathoverflow.net/questions/9477
Далее были приключения с «адаптацией» этого алгоритма, после чего идея была заброшена. Простой генератор с использованием product(given_set,repeat=count_items) и условием на сумму оказался самым шустрым вариантом!
После нескольких недель вернулся к данной задаче и понял, что для эффективности первоначального алгоритма нужно использовать графы или деревья. Анализ сложности алгоритмов пока у меня нет.
В итоге вот что получилось на этих выходных: nbviewer.ipython.org/gist/denfromufa/61b3ed4e902fd9d11d6a
Пока не хватает:
* обработки мусора, который скапливается в графе;
* ограничение на количество элементов в найденных мультимножествах.
* оптимизации по времени и памяти.
Но это уже гораздо лучше алгоритма по второй ссылке и моих недавних попыток.
