| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Помогите придумать алгоритм разделения множества |
| Автор: crYon 8.3.2013, 12:08 |
| Здравствуйте. Помогите, пожалуйста, придумать довольно простой алгоритм. Есть некое неупорядоченное множество из N элементов. Нужен алгоритм перебора всех возможных вариантов разделения данного множества на две равные половины (т.е., содержащие по N/2 элементов каждая). В случае нечетного N - один элемент принадлежит обеим половинам. |
| Автор: volatile 8.3.2013, 13:53 | ||
Его уже давно придумали. Искать по фразе: "алгоритм генерации сочетаний" У Кнута, например, целый том, посвящен этой теме. Вам, в частности, нужна генерация сочетаний N/2 элементов из N |
| Автор: crYon 8.3.2013, 14:11 | ||
Да, я знаю как это можно сделать, используя грубую силу: 1) http://algolist.manual.ru/maths/combinat/subentities.php. 2) Из них выбрать только те, которые содержат N/2 элементов. Это и будут все варианты "полумножества". 3) Привести каждому выбранному подмножеству в соответствие множество, содержащее элементы, в него не входящие (т.е., являющееся инверсией). Получатся пары "полумножество1"-"полумножество2". 4) Из этих пар удалить повторяющиеся. Но в таком методе многовато лишних телодвижений, я надеялся найти способ поизящнее. Кроме того, пока не знаю как обходить случай с нечетным N. |
| Автор: volatile 8.3.2013, 23:58 | ||
 вы чего это, обалдели чтоле? я же вам дал ключевое слово, что лень забить в поисковик? Вот первая-же ссылка: http://e-maxx.ru/algo/generating_combinations ёклмн. Добавлено через 2 минуты и 25 секунд для вас: К = N/2, если еще не поняли. |
