![]() |
|
![]() ![]() ![]() |
|
crYon |
|
|||
Новичок Профиль Группа: Участник Сообщений: 26 Регистрация: 30.11.2006 Репутация: нет Всего: нет |
Здравствуйте.
Помогите, пожалуйста, придумать довольно простой алгоритм. Есть некое неупорядоченное множество из N элементов. Нужен алгоритм перебора всех возможных вариантов разделения данного множества на две равные половины (т.е., содержащие по N/2 элементов каждая). В случае нечетного N - один элемент принадлежит обеим половинам. Это сообщение отредактировал(а) crYon - 8.3.2013, 12:17 |
|||
|
||||
volatile |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 2107 Регистрация: 7.1.2011 Репутация: 2 Всего: 85 |
||||
|
||||
crYon |
|
|||
Новичок Профиль Группа: Участник Сообщений: 26 Регистрация: 30.11.2006 Репутация: нет Всего: нет |
Да, я знаю как это можно сделать, используя грубую силу: 1) Сгенерировать все подмножества данного N-элементного множества. 2) Из них выбрать только те, которые содержат N/2 элементов. Это и будут все варианты "полумножества". 3) Привести каждому выбранному подмножеству в соответствие множество, содержащее элементы, в него не входящие (т.е., являющееся инверсией). Получатся пары "полумножество1"-"полумножество2". 4) Из этих пар удалить повторяющиеся. Но в таком методе многовато лишних телодвижений, я надеялся найти способ поизящнее. Кроме того, пока не знаю как обходить случай с нечетным N. Это сообщение отредактировал(а) crYon - 8.3.2013, 14:12 |
|||
|
||||
volatile |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 2107 Регистрация: 7.1.2011 Репутация: 2 Всего: 85 |
![]() вы чего это, обалдели чтоле? я же вам дал ключевое слово, что лень забить в поисковик? Вот первая-же ссылка: http://e-maxx.ru/algo/generating_combinations ёклмн. Добавлено через 2 минуты и 25 секунд для вас: К = N/2, если еще не поняли. |
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |