Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Помогите придумать алгоритм разделения множества, Разделение множества из N элементов 
:(
    Опции темы
crYon
Дата 8.3.2013, 12:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 26
Регистрация: 30.11.2006

Репутация: нет
Всего: нет



Здравствуйте.
Помогите, пожалуйста, придумать довольно простой алгоритм.

Есть некое неупорядоченное множество из N элементов. Нужен алгоритм перебора всех возможных вариантов разделения данного множества на две равные половины (т.е., содержащие по N/2 элементов каждая). В случае нечетного N - один элемент принадлежит обеим половинам.



Это сообщение отредактировал(а) crYon - 8.3.2013, 12:17
PM MAIL   Вверх
volatile
Дата 8.3.2013, 13:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 2
Всего: 85



Цитата(crYon @  8.3.2013,  12:08 Найти цитируемый пост)
придумать довольно простой алгоритм

Его уже давно придумали. Искать по фразе: "алгоритм генерации сочетаний"
У Кнута, например, целый том, посвящен этой теме.

Вам, в частности, нужна генерация сочетаний N/2 элементов из N

PM MAIL   Вверх
crYon
Дата 8.3.2013, 14:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 26
Регистрация: 30.11.2006

Репутация: нет
Всего: нет



Цитата(volatile @  8.3.2013,  13:53 Найти цитируемый пост)
Вам, в частности, нужна генерация сочетаний N/2 элементов из N

Да, я знаю как это можно сделать, используя грубую силу:
1) Сгенерировать все подмножества данного N-элементного множества.
2) Из них выбрать только те, которые содержат N/2 элементов. Это и будут все варианты "полумножества".
3) Привести каждому выбранному подмножеству в соответствие множество, содержащее элементы, в него не входящие (т.е., являющееся инверсией). Получатся пары "полумножество1"-"полумножество2".
4) Из этих пар удалить повторяющиеся.

Но в таком методе многовато лишних телодвижений, я надеялся найти способ поизящнее. Кроме того, пока не знаю как обходить случай с нечетным N.

Это сообщение отредактировал(а) crYon - 8.3.2013, 14:12
PM MAIL   Вверх
volatile
Дата 8.3.2013, 23:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 2
Всего: 85



Цитата(crYon @  8.3.2013,  14:11 Найти цитируемый пост)
Сгенерировать все подмножества данного N-элементного множества.

 smile
вы чего это, обалдели чтоле?

я же вам дал ключевое слово, что лень забить в поисковик?
Вот первая-же ссылка:
http://e-maxx.ru/algo/generating_combinations

ёклмн.

Добавлено через 2 минуты и 25 секунд
для вас: К = N/2, если еще не поняли.
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0929 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.