Перейти к содержимому

Как возводить перестановку в степень

  • автор:

Действие перестановки на набор из элементов, представление в виде циклов

Обозначим за [math]A[/math] множество (не пронумерованных) объектов [math]\[/math] . Поскольку перестановку можно рассматривать как отображение [math]\pi \colon \ \to \[/math] , а нумерацию как отображение [math]\alpha \colon \ \to A[/math] , то действие перестановки можно определить как композицию отображений [math]\alpha \circ \pi[/math] .

Например, рассмотрим множество [math]A = (a, b, c, d)[/math] и перестановку [math]\pi = \langle 3, 4, 1, 2 \rangle[/math] . Тогда результат действия [math]\pi[/math] на [math]A[/math] — упорядоченное множество [math]\pi(A) = (c, d, a, b)[/math] . Если рассмотреть граф перестановки (описано ниже), то действие перестановки можно представить таким образом: каждый элемент устанавливается в вершину графа, соответствующую номеру этого элемента, после чего каждый элемент передвигается по исходящему из этой вершины ребру.

Иллюстрация действия перестановки

Также, композицию перестановок можно выразить как действие одной перестановки на другую. Стоит отметить, что действие перестановки [math]\pi^n[/math] соответствует переходу по графу [math]n[/math] раз.

Действие обратной перестановки над множеством [math]A[/math] соответствует переходу элементов по развёрнутым рёбрам и даёт упорядоченное множество [math]b[/math] , для которого верно [math]\pi(b) = i(A)[/math] .

Если [math]a = i(A), b = \pi^<-1>(A)[/math] , то [math]\pi(b) = a[/math] ;

Циклы

Определение:
Циклом длины [math]~l[/math] называется такая перестановка [math]\pi,[/math] которая тождественна на всём множестве [math]X,[/math] кроме подмножества [math]\\subset X[/math] и [math]\pi(x_l)=x_1[/math] , [math]\pi(x_i)=x_[/math] . Обозначается [math](x_1,x_2,\dots,x_l)[/math] .

Изображение перестановки в виде графа

Перестановку можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: [math](1, 5, 2)(3, 6)(4)=\langle 5,1,6,4,2,3\rangle [/math] .

Цикл может быть записан по разному, например, в приведенном выше примере цикл [math](1, 5, 2)[/math] может быть записан как [math](5, 2, 1)[/math] , [math](2, 1, 5)[/math] , но не может быть записан как [math](2, 5, 1)[/math] .

Перестановку можно представить в виде графа. Граф содержит ребро от вершины [math]x_i[/math] к вершине [math]x_j[/math] если [math]\pi(x_i) = x_j[/math] . Тогда циклы перестановки соответствуют циклическим путям в графе.

С циклами связаны некоторые интересные свойства перестановок.

Определение:
Степенью перестановки называется минимальное число [math]n \in N[/math] такое, что [math]\pi^n = i[/math]

Степень перестановки равна наименьшему общему кратному длин всех циклов
Если длины всех циклов не превышают [math]2[/math] , то перестановка является инволюцией.

Поиск всех циклов в перестановке

Задача:
Дана перестановка [math]\pi[/math] из [math]n[/math] элементов, требуется найти все циклы в ней.

Рассмотрим элемент перестановки [math]\pi_i[/math] . Добавим его к циклу, отметим позицию [math]i[/math] посещенной и перейдем к [math]\pi_<\pi_i>[/math] . Если мы перешли в позицию [math]i[/math] , которую уже посещали, значит мы нашли очередной цикл перестановки. Перейдем к первой непосещенной позиции и продолжим поиск.

Рассмотрим в качестве примера поиск циклов в перестановке [math]\langle2, 4, 5, 1, 3\rangle[/math] :

  1. В позиции [math]1[/math] находится число [math]2[/math] . Добавим его к новому циклу и перейдем в позицию [math]2[/math] . Аналогично добавим к циклу числа [math]4[/math] и [math]1[/math] . Перейдем в позицию [math]1[/math] , которую мы уже посещали — нашли первый цикл [math](2, 4, 1)[/math] .
  2. Аналогично найдем второй цикл [math](5, 3)[/math] .
  3. Таким образом, [math](2, 4, 1)(5, 3)=\langle2, 4, 5, 1, 3\rangle[/math]

Псевдокод алгоритма

function findCycles(int p[]): vector used(n) // массив, где отмечены посещенные позиции for i = 1 to n if not used[i] j = i vector cycle while not used[j] cycle.push_back(p[j]) used[j] = true j = p[j] print cycle // выведем на экран очередной цикл перестановки

См. также

Источники

  • Википедия — Перестановка
  • Wikipedia — Permutation
  • Дискретная математика и алгоритмы
  • Комбинаторика

Научный форум dxdy

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».

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

Не ищите на этом форуме халяву , правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.

Возвести подстановку в степень.

На страницу 1 , 2 След.

Возвести подстановку в степень.
04.05.2013, 21:55

Последний раз редактировалось qwertz 04.05.2013, 21:57, всего редактировалось 3 раз(а).

$<\begin</p> <p>1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 2 & 1 & 3 \end>$^» /></p> <p>Как это сделать?</p> <p><b>Re: Возвести подстановку в степень.</b><br /> 04.05.2013, 21:57</p> <table cellspacing= Заслуженный участник

В виде произведения независимых циклов представьте. Или просто начните перемножать, заметите закономерность.

Re: Возвести подстановку в степень.
04.05.2013, 22:07

$(1 4)(2 5 3) = (1 4)^</p> <p>(2 5 3)^$» /> а дальше?</p> <p><b>Re: Возвести подстановку в степень.</b><br /> 04.05.2013, 22:22<br /> qwertz <br />1 это 4, 4 это 1, 1 это 4, 4 это 1..<br /> <b>Re: Возвести подстановку в степень.</b><br /> 04.05.2013, 22:40</p> <p>Даже я уже понял, хотя до сего момента ничего не слышал о подстановках и перестановках http://www.intuit.ru/studies/courses/10 . 728?page=3</p> <p><b>Re: Возвести подстановку в степень.</b><br /> 04.05.2013, 22:54<br /> <b>Re: Возвести подстановку в степень.</b><br /> 05.05.2013, 00:21</p> <table cellspacing= Заслуженный участник

Последний раз редактировалось arseniiv 05.05.2013, 00:23, всего редактировалось 1 раз.

qwertz в сообщении #719645 писал(а):

$(1 4)(2 5 3) = (1 4)^</p> <p>(2 5 3)^$» /></p> <p><img decoding= Заслуженный участник

qwertz в сообщении #719645 писал(а):

$(1 4)(2 5 3) = (1 4)^</p> <p>(2 5 3)^$» /> а дальше?</p> <p>Почему равно? Вы имели в виду, что левую часть надо тоже в сотую степень возвести?</p> <p><img decoding=

Сегодняшнее пасхальное настроение привело меня к такому совету: будьте как дети! То есть попробуйте решить задачу без теории, экспериментально. Ну вот, цикл что означает? Что будет, если применить его 2 раза? Три раза? Во что перейдут 1 и 4?

Re: Возвести подстановку в степень.
05.05.2013, 10:05

Последний раз редактировалось qwertz 05.05.2013, 10:09, всего редактировалось 2 раз(а).

Цикл $(1 4)$означает, что элемент '$отображается в $4$. Пробовал возводить цикл $(1 4)$во вторую степень (применить два раза), получилось, что '$перейдет в '$, а $4$в $4$, т.е тождественная подстановка. Если в третью (применить три раза), то $(1 4)^3 = (1 4)$, т.е получился сам же цикл. Стало быть, если цикл длины $n$возвести в степень $n$, то получится тождественная подстановка.
$((1 4) (2 5 3))^= (1 4)^ (2 5 3)^ = ((1 4)^2)^ ((2 5 3)^3)^ (2 5 3) = (1)(4)(2)(5)(3) \cod (2 5 3)$
Получилось, что тождественная подстановка $(1)(4)(2)(5)(3)$умножается на цикл $(2 5 3)$, т.е:
$\begin1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end \begin 2 & 5 & 3 \\ 5 & 3 & 2 \end$
Никогда не умножал подстановки разных размеров, но полагаю, что получится:
$\begin1 & 2 & 3 & 4 & 5 \\ 1 & 5 & 2 & 4 & 3 \end$

Как быстро возвести перестановку в k степень?

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

Лучший ответ

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

Дмитрий ЧугуновУченик (101) 13 лет назад

да, есть такой термин. степенью перестановки называется перестановка, умноженная на себя k раз. надеюсь, объяснять, что такое умножение перестановок, не надо

sm Просветленный (32518) И кто такая «перестановка» ? Если уж ты тут начал сыпать терминами, то приведи вразумительное пояснение к термину «перестановка» ..

Остальные ответы

Надо понимать, время бывает еще и нелинейное — квадратичное, параболическое, сферическое ..
))

Дмитрий ЧугуновУченик (101) 13 лет назад

а то я не знаю! вот я и прошу помочь придумать алгоритм за линейное время, ибо за квадрат, да даже за NlogN написать и я могу

sm Просветленный (32518) Чудик, это не время линейное — это ЗАВИСИМОСТЬ линейная))

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

Число k представляем в двоичном виде. Допустим, k = 11(десятич. ) = 1011(двоич. ) — нам важны единичные биты — это 3-й, 2-й и 0-й.
Исходное число a (основание степени) последовательно возводим в квадрат.
a[0] = a
a[1] = a[0]*a[0] (будет a^2)
a[2] = a[1]*a[1] (получается a^4)
a[3] = a[2]*a[2] (получается a^8)

Теперь те, что соответствуют единичным битам, перемножаем и получаем a[3]*a[2]*a[0] = a^11. Получаем 5 умножений вместо 10.

Дмитрий ЧугуновУченик (101) 13 лет назад

>За логарифмическое время хотите? Легко.
все это прекрасно, но как видите в комментарии к предыдущему ответу я написал что могу за логрифм. Мне надо не число, а перестановку. причем не за NlogN, а за N

Булат 1 Оракул (54387) Из вашего пояснения я понял, что возвести нужно либо число (это сделано), либо множество чисел. А под возведением множества в степень я могу подразумевать только декартову степень — множество упорядоченных пар, троек, k-ок.

Что обратно возведению в степень?

Во-первых, сначала надо разобраться, что значит обратное действие. Так деление есть обратное действие умножению, а вычитание — сложению. Это вытекает из рассуждений, что произведение, получившееся от перемножения двух множителей, позволяет найти один из множителей, если известен другой. Например, 5 * 3 = 15. Если нам неизвестен второй множитель (5 * ? = 15), то его можно найти, выполнив деление: 15 : 5 = 3. Операция не меняется, если неизвестен первый множитель: ? * 3 = 15, 15 : 3 = 5. Это связано с тем, что умножение подчиняется переместительному закону (от перемены мест множителей произведение не меняется).

Аналогично и для вычитания: ? + 10 = 33, 33 — 10 = 23 или ? + 23 = 33, 33 — 23 = 10. Неважно, какое слагаемое неизвесто, его всегда находят вычитанием.

Но не все так просто с возведением в степень. Здесь от перестановки основания степени и показателя степени результат изменяется, т.е. возведение в степень не подчиняется переместительному закону: 4 3 = 64, но 3 4 = 81. (Хотя есть исключения: 2 4 = 16 и 4 2 = 16.)

Поэтому, если нам известен результат операции возведения в степень и показатель степени, то, чтобы найти основание степени, надо извлечь корень известной по показателю степени из результа возведения в степень:

? 3 = 125, следовательно 3 √125 = 5.

Если же известны основание степени и результат возведения в степень, а надо найти показатель степени, то используется такая операция как нахождение логарифма:

2 ? = 64, отсюда log264 = 6

Похожие публикации:
  1. Dm contract fines что это
  2. Как убрать первую цифру в ячейке excel
  3. Какая функция растет быстрее степенная или показательная
  4. Скачать панель задач как на мак ос

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *