Как найти число инверсий в перестановке

Что такое перестановка?

Перестановка
– упорядоченный
набор (=множество)
n
элементов множества E,
то есть
расположение их в определённом порядке.

Если
множество Е состоит из n-элементов, то
число перестановок (то
есть вариантов расположения n элементов)
равно
n!,
где n
— длина
перестановки.

Перестановки
бывают четными и нечетными.

Что такое транспозиция перестановки?

Транспозиция
— перемена местами двух элементов
перестановки.

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

Следствие.
Число четных перестановок из символов
равно числу нечетных, т.е.
(при любом
).

Теор.2
Любая
транспозиция меняет чётность перестановки
на противоположную.

В каком случае два числа образуют инверсию в перестановке?

Инверсию (нарушение
порядка) образует
пара элементов в перестановке когда
меньшее из них расположено правее
большего.

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

Перестановка
называется четной,
если число инверсий
в ней четно, и нечетной –
если инверсий в ней нечётное количество.

ПРИМЕР:
Найти число инверсий в перестановке:
(5,3,1,4,2,6).

Рассмотрим
элементы слева направо по очереди,
считая инверсии для каждого.

1) инверсии
с 1-м элементом (5,3)
(5,1) (5,4) и (5,2) => 4
инверсии

2)
инверсии с 2-м элементом (3,
1) и (3,2) => 2
инверсии

3) инверсии
с 3-м элементом 1
=> 0 инверсий, т.к. 4,2 и 6
больше 1

4)
инверсии с 4-м элементом (4,2)
=> 1 инверсия

5) инверсии
с 5-м элементом 2
=> 0 инверсий, т.к. 6 больше
2.

Итого
в перестановке 4
+ 2 + 0 + 1 + 0 = 7 инверсий.
Перестановка нечетная.

Какая
перестановка называется четной?

Четная
перестановка —
содержащая четное
количество инверсий.

*Число
инверсий в перестановке
подсчитывается так: для каждого из
элементов определяют количество инверсий
(стоящих правее его меньших чисел), и
полученные результаты складывают.

Какая
перестановка называется нечетной?

Нечетная
перестановка —
содержащая нечетное
количество инверсий.

Как
влияет транспозиция на четность
перестановки?

Любая
транспозиция
(то
есть перемена местами двух любых
элементов)
меняет чётность перестановки на
противоположную.

Какая
подстановка называется четной?

Подстановка называется чётной
если при
всех записях
подстановки чётности
верхней и нижней строк (перестановок)
– совпадают.

Например,
тождественная подстановка()
будет чётной:

Какая
подстановка называется нечетной?

Подстановка называется нечётной
если при всех записях подстановки чётности
верхней и нижней строк (т.е. перестановок)
– противоположны.

Сформулируйте
определение определителя матрицы

Определителем
(детерминантом) квадратной матрицы n–го
порядка называют число,
равное алгебраической сумме
всех возможных произведений
элементов этой матрицы, взятых
по одному
из каждой строки и каждого столбца; при
этом знак,
с которым произведение входит в сумму
определяется
по
правилу:

Сомножители
в каждом произведении записываются в
порядке следования строк, тогда номера
столбцов образуют перестановки. Если
перестановка четная, то произведение
берется со знаком «+», а если нечётная
– то со знаком «-».

Произведение
элементов матрицы (слагаемые,
из которых состоит сумма)
называется членом
определителя.

!
Элементы
матрицы при этом могут быть также и
комплексными числами!

НАПРИМЕР,
при n=6 произведение а₂₁а₁₃а₆₂а₃₄а₄₆а₅₅ является
членом определителя, так как в него
входит точно
по одному
элементу из каждой строки и из каждого
столбца.

Подстановка,
составленная из его индексов будет:

В
ней 4 инверсии в верхней строке и 2 в
нижней. Общее число инверсий 6, то есть
подстановка чётная. Значит, этот член
определителя входит в сумму со знаком
«+».

Свойства
определителей:

При
транспонировании матрицы её определитель
не
меняется.
Если
поменять местами две строки или два
столбца определителя, то определитель
изменит знак, а по абсолютной величине
не изменится.
Пусть C
= AB где A и B квадратные
матрицы. Тогда
det C = detA ∙ detB .
Если
все элементы одной строки (столбца)
равны нулю, то и определитель равен
нулю.
Определитель
с двумя одинаковыми строками (столбцами)
равен 0.
Определитель
с двумя пропорциональными строками
или столбцами равен 0.
Определитель
треугольной матрицы равен произведению
диагональных элементов.
Определитель
диагональной матрицы равен произведению
диагональных элементов.
Если
все элементы строки (столбца) умножить
на одно и то же число, то определитель
умножится на это число.
Если
каждый элемент некоторой строки
(столбца) определителя представлен в
виде суммы двух слагаемых, то определитель
равен сумме двух определителей, у
которых все строки (столбцы) кроме
данной, прежние, а в данной строке
(столбце) в первом определителе стоят
первые, а во втором — вторые слагаемые.
Теорема
Якоби: Если к элементам некоторого
столбца определителя прибавить
соответствующие элементы другого
столбца, умноженные на произвольный
множитель λ, то величина определителя
не изменится.

Соседние файлы в папке экз 1 сем

Источник

Определение 1. Количество инверсий (беспорядка) в перестановке – это количество пар элементов (не обязательно соседних), в которых следующий элемент имеет меньший номер, чем предыдущий.

Пример 1.6. Найти количество инверсий в перестановке
(2, 3, 1, 6, 4, 5, 7).

Решение.

Первый способ. Перечислим все пары: (2, 3), (2, 1) , (2, 6), (2, 4), (2, 5),
(2, 7), (3, 1) , (3, 6), (3, 4), (3, 5), (3, 7), (1, 6), (1, 4), (1, 5), (1, 7), (6, 4) ,
(6, 5) , (6, 7), (4, 5), (4, 7) и (5, 7). Инверсии подчёркнуты – всего их 4.

Второй способ представляет собой алгоритм нахождения числа инверсий.

Считаем количество элементов левее 1: их 2. Удаляем единицу: (2, 3, 6, 4, 5, 7). Считаем количество элементов левее 2: их нет (0). Далее удаляем двойку: (3, 6, 4, 5, 7). Считаем количество элементов левее 3: их тоже нет. Продолжаем. После удаления тройки: (6, 4, 5, 7) находим, что левее 4 есть 1 элемент, после удаления 4: (6, 5, 7) левее 5 – 1 элемент; и в (6, 7) левее 6 нет элементов. Суммируем найденные числа – это и есть количество инверсий: 2 + 0 + 0 + 1 + 1 + 0 = 4.

С помощью данного калькулятора можно вычислить онлайн число инверсий любой перестановки.

Источник

Инверсии в комбинаторике – это количество пар элементов, в которых следующий элемент имеет меньший номер, чем предыдущий. Иногда важно иметь количественную оценку степени отличия произвольной перестановки от лексиграфически наименьшей по числу нарушений возрастающего порядка значений ее элементов. Любая пара элементов, где имеет место такое нарушение их взаимного положения в перестановке, называется инверсией.

Количество инверсий в перестановке

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

Для компактной записи инверсий по элементам перестановки применяются вектор инверсий (V₁,…V_j,…V_n) и таблица инверсий (W₁,…W_j,…W_n). Эти обе формы записи идентифицируют числа инверсий для всех элементов перестановки.

Состав вектора и таблицы инверсий для цифровой перестановки P=(5,9,1,8,2,6,4,7,3) показан в следующем примере, где для наглядности индексированы позиции всех элементов:

j	1	2	3	4	5	6	7	8	9
p_j	5	9	1	8	2	6	4	7	3
V_j	0	0	2	1	3	2	4	2	6
W_j	2	3	6	4	0	2	2	1	9

В частности, в этом примере V₈=2, потому что слева от элемента P₈=7 в перестановке есть 2 элемента P₂=9 и P₄=8 с большим значением, чем 7. С другой стороны, W₈=1,потому что слева от элемента со значением 8 (это P₄) в перестановке имеется только 1 элемент (P₂=9), значение которого больше, чем 8. Аналогичным образом можно обосновать выбор величин остальных компонентов вектора и таблицы инверсий в данном примере. Следует также отметить, что для любой перестановки значения компонентов вектора и таблицы инверсий связаны следующими соотношениями:

V₁ = W_n = 0; V_j= W_i | i = P_j; W_j = V_i | P_i = j.

Возвращаясь к интегральным оценкам, следует отметить, что сумма значений всех компонентов вектора или таблицы инверсий определяет общее число инверсий I перестановки. В частности, для рассмотренного примера оно равно 20:

I(5, 9, 1, 8, 2, 6, 4, 7, 3) = 20.

Источник

These are the original MERGE and MERGE-SORT algorithms
from Cormen, Leiserson, Rivest, Stein Introduction to Algorithms:

MERGE(A,p,q,r)
 1  n1 = q - p + 1
 2  n2 = r - q
 3  let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
 4  for i = 1 to n1
 5      L[i] = A[p + i - 1]
 6  for j = 1 to n2
 7      R[j] = A[q + j]
 8  L[n1 + 1] = infinity
 9  R[n2 + 1] = infinity
10  i = 1
11  j = 1
12  for k = p to r
13      if L[i] <= R[j] 
14          A[k] = L[i]
15          i = i + 1
16      else A[k] = R[j]
17          j = j + 1

and

MERGE-SORT(A,p,r)
 1 if p < r
 2     q = floor((p + r)/2)
 3     MERGE-SORT(A,p,q)
 4     MERGE-SORT(A,q + 1,r)
 5     MERGE(A,p,q,r)

at line 8 and 9 in MERGE infinity is the so called sentinel card,
which has such value that all array elements are smaller then it.
To get the number of inversion one can introduce a global counter,
let’s say ninv initialized to zero before calling MERGE-SORT
and than to modify the MERGE algorithm by adding one line
in the else statement after line 16, something like

ninv += n1 - i

than after MERGE-SORT is finished ninv will hold the number of inversions

Источник

Нужно определить число инверсий и указать общий признак для тех чисел n, для которых эта перестановка четна и нечетна.
1, 4, 7, … , 3n-2, 2, 5, 8, … , 3n-1, 3, 6, 9, … , 3n
Объясните пожалуйста алгоритм решения подобного вида задач на этом примере.

Вопрос задан

более трёх лет назад
13030 просмотров

Источник

Что такое перестановка?

Что такое транспозиция перестановки?

В каком случае два числа образуют инверсию в перестановке?

Как найти число инверсий в перестановке

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