Поиск следующей перестановки. Формулы комбинаторики

Перестановка – это комбинация элементов из 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 swap(a, l++, r--);
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 swap(a, l++, r--);
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;
}

Результат работы приведенного выше алгоритма:

Запись перестановки  в виде произведения независимых циклов

позволяет легко найти порядок перестановки

Теорема 2. Порядок
перестановки
(порядок циклической подгруппы
)равен наименьшему общему кратному (НОК) длин независимых циклов, входящих в разложение .

Доказательство. Представим перестановку
в виде произведения независимых циклов

. (7)

Так как циклы
независимы (они действуют на различных множествах
), и если q – порядок циклической подгруппы,

где
.

Следовательно, q – общее кратное порядков циклов  k , которые совпадают с их длинами .

Если q – наименьшее положительное число, для которого

,то

Основная теорема арифметики. Каждое положительное целое число n не равное единице может быть записано в виде произведения простых чисел

. (9)

Эта запись единственна с точностью до порядка следования сомножителей.

Заменив произведения совпадающих простых чисел в (9) их степенями, получим

где

Множество простых чисел

Пример. Два любых целых числа m и n можно записать в виде произведений одних и тех же простых чисел

Пример. Определить порядок перестановки
вида

Решение. Представим перестановку  в виде произведения независимых циклов, т.е.

Длины независимых циклов
равны

Следовательно, порядок рассматриваемой перестановки равен 28.

Разложение перестановки в произведение транспозиций .

Определение. Цикл длиной два называется транспозицией. Любая транспозиция имеет вид
и оставляет на местах все символы за исключением
.

Теорема. Каждая перестановка
может быть представлена в виде произведения транспозиции.

Доказательство. Теорема будет доказана, если мы сможем представить в виде произведений транспозиций каждый из циклов  k , входящих в разложения перестановки:
.

Рассмотрим произвольный цикл , например
и произведем его разложение в произведение транспозиций.

Алгоритм разложения цикла
в произведение транспозиций представлен на рисунке 2.

Цикл
транспозиции

Рис 2. – Разложение цикла
в произведение транспозиций.

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

Естественно, это разложение не единственно. Например

Важно другое – и в первом и во втором его разложении имеется равное количество транспозиций – четыре. Если
, то количество транспозиций равно
. Раскладывая аналогичным образом каждый цикл
перестановкив произведение транспозиции, мы получим разложение всей перестановкив произведение транспозиций.

Замечание. Количество транспозиций в цикле
может быть и больше четырех! Возьмем произвольную транспозицию из разложения этого цикла, например,
. Тогда произведение
совпадает с тождественной перестановкой и цикл
можно представить в виде

Легко заметить, что во всех этих случаях число транспозиций четно и равно 4, 6, 8. Ясно, что способ, «удлиняющий» разложение, не изменяет четности исходного разложения.

Теорема. Пусть  – перестановка из , а

. (9)

какое-либо разложение  в произведении транспозиций.

Тогда число

(10)

называется четностью (сигнатурой или знаком) перестановки  и полностью определяется , т.е. не зависит от способа разложения перестановки  в произведение транспозиций. Кроме того, если
, то