Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 09.06.2010, 19:27
Новичок

Отправить личное сообщение для madmech Посмотреть профиль Найти все сообщения от madmech
 
Регистрация: 28.10.2008
Сообщений: 3

Возникла проблема с генерацией заданного количества сочетаний
Передо мной стоит следующая задача. Есть некое множество элементов количеством n. Нужно сформировать заранее заданное количество случайных сочетаний (С из n по k) данного множества. Разумеется, предполагается, что это предустановленное количество должно быть значительно меньше общего числа сочетаний. Дополнительным требованием выступает необходимость совпадения частот, ну или хотя бы их близости, попадания каждого элемента во все подмножества (сочетания). Вторым требованием является обязательное наличие каждого элемента в хотя бы одном сочетании получившегося семейства сочетаний. Поясню на примере. Есть некое стартовое множество, состоящее из 5 элементов, каждый из которых для условности пронумеруем по порядку от 1 до 5. И надо сформировать 5 сочетаний по 2 элемента в каждом с указанными выше требованиями. Общее количество сочетаний: С из 5 по 2 = 10. В итоге должно получиться что-то вроде этого:
1.(1, 2)
2.(3, 4)
3.(2, 5)
4.(1, 4)
5.(3, 5)

Как видим, при данных стартовых условиях задачи частоты у всех элементов совпадают и равны 2.
Может быть, кто-нибудь знает, как к этой задаче можно подступиться? Или, может, существуют готовые решения, алгоритмы для моей или схожей задачи? Алгоритм генерации сочетаний у меня есть.
  #2  
Старый 10.06.2010, 20:03
гость

 
Сообщений: n/a

Могу предложить идею...
Делаеш свое множество, и делаеш массив для множества в котором будеш хранить количество использований элемента множества, в цикле будеш генерировать случайные множества и проверять их элементы на количество использований,если слишком много генерировать другое,мало добавлять...
  #3  
Старый 11.06.2010, 07:00
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

См. в сторону covering designs: http://www.ccrwest.org/cover.html
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Количество сочетаний k из n, где среди n могут быть повторения Сергей Васильев Задачи 2 27.01.2010 18:06
Ументшение количества цветов в рисунке гость Обработка изображений, звук, графика 7 03.06.2009 18:43
Округление до количества значащих чисел spoilt_child Реализация, исходники, языки 5 17.12.2008 16:37
Вывести значение целочисленного выражения, заданного в виде строки S в delphi SergeyHelpMe Математические алгоритмы 5 12.06.2008 12:59
алгоритм вывода всех размещений, и сочетаний с повторениями orange Реализация, исходники, языки 2 09.12.2007 16:25