Перестановки, Объясните [перемещено] Опции

[Lapp]

В принципе вот условие)

А в принципе, в чем проблема? ))

Пока я тут не вижу ничего реально связанного с перестановками, кроме названия. Можно было бы назвать.. скажем, Петей..

Петей порядка n называется последовательность из попарно различных целых положительных чисел p1, p2, ... , pn, где каждое 1 <= pi <= n. Будем говорить, что Петя q1, q2, ... , qn лексикографически меньше Пети p1, p2, . . . , pn, если существует такое i, что qi < pi, а для любого j < i pj = qj .

Циклическим сдвигом на k Пети p1, p2, ... , pn называется последовательность, pk+1, pk+2, ... , pn, p1, ... , pk. Отметим, что любой циклический сдвиг Пети также является Петей.

Ваша задача состоит в том, чтобы найти наименьший лексикографически циклический сдвиг заданного Пети

Как тебе такое? И короче вышло.. Извиняюсь, рука не поднялась писать Петя с маленькой буквы))).

Так в чем проблема? Дан Петя. Сдвигаешь его циклически и ищешь минимального.. Что именно непонятно?

[Cheburashka]

Тогда я так сказать приведу пару своих примеров и вы скажите правильно ли я это понимаю:
Есть к примеру перестановка 4213, лексиграфически меньшая получается здесь будет 1342. Я прав?
Или вот ещё пару
321 - 132.
DCBAE - AEDCB (43215 - 15432)
Если мои рассуждения не верны, скажи тогда как именно правильно будет выглядеть данная перестановка.

[Lapp]

Есть к примеру перестановка 4213, лексиграфически меньшая получается здесь будет 1342. Я прав?

Прав, Петя 4213 > Петя 1342.

Или вот ещё пару
321 - 132.
DCBAE - AEDCB (43215 - 15432)
Если мои рассуждения не верны, скажи тогда как именно правильно будет выглядеть данная перестановка.

А тут я ничего не понял . Зачем знак "минус"? Если хочешь сказать, кто больше/меньше, используй > или <. И ЗАЧЕМ ты перевел в буквы?? Это же внесет страшную путаницу, когда (и если) ты будешь действительно пользоваться ими как перестановками. Ты, что, действительно говоришь в магазине "дайте мне b.e кило колбасы", вместо того, чтоб сказать 2.5 кило?? Эта информация существенно цифровая! Она определяет номер позиции в упорядоченном множестве.

Перестановки должны содержать только цифры. Больше ничего, кроме цифр. Я имею в виду то определение перестановки, которое приведено тобой раньше.

А что касается сравнения перестановок на больше/меньше, то это выходит (в соответствии с приведенным тобой определением) простое сравнение чисел, если просто считать перестановки числами в n-ричной системе счисления. И если n<10, то простой взгляд на перестановки, как на числа, сразу дает ответ..

[Cheburashka]

321 > 132.
43215 > 15432

Я имел ввиду это) А что по поводу букв, то я видел такие задачи! Могу конечно привести пример если чуть трудно верится)))
Скажите правильно ли я понял циклическую перестановку по этим примерам

[Lapp]

321 > 132.
43215 > 15432

Я имел ввиду это) А что по поводу букв, то я видел такие задачи! Могу конечно привести пример если чуть трудно верится)))
Скажите правильно ли я понял циклическую перестановку по этим примерам

Вроде правильно.. Но немного странно, что у тебя сомнения. В таком простом вопросе сомнений быть не должно)). Циферки сзади переносишь вперед, k раз - вот и все.

Трудно верится. Приведи, плз.

[Cheburashka]

http://acmp.ru/index.asp?main=task&id_task=350
К примеру вот) Ну там частично идёт речь о перестановках. Ну так сказать спасибо Вам, если у меня будут в дальнейшем вопросы по этой теме, буду Вас просить о помоще.

[Lapp]

К примеру вот) Ну там частично идёт речь о перестановках.

Сергей, ты путаешь различные понятия.

В этом примере перестановкой называется само упорядоченное множество, точнее - его конкретное воплощение. В изначальном же условии авторы задачи ввели свое собственное определение некоторого объекта, который назвали перестановкой. Надо сказать, что это название в данной ситуации вполне логично, и упрекать авторов задачи не нужно. Само слово "перестановка" проискодит от глагола "переставлять" и может выражать как само действие переставления ("не могу пойти гулять - у нас дома перестановка мебели"), так и его результат ("как вам нравится наша новая перестановка?"). Посмотри в словаре, наверняка там есть оба значения. Так вот, в изначальном условии перестановка понимается как действие (потому мы и называли ее операцией), а в твоей последней ссылке - как результат (в данном случае ищутся различные результаты всех возможных операций по перестановкам).

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

[Cheburashka]

Назовем перестановку из N чисел 1…N K-перестановкой, если любые два соседних в ней элемента отличаются не более, чем на K.

Требуется найти число K-перестановок из N чисел от 1 до N.

В общем нашёл ещё одну интересную задачку на перестановки, и хотел бы спросить у Вас кое-что.
Для N=3 и K=1 существует 2 таких перестановки. (1, 2, 3) => (2, 3, 1) и (3, 2, 1).
А для N=4 и K=2 существует уже 12 перестановок. Не могли бы Вы объяснить почему именно 12 или разъяснить основную суть задачи?

[Lapp]

Для N=3 и K=1 существует 2 таких перестановки. (1, 2, 3) => (2, 3, 1) и (3, 2, 1).
А для N=4 и K=2 существует уже 12 перестановок. Не могли бы Вы объяснить почему именно 12 или разъяснить основную суть задачи?

Сергей, когда ты уже научишься наконец правильно ставить задачу и правильно выбирать раздел? Я всегда рад помочь (если могу), но следить за правильным наполнением Форума - моя обязанность (почетная)). Если воспринимать эту задачу как математическую и решать чисто аналитически (то есть вывести общую формулу), то это одно (и, думаю, это ооочень непросто). Но ты забыл сказать, что задачу-то нужно решать численно, т.к. она взята с олимпиады по информатике. И в этом случае она должна быть в разделе Задачи (переносить я не буду - замучился уже)). Я понимаю, что тема типа та же, но ты пойми, что комбинаторика - это целая большая отрасль математики. Как и в других областях, в ней есть задачи, которые решаются аналитически, и есть, которые численно. И не нужно всю ее лепить в одну тему. Выяснил основы предмета - решаешь задачи. Нужно выяснить еще что-то по ее теории - вернись сюда...

Объяснять тут численное решение не буду, флуд это. Надо - создай тему там, где надо. И приведи условие полностью (с ограничениями на N). Но могу сказать некое чисто аналитическое соображение: при любом N число 1-перестановок (то есть К=1) всегда равно 2. Это следует из того, что в этом случае годятся только восходящая и низходящая расстановки, больше никакие. Для других значений К (например, 2), все значительно усложняется

Еще, проверяй свои мессаджи на предмет ошибок, плз. Мне кажется, должно быть так:

Для N=3 и K=1 существует 2 таких перестановки. (1, 2, 3) => (1, 2, 3) и (3, 2, 1).

Ну, а как объяснить, что для N=4, К=2 получается 12? Вот так, например:

1 2 3 4
2 1 3 4
1 3 2 4
.. 3 1 2 4
.. 1 3 4 2
1 2 4 3

4 3 2 1
3 4 2 1
4 2 3 1
.. 2 4 3 1
.. 4 2 1 3
4 3 1 2