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

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

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

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

Алгоритм подсчета числа перестановок с ограничениями
Здравствуйте! Помогите пожалуйста с алгоритмом подсчета числа перестановок:

Дано N ящиков и N предметов с массами Mi (1<=N<=80)

Разложением назовем распределение всех предметов по ящикам таким образом,
чтобы i-й ящик содержал только один предмет массой не менее MINi и не более
MAXi.

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

Дело в том что здесь требуется не только получить число всех перестановок (n!),
но и должны выполняться некоторые ограничения, к тому же учитываются
одинаковые по массе предметы. Как подсчитать это самое число способов? Заранее благодарен!
  #2  
Старый 25.12.2007, 08:51
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Виленкин Популярная комбинаторика (книга есть в инете, в частности, здесь: http://ilib.mccme.ru/ )

Генерировать все перестановки и выделять нужные для N=80, конечно, не получится.

Если не искать эффективного решения, то первое, что приходит в голову - делать рекурсивно - отсортировать предметы по размеру, получив примерно такое -
1 - 3 штуки, 2 -5 штук и т.д. (массив пар Size;Count)
Затем для предметов первого размера (Count = k) ищутся подходящие места (пусть их L), и генерируются соотв. комбинации - их С(L, K).
Для каждой комбинации все повторяется для второго размера и оставшихся мест и так далее.
  #3  
Старый 26.12.2007, 16:19
Новичок

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

Нельзя ли как-нибудь получить ответ одной или несколькими общими формулами?
  #4  
Старый 23.03.2008, 13:24
Пользователь

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

Сообщение от Rusl_K Посмотреть сообщение
Дело в том что здесь требуется не только получить число всех перестановок (n!),
но и должны выполняться некоторые ограничения, к тому же учитываются
одинаковые по массе предметы. Как подсчитать это самое число способов?
Ну во-первых, с учетом одинаковых по массе предметов нет особых проблем. Нужно лишь посчитать число требуемых размещений, считая их различными, а затем поделить результат на произведение факториалов кратностей масс предметов. То есть, например, если было 3 массы 1кг, 5 масс 2кг и одна масса 10кг, то разделить нужно будет на 3!*5!.
Поэтому можно изначально предполагать, что все предметы у нас разной массы. Причем можно так изменить ограничения MINi и MAXi и массы предметов Mi, что масса i-го предмета равна i (т.е. Mi=i), а все ограничения MINi и MAXi являются целыми числами.

Далее, общую формулу получить также можно, но она будет довольно сложной. Чтобы дать представление о ее природе рассмотрим случай MINi=0 для всех i, то есть когда нет ограничений по массе снизу. В этом случае ограничения на массу предметов можно представить доской Ферре, а каждое размещение будет соответствовать расположению N небьющих друг друга ладей на этой доске. Подробности смотрите в книге

Стенли. Перечислительная комбинаторика. Том I. Глава 2.4 и рядом.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм для представления длинного числа в компактной форме Hunter Математические алгоритмы 4 24.12.2007 12:50
алгоритм разбиения числа с ограничениями незарегистрированный Математические алгоритмы 0 18.04.2007 04:00
нужен алгоритм вычисления наибольшего множителя являющегося квадратом целого числа Alik Математические алгоритмы 5 31.01.2007 00:30
нужен алгоритм вычисления периодической и непереодической части дробного числа незарегистрированный Математические алгоритмы 3 20.01.2007 06:08
алгоритм преобразования числа в string незарегистрированный Обработка изображений, звук, графика 1 08.12.2006 12:59