Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Циклическая перестановка

Из Википедии — свободной энциклопедии

В теории групп циклическая перестановка — это перестановка элементов некоторого множества X, которая переставляет элементы некоторого подмножества S множества X циклическим образом, сохраняя на месте остальные элементы X (т.е. отображая их в себя). Например, перестановка (1, 3, 2, 4), переводящая 1 в 3, 3 в 2, 2 в 4 и 4 в 1 является циклической, в то время как перестановка (1, 3)( 2, 4), переводящая 1 в 3, 3 в 1, 2 в 4 и 4 в 2 циклической не является.

Цикл в перестановке — это подмножество элементов, которые переставляются циклическим образом. Множество S называется орбитой цикла. Каждую перестановку конечного множества элементов можно разложить в объединение циклов с непересекающимися орбитами. В некоторых контекстах циклическая перестановка сама по себе называется циклом.

Определение

перестановки
перестановки

Перестановка называется циклической тогда и только тогда, когда она состоит из единственного нетривиального цикла (т.е. цикла длиной больше 1)[1].

Пример:

Некоторые авторы ограничивают определение только теми перестановками, которые имеют в точности один цикл (то есть, не разрешаются перестановки, имеющие фиксированные точки[2].

перестановки
перестановки

Пример:

Более формально, перестановка множества X, которая является биективной функцией , называется циклической, если действие на X подгруппы с генератором имеет максимум одну орбиту из более чем одного элемента[3]. Это понятие чаще всего используется, когда X является конечным множеством. Тогда, конечно, наибольшая орбита S также конечна. Пусть  — любой элемент S, положим для любого . Если множество S конечно, имеется минимальное число , для которого . Тогда и является перестановкой, определённой формулой

для

и для любого элемента . Элементы, не фиксируемые отображением , можно представить как

.

Цикл можно записать с использованием компактной циклической записи (запятая между элементами в такой записи не ставится, чтобы избежать путаницы с кортежами). Длина цикла — это число элементов его наибольшей орбиты. В циклической записи циклы длины 1 часто опускаются, если это не вызывает путаницы[4].

Основные свойства

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

Число различных циклов длины k в симметрической группе Sn задаётся для следующей формулой

Цикл длины k имеет чётность (−1)k − 1.

Транспозиции

Массив транспозиций

Цикл, состоящий из двух элементов, называется транспозицией. Например, перестановка {1, 4, 3, 2}, переводящая 1 в 1, 2 в 4, 3 в 3 и 4 в 2 является транспозицией (а именно, транспозицией, переставляющей 2 и 4).

Любую перестановку можно представить как композицию (произведение) транспозиций — формально, они являются генераторами группы[5]. Более того, любую перестановку упорядоченного множества X = {1, 2, …, n} можно выразить как произведение смежных транспозиций, то есть транспозиций вида Действительно, любую транспозицию можно представить в виде произведения смежных транспозиций.

Разложение перестановки в произведение транспозиций можно получить, например, путём выписывания перестановки как произведения различных циклов, а затем итеративного разложения циклов длины 3 и более в произведение транспозиции и цикла на единицу короче:

Симметрическая группа является группой Коксетера, в том смысле, что она порождается элементами порядка 2 (смежными транспозициями) и все соотношения имеют определённый вид.

Один из главных результатов элементарной теории симметрических групп утверждает, что либо все разложения данной перестановки на транспозиции имеют чётное число транспозиций, либо все разложения имеют нечётное число транспозиций[6]. Это позволяет чётности перестановки быть хорошо определённой функцией.

См. также

  • Циклическая сортировка[en] — алгоритм сортировки, основанный на идее, что массив можно разложить на циклы, которые можно индивидуально прокрутить, чтобы получить сортированный массив
  • Циклы и фиксированные точки[en]
  • Циклические перестановки целых чисел[en]
  • Циклические перестановки в протеинах[en]

Примечание

  1. Bogart, 1990, с. 486.
  2. Gross, 2008, с. 29.
  3. Fraleigh, 1993, с. 103.
  4. Sagan, 1991, с. 2.
  5. Rotman, 2006, с. 118, Prop. 2.35.
  6. Rotman, 2006, с. 122.

Литература

Ссылки

Эта страница в последний раз была отредактирована 8 декабря 2023 в 15:44.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).