Запись перестановки в виде произведения независимых циклов
позволяет легко найти порядок перестановки
.
Теорема
2.
Порядок
перестановки
(порядок циклической подгруппы
)равен
наименьшему
общему кратному
(НОК)
длин независимых циклов, входящих в
разложение .
Доказательство.
Представим
перестановку
в виде произведения независимых циклов
. (7)
Так как
циклы
независимы (они действуют на различных
множествах
),
и если q – порядок циклической подгруппы,
,
,
где
.
Следовательно, q – общее кратное порядков циклов k , которые совпадают с их длинами .
Если q – наименьшее положительное число, для которого
,то
Основная теорема арифметики. Каждое положительное целое число n не равное единице может быть записано в виде произведения простых чисел
. (9)
Эта запись единственна с точностью до порядка следования сомножителей.
Заменив произведения совпадающих простых чисел в (9) их степенями, получим
где
Множество простых чисел
Пример. Два любых целых числа m и n можно записать в виде произведений одних и тех же простых чисел
,
Пример.
Определить
порядок перестановки
вида
Решение. Представим перестановку в виде произведения независимых циклов, т.е.
Длины
независимых циклов
равны
Следовательно, порядок рассматриваемой перестановки равен 28.
Разложение перестановки в произведение транспозиций .
Определение.
Цикл
длиной два называется транспозицией.
Любая транспозиция имеет вид
и оставляет на местах все символы за
исключением
.
Теорема.
Каждая
перестановка
может быть представлена в виде произведения
транспозиции.
Доказательство.
Теорема
будет доказана, если мы сможем представить
в виде произведений транспозиций каждый
из циклов k ,
входящих в разложения перестановки:
.
Рассмотрим
произвольный цикл
,
например
и произведем его разложение в произведение
транспозиций.
Алгоритм
разложения цикла
в произведение транспозиций представлен
на рисунке 2.
Цикл
транспозиции
Рис
2.
– Разложение цикла
в произведение транспозиций.
После завершения всех операций на месте каждого элемента цикла оказался следующий за ним элемент, а первый элемент перешел на последнее место. Таким образом, циклоказался разложенным в произведение транспозиций:
Естественно, это разложение не единственно. Например
Важно
другое – и в первом и во втором его
разложении имеется равное количество
транспозиций – четыре. Если
,
то количество транспозиций равно
.
Раскладывая аналогичным образом каждый
цикл
перестановкив произведение транспозиции, мы получим
разложение всей перестановкив произведение транспозиций.
Замечание.
Количество
транспозиций в цикле
может быть и больше четырех! Возьмем
произвольную транспозицию из разложения
этого цикла, например,
.
Тогда произведение
совпадает с тождественной перестановкой
и цикл
можно представить в виде
Легко заметить, что во всех этих случаях число транспозиций четно и равно 4, 6, 8. Ясно, что способ, «удлиняющий» разложение, не изменяет четности исходного разложения.
Теорема. Пусть – перестановка из , а
. (9)
какое-либо разложение в произведении транспозиций.
Тогда число
(10)
называется
четностью (сигнатурой или знаком)
перестановки
и полностью определяется ,
т.е. не зависит от способа разложения
перестановки
в произведение транспозиций. Кроме
того, если
,
то
. (11)
Определение.
Перестановка
называется четной, если
,
и нечетной, если
.
Из определения четности перестановки вытекает, что все транспозиции – нечетные перестановки.
Действительно,
если
– транспозиция, то
,
тогда
Следствие 1.
Все
четные перестановки степени n образуют
подгруппу
порядка
(она называется знакопеременной группой
степени n).
Следствие 2.
Пусть
перестановка
разложена в произведение независимых
циклов
,
где
,
,
…,
,
…,
– длины независимых циклов.
. (12)
Доказательство. Действительно, по предыдущей теореме имеем
.
Кроме
того,
поскольку каждыйцикл записывается в виде произведения
транспозиций, то
Перестановка – это комбинация элементов из N разных элементов взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все N элементов.
Задача
: Найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:
1:
1 2 3
2:
1 3 2
3:
2 1 3
4:
2 3 1
5:
3 1 2
6:
3 2 1
Перестановки без повторений
Количество перестановок для N различных элементов составляет N! . Действительно:
- на первое место может быть помещен любой из N элементов (всего вариантов N ),
- на вторую позицию может быть помещен любой из оставшихся (N-1) элементов (итого вариантов N·(N-1) ),
- если продолжить данную последовательность для всех N мест, то получим: N·(N-1)·(N-2)· … ·1 , то есть всего N! перестановок.
Рассмотрим задачу получения всех перестановок чисел 1…N (то есть последовательности длины N ), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка 1 2 … N , а последней — N N-1 … 1 .
Рассмотрим алгоритм решения задачи. Дана исходная последовательность чисел. Для получения каждой следующей перестановки необходимо выполнить следующие шаги:
- Необходимо просмотреть текущую перестановку справа налево и при этом следить за тем, чтобы каждый следующий элемент перестановки (элемент с большим номером) был не более чем предыдущий (элемент с меньшим номером). Как только данное соотношение будет нарушено необходимо остановиться и отметить текущее число (позиция 1).
- Снова просмотреть пройденный путь справа налево пока не дойдем до первого числа, которое больше чем отмеченное на предыдущем шаге.
- Поменять местами два полученных элемента.
- Теперь в части массива, которая размещена справа от позиции 1 надо отсортировать все числа в порядке возрастания. Поскольку до этого они все были уже записаны в порядке убывания необходимо эту часть подпоследовательность просто перевернуть.
Таким образом мы получим новую последовательность, которая будет рассматриваться в качестве исходной на следующем шаге.
Реализация на С++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include
using
namespace
std;
{
int
s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int
*a, int
n)
{
int
j = n - 2;
while
(j != -1 && a[j] >= a) j--;
if
(j == -1)
return
false; // больше перестановок нет
int
k = n - 1;
while
(a[j] >= a[k]) k--;
swap(a, j, k);
int
l = j + 1, r = n - 1;
while
(l
return
true;
}
void
Print(int
*a, int
n) // вывод перестановки
{
static
int
num = 1; // номер перестановки
cout.width(3);
cout <<
num++ <<
": "
;
for
(int
i = 0; i < n; i++)
cout <<
a[i] <<
" "
;
cout <<
endl;
}
int
main()
{
int
n, *a;
cout <<
"N = "
;
cin >>
n;
a = new
int
[n];
for
(int
i = 0; i < n; i++)
a[i] = i + 1;
Print(a, n);
while
(NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return
0;
}
Результат выполнения
Перестановки с повторениями
Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n 1 , n 2 ... n k , где элемент n 1 повторяется r 1 раз, n 2 повторяется r 2 раз и т.д. При этом n 1 +n 2 +...+n k =N . Если мы будем считать все n 1 +n 2 +...+n k элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n 1 +n 2 +...+n k)! . Однако среди этих перестановок не все различны. В самом деле, все r 1 элементов n 1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n 2 , n 3 и т. д. В итоге имеем r 1 ! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n 1 . Таким образом, всякая перестановка может быть записана r 1 !·r 2 !·...·r k ! способами. Следовательно, число различных перестановок с повторениями равно
Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив a. Ниже приведен код программы для генерации перестановок с повторениями (изменен только код функции main()
).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include
using
namespace
std;
void
swap(int
*a, int
i, int
j)
{
int
s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int
*a, int
n)
{
int
j = n - 2;
while
(j != -1 && a[j] >= a) j--;
if
(j == -1)
return
false; // больше перестановок нет
int
k = n - 1;
while
(a[j] >= a[k]) k--;
swap(a, j, k);
int
l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
while
(l
return
true;
}
void
Print(int
*a, int
n) // вывод перестановки
{
static
int
num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
cout <<
num++ <<
": "
;
for
(int
i = 0; i < n; i++)
cout <<
a[i] <<
" "
;
cout <<
endl;
}
int
main()
{
int
n, *a;
cout <<
"N = "
;
cin >>
n;
a = new
int
[n];
for
(int
i = 0; i < n; i++)
a[i] = i + 1;
a = 1; // повторяющийся элемент
Print(a, n);
while
(NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return
0;
}
Результат работы приведенного выше алгоритма: