the_grue: (Default)
История с работы. Коллеги изваяли алгоритм для нахождения в заданном множестве всех подмножеств заданной длины. Задача непростая, поэтому честные сотрудники указали в javadocs, что готовый алгоритм был взят из труда по дискретной математике Кеннета Х. Розена. Поскольку в этот код я засунул нос из чистого любопытства (мои сотрудники! алгоритм реализовали!), то в книжку я, конечно, не полез, но поверхностный анализ показал, что код действительно делает то, что надо, и даже эффективнее, чем я смог придумать сходу.

Тут мне стало совсем интересно - для чего это им вдруг понадобилась такая грамотная штука? Оказалось, что с ее помощью решают другую задачу - выделения из заданного множества всех подмножеств всех длин. То есть дано множество A размером n. Есть функция под условным названием findAllFixedSubsets(set,len) - о ней я рассказал выше (упрощаю; речь идет о Java, поэтому роль этой функции выполняют два класса, взаимодействующие по модели producer-consumer). В цикле, начиная с i=1, i<=n, мы вызываем findAllFixedSubsets(A, i). Все получающиеся подмножества записываем в общий Set.

Не знаю, насколько понятно у меня вышло описать ситуацию, но в этом месте мои брови вернулись на назначенное им природой место, а проснувшаяся было надежда на то, что я целых полтора года сильно недооценивал наш Server Team, исчезла без следа. Дело в том, что основная задача - нахождение подмножеств всех длин - гораздо проще той, которую решает функция findAllFixedSubsets, и решается она намного эффективнее с точки зрения и complexity, и памяти, рекурсивной функцией длиной в 5 строк.
Page generated Jul. 22nd, 2017 10:51 pm
Powered by Dreamwidth Studios