dimaniac
Удален
|
    
Народ, помогите решить задачку.
Пусть дана перестановка a1, a2,a3...an. Она кодируется следующим образом. Сравниваются первые 2 элемента если 1-й меньше ставится 1, иначе 0. Сравниваются 2-й и 3-й. Если 2-й меньше ставится снова 1 и т.д. Например 12345 кодируется 1111, 2413 - 101, 3412 тоже 101. Задача: по заданному коду определить число перестановок соответсвующих ему. Число перестановок n! число кодов 2^(n-1).
Самое умное, что я придумал, если все единицы или все нули, то только 1 перестановка. Т.к. число перестановок симметричных кодов одинаково, то в формуле наверняка есть сочетания. Больше мне в голову ничего не приходит.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 14 апр. 2005 7:07 | IP
|
|
Guest
Новичок
|
Множеством спуска перестановки p называется множество тех i, для которых p(i)>p(i+1). В твоей терминологии это множество тех номеров позиций в бинарной строке, на которых стоит 0. Например, для перестановки 12345 множество спуска пустое, для перестановок 2413 и 3412 - это множество {2}.
Пусть b_n(S) - количество перестановок n элементов, для которых множество спуска равно S. Пусть S состоит из элементов s[1] < s[2] < ... < s[k], доопределим s[0]=0 и s[k+1]=n. Справедливы следующие формулы:
b_n(S) = SUM (-1)^(k-j) multinomial(n;s[i1],s[i2]-s[i1],...,n-s[ij]),
где сумма берется по всем j от 0 до k и всем возможным индексам 1 <= i1 < i2 < ... < ij <= k. Мультиномиальный коэффициент вычисляется как обычно: multinomial(n;m1,...,mt) = n!/(m1!m2!...mt!)
b_n(S) = n! det[ 1/(s[j+1]-s[ i])! ],
где i,j=0..k индексируют элементы квадратной матрицы размером (k+1)x(k+1).
b_n(S) = det[ binomial(n-s[ i],s[j+1]-s[ i]) ],
где i,j=0..k как и в предыдущей формуле.
Дальнейшие подробности см. в книге Стенли "Перечислительная комбинаторика".
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 16 апр. 2005 9:00 | IP
|
|
dimaniac
Удален
|
Цитата: Guest написал 16 апр. 2005 9:00
Справедливы следующие формулы:
Возникает естественый вопрос почему?
Если объяснения есть у Стенли, тогда возникает другой вопрос: где взять эту книгу. Вообще-то она есть на lib.homelinux.org.Но вот блин облом, ещё неделю назад оттуда можно было свободно скачивать все что угодно, а буквально только что захожу и на тебе Authorization Required>:((
Кто-нибудь знает есть ли другие зеркала колхоза или ещё какие-нибудь e-lib'ы, откуда можно скачать эту книгу. Хотя вообще-то она вышла в марте в каком-то издательстве, но сами понимаете, это несколько дороговато.
(Сообщение отредактировал dimaniac 17 апр. 2005 2:06)
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 17 апр. 2005 2:05 | IP
|
|
dm
Удален
|
Но вот блин облом, ещё неделю назад оттуда можно было свободно скачивать все что угодно, а буквально только что захожу и на тебе Authorization Required
Читайте здесь всё внимательно!
(Сообщение отредактировал dm 17 апр. 2005 1:09)
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 17 апр. 2005 2:09 | IP
|
|
dm
Удален
|
Стенли есть и на хоумлинуксе, и не только. Юзайте poiskknig.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 17 апр. 2005 2:13 | IP
|
|
dimaniac
Удален
|
Скачал книгу,будем читать. Кстати посмотрел пароль, зря они его использовали, потому что тема про УДАЛЕНО МОДЕРАТОРОМ вроде как популярна в японии (во всяком случае так по телеку говорят).
И ещё одна задачка. Число представлено в виде суммы положительных чисел(как минимум 2-х). Посчитать число таких представлений.
Для 4 существует 4 представления 1+1+1+1, 1+1+2, 2+2, 1+3. Причем 1+3, то же что 3+1 поэтому сочетания с повторениями по-видимому не проходят. Я вообще-то программист и мог бы наверное посчитать динамическим программированием (ну рекурсией в крайнем случае), но хочестя с помощью какой-нибудь формулы.
(Сообщение отредактировал dm 18 апр. 2005 12:35)
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 17 апр. 2005 3:41 | IP
|
|
Guest
Новичок
|
Число представлено в виде суммы положительных чисел(как минимум 2-х). Посчитать число таких представлений.
Для 4 существует 4 представления 1+1+1+1, 1+1+2, 2+2, 1+3. Причем 1+3, то же что 3+1 поэтому сочетания с повторениями по-видимому не проходят.
Ответом будет т.н. число разбиений n, обозначаемое p(n).
См., например, внешняя ссылка удалена
В Стенли тоже должно быть.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 17 апр. 2005 9:49 | IP
|
|
dimaniac
Удален
|
Один хрен получается динамическое программирование только побыстрее и памяти тратится поменьше.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 18 апр. 2005 7:14 | IP
|
|
dimaniac
Удален
|
И еще одна задачка на разбиения.
Нужно посчитать не число разбиений, а сумму произведений слагаемых, причем порядок слагаемых теперь важен (перестановки с повторениями).
Например для 4:
sum = 1*1*1*1+1*1*2+1*2*1+2*1*1+2*2+1*3+3*1
В частности меня интересует чему равна эта сумма при числах порядка 30. И та же задача при условии, что число слагаемых в точности равно 10.
(Сообщение отредактировал dimaniac 21 апр. 2005 22:13)
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 21 апр. 2005 21:31 | IP
|
|
Guest
Новичок
|
Цитата: dimaniac написал 21 апр. 2005 21:31
И еще одна задачка на разбиения.
Нужно посчитать не число разбиений, а сумму произведений слагаемых, причем порядок слагаемых теперь важен (перестановки с повторениями).
Например для 4:
sum = 1*1*1*1+1*1*2+1*2*1+2*1*1+2*2+1*3+3*1
а где еще +4, соответствующее разбиению из одного слагаемого?
Цитата: dimaniac написал 21 апр. 2005 21:31
В частности меня интересует чему равна эта сумма при числах порядка 30. И та же задача при условии, что число слагаемых в точности равно 10.
Если зафиксировать чсило слагаемых k в разбиениях n, то ответом будет биномиальный коэффициент C(n+k-1,n-k). Для k=10 получим C(n+9,n-10).
Если число слагаемых нефиксировано, то надо просуммировать C(n+k-1,n-k) по k от 1 до n. Для n=4 получим 21.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 23 апр. 2005 4:19 | IP
|
|
|
Форум
Кодирование перестановок.
