Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Математика
        Кодирование перестановок.
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Математика" «

Переход к теме
<< Назад Вперед >>
Несколько страниц [ 1 2 3 ]
Модераторы: Roman Osipov, RKI, attention, paradise
  

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).
См., например, http://mathworld.wolfram.com/PartitionFunctionP.html
В Стенли тоже должно быть.

Всего сообщений: Нет | Присоединился: 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

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Несколько страниц [ 1 2 3 ]

Форум работает на скрипте © Ikonboard.com