-
Обратные перестановки. Алгоритмы
Каждая перестановка
имеет себе обратную. Например, имеем
перестановку
,
для нее обратной будет перестановка
.
Алгоритм I.
(Обратная перестановка на месте). Заменим
перестановку X[1],
X[2]
… X[n],
которая является перестановкой чисел
{1, 2, …, n},
обратной перестановкой.
I1. [Инициализация].
Присвоить m
n, j
-1.
I2. [Следующий
элемент]. Присвоить i
X[m]. Если i
< 0, перейти
к шагу I5 (этот элемент уже был обработан).
I3. [Обратить один
элемент]. (В этот момент j
< 0 и
i
= X[m].
Если m
не является наибольшим элементом своего
цикла, то первоначальная перестановка
давала
X[-j] = m).
Присвоить X[m]
j,
j
—m,
m
i,
i
X[m].
I4. [Конец цикла?].
Если i
> 0, перейти
к шагу I3
(этот цикл не закончен); иначе — присвоить
i
j.
(В последнем случае первоначальная
перестановка давала X[-j] = m,
где m
— наибольший элемент в его цикле.)
I5. [Сохранить
окончательное значение]. Присвоить X[m]
—i.
(Первоначально X[-i]
было равно m).
I6. [Цикл по m].
Уменьшить m
на 1. Если m
> 0, перейти
к I2,
в противном случае работа алгоритма
заканчивается.
Пример.
Найти обратную перестановку для строки:
6 2 1 5 4 3.
Решение.
В качестве второй строки запишем
порядковые номера цифр строки, получим:
Переставим строки
местами, получим:
.
Переставим столбцы местами, сохраняя
порядок элементов заданной строки,
получим
.
Таким образом, перестановка (3 2 6 4 5 1)
является результатом обращения исходной
строки 6 2 1 5 4 3.
Алгоритм J.
(Обращение
на месте). Этот алгоритм дает такой же
результат, как и алгоритм I, но на основании
другого подхода.
J1. [Сделать все
величины отрицательными]. Присвоить
X[k]
-X[k] для 1
k
n. Присвоить
также m
n.
J2.
[Инициализация j].
Присвоить j
m.
J3.
[Нахождение отрицательного элемента].
Присвоить i
X[j].
Если i
> 0, то
присвоить j
i
и повторить этот шаг.
J4.
[Обращение]. Присвоить X[j]
X[-i],
X[-i]
m.
J5.
[Цикл по m].
Уменьшить m
на 1, если m
> 0, вернуться
к шагу J2.
В противном случае работа алгоритма
заканчивается.
Хотя алгоритм J
невероятно изящен, анализ показал, что
алгоритм I
намного его превосходит. На самом деле
оказывается, что среднее время выполнения
алгоритма J,
в сущности, пропорционально n
ln(n),
а среднее время выполнения алгоритма
I
пропорционально n.
Запись перестановки
в циклическом виде не единственна;
состоящую из шести элементов перестановку
(1 6 3) (4 5) (2) можно записать как (4 5) (3 1 6)
(2) и другими способами, что вносит
некоторую неопределенность. Поэтому
важно рассмотреть каноническую
форму
циклического представления, которая
является единственной.
Для получения
канонической формы перестановки выполним
следующие действия:
-
Вписать
в перестановку пропущенные единичные
циклы. -
Внутри
каждого цикла поместить на первое место
наименьшее число. -
Расположить
циклы в порядке убывания их первых
элементов.
Пример.
Для циклической
перестановки (3 1 6) (5 4) найти каноническое
представление.
Решение.
(3 1 6) (5 4) (2)
(1 6 3) (4 5) (2)
(4 5) (2) (1 6 3).
Важным свойством
канонической формы является то, что
скобки можно опустить, а затем восстановить
единственным образом.
Последовательность
действий следующая:
1. Выбираем
направление просмотра строки слева
направо.
2. Расставляем “(“
в начале строки и “)” в конце строки.
3. Ищем минимальное
число и, если перед ним еще не стоит “(“
ставим “(“
4. Перед “(“ ставим
“)”.
5. Переходим к
анализу нерассмотренных еще элементов
строки.
6. Если еще не все
элементы рассмотрены, переход к п. 3.
7. Конец алгоритма.
Пример. Написать
каноническую форму для перестановки
(6 4 3) (5 1 2)
Решение.
1.
(6 4 3) (5 1 2)
2. (3 6 4) (1 2 5)
3. 3 6 4 1 2 5.
Обратный процесс
введения скобок циклов будет следующим
(3 6 4) (1 2 5).
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
В чем разница между перестановкой и обратной перестановкой
Из любой таблицы инверсий d1,d2,…dn можно однозначно восстановить перестановку, которая порождает данную таблицу, путем последовательного определения относительного расположения элементов n, n-1,….,1 (в этом порядке). Например перестановку, соответствующую таблице инверсий (2,3,6,4,0,2,2,1,0) = (d1,d2,d3,d4,d5,d6,d7,d8,d9), можно построить следующим образом: выпишем число 9, так как d8=1, то 8 стоит правее 9. Поскольку d7=2, то 7 стоит правее 8 и 9. Так как d6=2, то 6 стоит правее двух уже выписанных чисел, таким образом получается расположение чисел 9,8,6,7. Припишем теперь 5 слева, потому что d5=0, помещаем 4 вслед за четырьмя уже выписных числами, 3 после 6 выписанных чисел (т.е. в правый конец) и получаем 5,9,8,6,4,7,3. Вставив аналогичным образом 2 и 1, придем к перестановке (5,9,1,8,2,6,4,7,3).
Обратные перестановки
Не следует путать «инверсии» перестановок с обратными перестановками. Пусть a1,a2,….an — различные шары, индексы которых свяжем с номерами шаров. Тогда исходное расположение шаров однозначно определяется тождественной перестановкой (e=1,2,…n)
Обратной к перестановке называется перестановка которая получается, если в исходной перестановке поменять местами строки, а затем упорядочить столбцы в возрастающем порядке по верхним элементам, т.е. Ясно, что последовательное изменение порядка шаров согласно перестановкам и обратной приводит к исходному их расположению, т.е. к тождественной перестановке.
Содержание
- 1 Умножение перестановок
- 1.1 Пример
- 2 Обратная перестановка
- 2.1 Получение обратной перестановки
- 3 Группа перестановок
- 4 Группа чётных перестановок
- 5 Группа подстановок
- 6 См. также
- 7 Источники информации
Умножение перестановок
| Определение: |
| Умножением (англ. multiplication) или композицией (англ. composition) перестановок, представленных в виде целочисленных функций , где позиция элемента, а — его номер, называется перестановка, получаемая по следующему правилу: |
| Утверждение: |
|
Умножение перестановок ассоциативно: |
|
Доказывается простым раскрытием скобок. |
Перед прочтением примера перемножения перестановок рекомендуем познакомиться с циклами в данной статье: Действие перестановки на набор из элементов, представление в виде циклов
Пример
или
Обратная перестановка
| Определение: |
| Обратной перестановкой (англ. inverse permutation) к перестановке называется такая перестановка, что: |
| Утверждение: |
|
Для каждой перестановки существует перестановка, обратная ей. |
| Пусть дана перестановка , построим обратную ей перестановку : если , то . Очевидно, что данная перестановка является обратной к . |
Также обратная перестановка единственна. Это следует из того, что для каждой -ой позиций в исходной перестановке однозначно определяется -ая позиций в обратной перестановке, значение которой есть
| Определение: |
| Перестановка, равная своей обратной, называется инволюцией (англ. involution): , то есть её представление в виде циклов не содержит цикла, размер которого больше двух. |
| Утверждение: |
|
Количество инволюционных перестановок длины может быть получено по формуле: , где |
| Докажем формулу по индукции. Базой являются . Предположим, что для всех , где , , формула верна. Рассмотрим перестановку длины и попробуем найти количество инволюций этой длины. Существует инволюций, при (у которых последний элемент представляет собой цикл длины ), а число инволюций длины , содержащих в своём представлении в виде циклов цикл , где , (так как при фиксированных и имеем перестановок оставшихся элементов, которые не нарушают свойств инволюции). Таким образом, |
| Определение: |
| Перестановка, содержащая чётное количество инверсий, называется чётной (англ. even permutation), в противном случае нечётной (англ. odd permutation). |
| Определение: |
| Перестановка, меняющая местами только два элемента, называется транспозицией (англ. transposition). |
| Лемма: |
|
Если в перестановке, длина которой больше , поменять местами элемента, то её четность изменится. |
| Доказательство: |
| Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами и находятся элементов, то есть перестановка имеет вид: , . Сначала поменяем последовательно с числами , а затем число с рядом стоящими . В итоге мы выполним транспозиций рядом стоящих элементов, то есть чётность перестановки изменится. |
Получение обратной перестановки
Пусть в массиве содержится перестановка, длины , тогда после выполнения алгоритма в массиве будет содержаться перестановка, обратная ей.
fun reversePerm(p : int[], rep : int[])
for i = 1 to n
rep[p[i]] = i;
Группа перестановок
| Определение: |
Группой (англ. group) называется множество с заданной на нём бинарной операцией , удовлетворяющей следующим свойствам:
|
| Утверждение: |
|
Множество перестановок с элементами с операцией умножения является группой (часто группу перестановок называют симметрической (англ. symmetric group), и обозначают ). |
| Свойства и (ассоциативность умножения и существование обратной перестановки для любой из перестановок) доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (). |
Мощность симметрической группы:
Теорема Кэли утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.
Группа чётных перестановок
| Определение: |
| Группа чётных перестановок (англ. alternating group) является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится. |
| Утверждение: |
|
Количество чётных перестановок длины равно количеству нечётных и равно |
| Пусть число число чётных перестановок , а нечётных . Сделаем транспозицию для всех чётных перестановок. Получим нечётных различных перестановок, то есть . Проделаем то же самое с нечётными перестановками. Получим, что , то есть и . |
Группа подстановок
| Определение: |
| Подстановкой (англ. substitution) называется всякое взаимно однозначное отображение множества первых натуральных чисел на себя. |
Всякая подстановка может быть записана при помощи двух перестановок, подписанных одна под другой:
Где через обозначается то число, в которое при подстановке переходит число .
| Определение: |
| Группой подстановок (англ. group of substitutions) называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве. |
См. также
- Теорема Кэли
- Действие перестановки на набор из элементов, представление в виде циклов
Источники информации
- Wikipedia — Involution
Given an array of size n of integers in range from 1 to n, we need to find the inverse permutation of that array.
An inverse permutation is a permutation which you will get by inserting position of an element at the position specified by the element value in the array. For better understanding, consider the following example:
Suppose we found element 4 at position 3 in an array, then in reverse permutation, we insert 3 (position of element 4 in the array) in position 4 (element value).
Basically, An inverse permutation is a permutation in which each number and the number of the place which it occupies is exchanged.
The array should contain element from 1 to array_size.
Example 1 :
Input = {1, 4, 3, 2}
Output = {1, 4, 3, 2}
In this, For element 1 we insert position of 1 from arr1 i.e 1 at position 1 in arr2. For element 4 in arr1, we insert 2 from arr1 at position 4 in arr2. Similarly, for element 2 in arr1, we insert position of 2 i.e 4 in arr2.
Example 2 :
Input = {2, 3, 4, 5, 1}
Output = {5, 1, 2, 3, 4}
In this example, for element 2 we insert position of 2 from arr1 in arr2 at position 2. similarly, we find the inverse permutation of other elements.
Consider an array arr having elements 1 to n.
Method 1: In this method, we take element one by one and check elements in increasing order and print the position of the element where we find that element.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
void inversePermutation(int arr[], int size) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (arr[j] == i + 1) {
cout << j + 1 << " ";
break;
}
}
}
}
int main() {
int arr[] = {2, 3, 4, 5, 1};
int size = sizeof(arr) / sizeof(arr[0]);
inversePermutation(arr, size);
return 0;
}
Java
import java.io.*;
class GFG {
static void inversePermutation(int arr[], int size)
{
int i ,j;
for ( i = 0; i < size; i++)
{
for ( j = 0; j < size; j++)
{
if (arr[j] == i + 1)
{
System.out.print( j + 1 + " ");
break;
}
}
}
}
public static void main (String[] args)
{
int arr[] = {2, 3, 4, 5, 1};
int size = arr.length;
inversePermutation(arr, size);
}
}
Python3
def inversePermutation(arr, size):
for i in range(0, size):
for j in range(0, size):
if (arr[j] == i + 1):
print(j + 1, end = " ")
break
arr = [2, 3, 4, 5, 1]
size = len(arr)
inversePermutation(arr, size)
C#
using System;
class GFG {
static void inversePermutation(int []arr, int size)
{
int i ,j;
for ( i = 0; i < size; i++)
{
for ( j = 0; j < size; j++)
{
if (arr[j] == i + 1)
{
Console.Write( j + 1 + " ");
break;
}
}
}
}
public static void Main ()
{
int []arr = {2, 3, 4, 5, 1};
int size = arr.Length;
inversePermutation(arr, size);
}
}
PHP
<?php
function inversePermutation($arr, $size)
{
for ( $i = 0; $i < $size; $i++)
{
for ($j = 0; $j < $size; $j++)
{
if ($arr[$j] == $i + 1)
{
echo $j + 1 , " ";
break;
}
}
}
}
$arr = array(2, 3, 4, 5, 1);
$size = sizeof($arr);
inversePermutation($arr, $size);
?>
Javascript
<script>
function inversePermutation(arr, size)
{
let i ,j;
for ( i = 0; i < size; i++)
{
for ( j = 0; j < size; j++)
{
if (arr[j] == i + 1)
{
document.write( j + 1 + " ");
break;
}
}
}
}
let arr = [2, 3, 4, 5, 1];
let size = arr.length;
inversePermutation(arr, size);
</script>
Time Complexity: O(n*n)
Auxiliary Space: O(1)
Method 2: The idea is to use another array to store index and element mappings
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
void inversePermutation(int arr[], int size) {
int arr2[size];
for (int i = 0; i < size; i++)
arr2[arr[i] - 1] = i + 1;
for (int i = 0; i < size; i++)
cout << arr2[i] << " ";
}
int main() {
int arr[] = {2, 3, 4, 5, 1};
int size = sizeof(arr) / sizeof(arr[0]);
inversePermutation(arr, size);
return 0;
}
Java
import java.io.*;
class GFG {
static void inversePermutation(int arr[], int size) {
int arr2[] = new int[size];
for (int i = 0; i < size; i++)
arr2[arr[i] - 1] = i + 1;
for (int i = 0; i < size; i++)
System.out.print(arr2[i] + " ");
}
public static void main(String args[]) {
int arr[] = {2, 3, 4, 5, 1};
int size = arr.length;
inversePermutation(arr, size);
}
}
Python3
def inversePermutation(arr, size) :
arr2 = [0] *(size)
for i in range(0, size) :
arr2[arr[i] - 1] = i + 1
for i in range(0, size) :
print( arr2[i], end = " ")
arr = [2, 3, 4, 5, 1]
size = len(arr)
inversePermutation(arr, size)
C#
using System;
class GFG {
static void inversePermutation(int []arr, int size) {
int []arr2 = new int[size];
for (int i = 0; i < size; i++)
arr2[arr[i] - 1] = i + 1;
for (int i = 0; i < size; i++)
Console.Write(arr2[i] + " ");
}
public static void Main() {
int []arr = {2, 3, 4, 5, 1};
int size = arr.Length;
inversePermutation(arr, size);
}
}
Javascript
function inversePermutation(arr, size) {
let arr2 = [];
for (let i = 0; i < size; i++)
arr2[arr[i] - 1] = i + 1;
for (let i = 0; i < size; i++)
console.log(arr2[i] + " ");
}
let arr = [2, 3, 4, 5, 1];
let size = arr.length;
inversePermutation(arr, size);
Time Complexity: O(n)
Auxiliary Space: O(n)
Last Updated :
02 Mar, 2023
Like Article
Save Article
Определение обратной перестановки. Перестановка ψ из Sn называется обратной к перестановке φ из Sn , если φψ = ψφ = e.
Перестановку, обратную к φ , обозначают через φ−1
Пример. Найти обратную перестановку
Для того, чтобы найти обратную перестановку φ−1 , вставляем в калькулятор вторую строку … Смотреть решение »
Композиция перестановок
Композиция перестановок определяется как обычная композиция отображений: (φ◦ ψ)(j) = φ(ψ(j)) (j ∈ Xn ).
Композиция перестановок является перестановкой (композиция биективных отображений биективна).
Композицию перестановок часто называют произведением перестановок и вместо φ ◦ ψ пишут просто φψ
Алгоритм — как найти композицию перестановок: … Смотреть решение »
Как найти число инверсий в перестановке
Определение 1. Количество инверсий (беспорядка) в перестановке – это количество пар элементов (не обязательно соседних), в которых следующий элемент имеет меньший номер, чем предыдущий.
Пример 1.6. Найти количество инверсий в перестановке
(2, 3, 1, 6, 4, 5, 7).
Решение. … Смотреть решение »