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

[Cheburashka]

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

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

Сообщение отредактировано: Lapp - 17.07.2009 3:00

[amega]

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

[Cheburashka]

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

Перестановкой из 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).

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

[amega]

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

[volvo]

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

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

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

[sheka]

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

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

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

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

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

[Lapp]

М

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

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

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

abc
acb
bac
bca
cba
cab

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

[Cheburashka]

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

[sheka]

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

[Cheburashka]

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

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

"Пусть у нас есть упорядоченное множество из N элементов. Перестановка задает преобразование этого множества. А именно, она говорит, что на i место нужно поставить ai элемент множества, где ai - i-тый элемент перестановки.

Обратной перестановкой к перестановке π называется такая перестановка π^-1, что ππ^-1 = π^-1π = ε, где ε – тождественная перестановка. "

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

[Lapp]

(И пример - 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!

Сообщение отредактировано: Lapp - 17.07.2009 18:07

[Cheburashka]

b c a

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

3 1 2

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

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

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

[Lapp]

Из этого немного не понял...
...
Или я ошибаюсь?

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

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

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.

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


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

Сообщение отредактировано: Lapp - 17.07.2009 18:04

[Cheburashka]

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

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

[Lapp]

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

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

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

[Cheburashka]

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

Циклическим сдвигом на k перестановки p1, p2, ... , pn называется последовательность, p_k+1, p_k+2, ... , p_n, p₁, ... , p_k. Отметим, что любой циклический сдвиг перестановки также является перестановкой. (пример - 3 2 1. Ответ -1 3 2)

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

Сообщение отредактировано: Сергей Меркурьев - 18.07.2009 15:27

[Lapp]

В данном случае мне не понятна сама последовательность, и чем в данном случае является 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. И, следовательно, результат такого сдвига можно трактовать как перестановку. Вообще говоря, это необходимое условие для действия над объектами, чтобы это действие называлось операцией: оно не должно выводить объект за пределы пространства этих объектов.

[Cheburashka]

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

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

[Lapp]

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

Хм. А что значит "как быть"? Смотри, сначала я повторю то, что ты цитировал:

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

А теперь приведу другое определение:

Произведением числа n на число k (обозначается n*k) является сумма n+n+n+...+n+n (повторяется k раз). Отметим, что любое произведение также является числом. (пример - 3*2=6)

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

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

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

[Cheburashka]

Сдвиг перестановки (Сложность: 24%)

Перестановкой порядка 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. Отметим, что любой циклический сдвиг перестановки также является перестановкой.

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

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