Перестановка – это комбинация элементов из {\displaystyle{N}} разных элементов взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все {\displaystyle{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
Перестановки без повторений
Количество перестановок для {\displaystyle{N}} различных элементов составляет {\displaystyle{N!}}.
Действительно:
- на первое место может быть помещен любой из {\displaystyle{N}} элементов (всего вариантов {\displaystyle{N}}),
- на вторую позицию может быть помещен любой из оставшихся {\displaystyle{(N-1)}} элементов (итого вариантов {\displaystyle{N \cdot (N-1)}}),
- если продолжить данную последовательность для всех {\displaystyle{N}} мест, то получим: {\displaystyle{N \cdot (N-1) \cdot (N-2) \cdot … \cdot 1}}, то есть всего {\displaystyle{N!}}перестановок.
Рассмотрим задачу получения всех перестановок чисел {\displaystyle{1…N}} (то есть последовательности длины {\displaystyle{N}}), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка {\displaystyle{1 \ 2 \ … \ N}}, а последней — {\displaystyle{N \ (N-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 <iostream>
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 + 1]) 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 < r)
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;
}
Перестановки с повторениями
Особого внимания заслуживает задача генерации перестановок {\displaystyle{N}} элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов {\displaystyle{n_1,\ n_2,\ …\ n_k}}, где элемент {\displaystyle{n_1}} повторяется {\displaystyle{r_1}} раз, {\displaystyle{n_2}} повторяется {\displaystyle{r_2}} раз и т.д.
При этом {\displaystyle{n_1 + n_2 + … + n_k = N}}.
Если мы будем считать все {\displaystyle{n_1 + n_2 + … + n_k}} элементов перестановки с повторениями различными, то всего различных вариантов перестановок {\displaystyle{(n_1 + n_2 + … + n_k)!}}.
Однако среди этих перестановок не все различны. В самом деле, все {\displaystyle{r_1}} элементов {\displaystyle{n_1}} мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы {\displaystyle{n_2}}, {\displaystyle{n_3}} и т. д. В итоге имеем {\displaystyle{r_1!}} вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов {\displaystyle{n_1}}.
Таким образом, всякая перестановка может быть записана {\displaystyle{r_1! \cdot r_2! \cdot … \cdot r_k!}} способами. Следовательно, число различных перестановок с повторениями равно
{\displaystyle{P=\frac {n!}{r_1! \cdot r_2! \cdot … \cdot r_k!}}}
Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив a.
Ниже приведен код программы для генерации перестановок с повторениями (изменен только код функции main()).
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 <iostream>
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 + 1]) 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 < r)
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] = 1; // повторяющийся элемент
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}Результат работы приведенного выше алгоритма:
