В общем, достаточно давно я встретился с такой сложной темой (для меня) как перестановки. Сколько я не искал литературы на эту темы, но ничего стоющего не нашёл. Поэтому обратился именно к Вам.

Не могли бы Вы объяснить в чём основной смысл, и как они выполняются?

ммм.. что за перестановки? первый раз слышу

Ну я тут на одном сайте нашёл:

Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N. Количество различных перестановок порядка N равно N! = 1*2*3 ... * (N-1) * N.
Например, для N=3 существует всего 6 таких перестановок: (1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 1 2) и (3 2 1).

Вот а как с ними работать я вообще не могу понять!

что-то с комбинаторыи и теории вероятности школьного курса вспоминаю

А как работать с формулой Герона, ты понимаешь? Точно так же и с перестановками. Когда тебе понадобится посчитать количество перестановок (или найти все перестановки какого-то множества значений), тогда и начнешь с ними работать.

Или тебя что-то конкретное интересует?

а что тут понимать?

(в данных примерах числа в выборках не повторяются)
N! находит все возможные положения N чисел относительно друг друга.

С_n^k - находит количество таких k-элементных выборок(в которых имеется k елементов) из n элементов, в которых набор чисел всегда разный(НЕ учитывая взаимного расположения элементов).

A_n^k - тоже самое что и С_n^k, но только учитывая взаимное расположение элементов.

М

Сергей, большая просьба не валить все, что не задачи, в раздел Теория Паскаля. Прочти вот это, пожалуйста: КО ВСЕМ УЧАСТНИКАМ ФОРУМА

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

Перестановки легко понять на наивном уровне. Для начала подумай, например, сколько существует различных способов разложить три (в общем случае - N) разных шарика (a, b, c) в три (или N) разных места (1, 2, 3). Решение легко получить на листе бумаги, выписав все возможные варианты:

abc
acb
bac
bca
cba
cab

Получилось 6 перестановок. Проанализируй построение и результат и попробуй вывести общую формулу для раскладывания N предметов по N местам. Это "самая главная" формула, с ней ты легко поймешь и остальные.

Так, ну сейчас я хотя бы какое-то представление имею о понятии перестановки, но формулу вывести всё равно отсюда сложновато... Сейчас попытаюсь что-нибудь нахимичить.

смотри. например N=3. тогда
_ _ _ (произвольная комбинация из 3х чисел).
сколькими вариантами ты можешь поставить первое число на любое пустое место?
тремя.
1 _ _
второе число - двумя;
1 2 _
третье одним.
1 2 3
для нахождения количества комбинаций независимых опытов надо переумножить результаты отдельных опытов. 3*2*1.
то же самое для 4++.

С обычным понятием перестановки мне всё понятно (хотя формулу мне так и не удалось вывести).

sheka, Ну это я понимаю. А вот как быть к примеру вот с таким:

(И пример - 2 3 1. Ответ - 3 1 2).
Вот с этим я вообще разобраться не могу...

Все нужно проделать, и сразу станет ясно. Смотри..
Есть упорядоченное множество:

a b c

Берем перестановку из этого примера:

2 3 1

Действуем, как она указывает:
на первое место ставим второй элемент (b),
на второе место ставим третий элемент (с ),
на третье - первый (a).
В результате имеем:

b c a

Теперь мы имеем множество в новом порядке. Вопрос: какой должна быть перестановка, чтобы вернуться к старому порядку? Конструируем эту перестановку:
на первое место надо поставить a, а оно у нас имеет номер 3,
на второе место надо поставить b, а оно у нас имеет номер 1,
на третье место надо поставить c, а оно у нас имеет номер 2.
Записываем это в виде перестановки:

3 1 2

Это и есть ответ.
Ясно?

-----------------------

С формулой все просто. Я немного уточню, что sheka (извиняюсь, первоначально было amega) сказал.
Пусть число перестановок для множества из N шаров равно числу П(N). Попробуем на основании этого выяснить, чему равно число перестановок множества из N+1 шаров. Будем действовать за N+1 шагов:

1. Поставим на первое место шар номер 1. Остальные образуют множество из N шаров, его число перестановок равно П(N).
2. Поставим на первое место шар номер 2. Остальные образуют множество из N шаров, его число перестановок равно П(N).
3. Поставим на первое место шар номер 3. Остальные образуют множество из N шаров, его число перестановок равно П(N).
....
N. Поставим на первое место шар номер N. Остальные образуют множество из N шаров, его число перестановок равно П(N).
N+1. Поставим на первое место шар номер N+1. Остальные образуют множество из N шаров, его число перестановок равно П(N).

В результате на первом месте побывали все шары, причем по одному разу. Остальные шары расставлялись всеми возожными способами. Значит, мы выполнили все перестановки. Для того, чтобы найти их число, нужно сложить числа перестановок на всех шагах. В каждом из них П(N), всего шагов N+1. Следовательно, общее число перестановок равно:

П(N+1) = (N+1)*П(N)

Уже отсюда видно, что смахивает на факториал (но еще остается возможность включения некоторого коэффициента). Чтобы в этом убедиться, нужно рассмотреть начало: число перестановок множества из 1 шара равно 1. Это как раз совпадает с факториалом. Следовательно:

П(N) = N!

Из этого немного не понял...
Если у нас имеется изначально 2 3 1, то после вашего алгоритма она получается у меня пдругому...
2 3 1

1 3 2 (на первое место надо поставить a, а оно у нас имеет номер 3,)
3 1 2 (на второе место надо поставить b, а оно у нас имеет номер 1,)
3 2 1 (на третье место надо поставить c, а оно у нас имеет номер 2.)

Или я ошибаюсь?

Ты не понял постановку задачи. Попробую объяснить ее.

Есть упорядоченное множество. В моем примере я взял множество, состоящее из первых трех латинских букв и расставил их в естественном порядке:

a b c

Именно с этим множеством мы будем работать.
Далее, нам дают некоторое правило, по которому мы будем переставлять буквы. Правило записывается так:

2 3 1

Первой стоит двойка. Это значит, что на первое место надо поставить второй элемент множества (у нас это b).
Второй стоит тройка. Это значит, что на второе место надо поставить третий элемент множества (у нас это c).
Третьей стоит единица. Это значит, что на третье место надо поставить первый элемент множества (у нас это a).
В результате получаем:

b c a

Тут важно, что тройка букв - это само множество, а тройка чисел - это запись операции над этим множеством. Как, например, над обычными числами можно придумать операцию Oper=*2, которая будет обчное число умножать на два. Или, скажем, операция cube="возведение в куб". К первой операции обратной будет умножение на 0.5, то есть oper^-1=*0.5, а ко второй операции обратной будет такая: cube^-1="извлечение кубического корня". Минус единица вверху - это просто обозначение обратной операции. Еще пример: операция cycle, которая циклически переставляет буквы:

cycle(a b c) = c a b

Тогда обратная операция будет переставлять тоже циклически, но в другом направлении:

cycle^-1(a b c) = b c a

Тогда

cycle^-1(cycle(a b c)) = a b c

Еще можно заметить, что двукратное применение cycle к множеству из трех букв эквивалентно применению cycle^-1. То есть cycle²=cycle^-1.

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


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

С предыдущим постом понятно, а вот с новым опять нове проблемы)

Я попытался вычислить у меня получается так. Воде правильно (cycle²=cycle^-1)
abc
acb
cab
cba
bca

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

Но может, ты не понимаешь слово "циклически"? Циклически, зачит так:
12345
23451
34512
45123
51234
И можно в обратную сторону:
12345
51234
45123
...
Но не зацикливайся (извиняюсь за каламбур)) на этом, это был всего лишь пример понятия операции. Это все были унарные операции (над одним объектом - число, множество..). Обычное сложение, например - это бинарная операция, в ней участвуют 2 числа. В бинарных операциях тоже есть понятие обратности. Например, +^-1 = - . Но тут нужны некоторые уточнения, которые пока лучше не трогать. Постарайся пока привыкнуть к понятию унарной операции, попридумывай примеры сам.

В принципе всё выше сказанное мне становится понятным... Я раньше не мог понять во многих задачах как выполняются перестаноки в основном из-за того что их выписывают в лексикографическом порядке.
Но в данной теме есть очень много понятий которые мне не ясны.
К примеру:


В данном случае мне не понятна сама последовательность, и чем в данном случае является k.

Тут производятся операции над операциями, то есть над перестановками. То есть добавляется еще один уровень. Было множество, пример:
a b c d e f g.
Над ним были операции (перестановки), пример:
2 4 3 5 1 7 6.
Теперь есть еще и операция над перстановками. Она выражается числом k, означающим насколько нужно сдвинуть цифры в перестановке направо. Например, при к=2 приведенная выше перестановка превращается в такую:
7 6 2 4 3 5 1 .
Слова о том, что циклический сдвиг снова является перестановкой означают следующее. Из определения перестановки следует, что не всякий набор чисел есть перестанока. Например, набор:
2 2 2 1 1 1 3
- перестановкой не является. В перестаноке все числа должны быть разными. Но ясно, что если они были разными, то они останутся разными и после циклического сдвига как операции над перестановкой при любом k. И, следовательно, результат такого сдвига можно трактовать как перестановку. Вообще говоря, это необходимое условие для действия над объектами, чтобы это действие называлось операцией: оно не должно выводить объект за пределы пространства этих объектов.

А если у нас вообще число k неизвестно? Как быть с этим?

P.S. Может быть Вам скинуть полное условие задачи для лучшего понимания данных перестановок?

Хм. А что значит "как быть"? Смотри, сначала я повторю то, что ты цитировал:
А теперь приведу другое определение:
(я извиняюсь за цитирование самого себя))). Сравни эти два определения. Какая между ними разница? Операции разные, смысл один (ну, в нашем смысле)) - и то и другое определяет операцию. И если множитель неизвестен, то его обычно называют x (читается "икс")) и находят из уравнения, то есть исходя из некоторых дополнительных сведений об этом самом x. Does it make sense? Думаю, если k неизвестно в задаче, то его нужно найти!

Конечно, давай! Если оно не весит гигабайты - то в чем проблема?

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

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

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


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

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

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

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

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

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

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

321 > 132.
43215 > 15432

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

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

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

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

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

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

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

В общем нашёл ещё одну интересную задачку на перестановки, и хотел бы спросить у Вас кое-что.
Для 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=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