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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 17.01.2009, 00:37
ugo ugo вне форума
Новичок

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

Разбиение множества.
Есть множество натуральных чисел, в множестве числа могут повторятся. Нужно найти колличество разбиений этого множества на k подмножеств, учитывая что числа могут повторятся в множестве, и разбиения отличающиеся порядком множеств следует считать одинаковыми.
  #2  
Старый 17.01.2009, 05:47
гость

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

Для случая неповторяющихся элементов - это числа Белла.
В общем случае решается методом динамического программирования (см. любое доказательство формулы для чисел Белла и обобщи)
  #3  
Старый 17.01.2009, 14:21
ugo ugo вне форума
Новичок

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

Спасибо, только наверно число стирлинга а не белла?
  #4  
Старый 17.01.2009, 14:35
гость

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

Ах, да, если число подмножеств фиксировано - то это числа Стирлинга.
  #5  
Старый 17.01.2009, 14:45
ugo ugo вне форума
Новичок

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

Это тоже решается динамикой?
  #6  
Старый 17.01.2009, 14:55
гость

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

Почему "тоже"?

Число разбиений мультимножества на k под-мультимножеств, да, можно посчитать динамикой.
  #7  
Старый 17.01.2009, 15:43
ugo ugo вне форума
Новичок

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

Расскажите пожалуйста как
  #8  
Старый 17.01.2009, 18:22
гость

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

Ну, идея такая - на каждом "макрошаге" мы будет генерировать все способы выбора одного подмножества. Для этого сначала положим в это подмножество наименьший из оставшихся элементов (чтобы зафиксировать порядок подмножеств), а потом переберем все возможные подмножества других элементов. Состояние динамики в макрошаге - это отсортированный список частот встречаемости каждого элемента, и число требуемых подмножеств.

Чтобы эффективно подсчитать число возможных подмножеств в макрошаге, внутри макрошага потребуется сделать еще одну простую вложенную динамику.
  #9  
Старый 17.01.2009, 18:47
ugo ugo вне форума
Новичок

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

Цитата:
Состояние динамики в макрошаге - это отсортированный список частот встречаемости каждого элемента
Как же такое можно реализовать?
  #10  
Старый 17.01.2009, 19:05
гость

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

Сообщение от ugo Посмотреть сообщение
Как же такое можно реализовать?
На C++, я бы хранил состояние динамики в vector<int>, первый элемент - число подмножеств, остальные - отсортированный список частот.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нахождение множества элементарных циклов графа kilobait Графы 9 17.03.2008 10:02
Покрытие множества кругами Tolran Вычислительная геометрия 3 29.11.2007 01:00
алгоритм нахождения минимального множества сечений контуров обратной связи ikro Графы 0 03.05.2007 11:00
разбиение плоскости фигурами ASH Вычислительная геометрия 1 17.03.2007 15:13
разбиение прямоугольника helium Вычислительная геометрия 5 03.03.2007 11:24