Перестановка – это комбинация элементов из 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 надо отсортировать все числа в порядке возрастания. Поскольку до этого они все были уже записаны в порядке убывания необходимо эту часть подпоследовательность просто перевернуть.
Таким образом мы получим новую последовательность, которая будет рассматриваться в качестве исходной на следующем шаге.
Реализация на С++
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
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;
}
Результат выполнения
Перестановки с повторениями
Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n1, n2... nk, где элемент n1 повторяется r1 раз, n2 повторяется r2 раз и т.д. При этом n1+n2+...+nk=N. Если мы будем считать все n1+n2+...+nk элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n1+n2+...+nk)! . Однако среди этих перестановок не все различны. В самом деле, все r1 элементов n1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n2, n3 и т. д. В итоге имеем r1! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n1. Таким образом, всякая перестановка может быть записана r1!·r2!·...·rk! способами. Следовательно, число различных перестановок с повторениями равно
Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив 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
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;
}
Результат работы приведенного выше алгоритма:
Назад: Алгоритмизация
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
47
48
49
50
51
52
53
54
using namespace std;
void swap(char *a, int i, int j)
{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(char *a, int k)
{
int j = k - 2;
while (j != -1 && a[j] >= a[j + 1]) j--;
if (j == -1)
return false; // больше перестановок нет
int n = k - 1;
while (a[j] >= a[n]) n--;
swap(a, j, n);
int l = j + 1, r = k - 1; // сортируем оставшуюся часть последовательности
while (l < r)
{
swap(a, l++, r--);
}
return true;
}
void Print(int *a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
int main()
{
int k;
std::cout << "k = ";
std::cin >> k;
char *a = new char[k + 1]{};
for (int i = 0; i < k; i++)
{
a[i] = 'a' + i;
}
std::cout << a << std::endl;
while (NextSet(a, k))
{
std::cout << a << std::endl;
}
return 0;
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <string>
#include <vector>
using namespace std;
void swap(int* a, int i, int j, vector<string>& vec)
{
int s = a[i];
string temp = vec[i];
a[i] = a[j];
vec[i] = vec[j];
a[j] = s;
vec[j] = temp;
}
bool NextSet(int* a, int n, vector<string>& vec)
{
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, vec);
int l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
while (l < r)
swap(a, l++, r--, vec);
return true;
}
void Print(int* a, int n, vector<string>& vec) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
cout << num++ << ": ";
for (int i = 0; i < n; i++)
cout << vec[i] << " ";
cout << endl;
}
int main()
{
vector<string> vec = { "A", "B", "C", "D" };
setlocale(LC_ALL, "ru");
int n;
string temp;
cout << "Введите кол-во элементов: ";
cin >> n;
int* a = new int [n];
for (int i = 0; i < n; i++) {
a[i] = i+1;
}
cout << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (vec[i] == vec[j])
a[j] = a[i];
}
}
Print(a, n, vec);
while (NextSet(a, n, vec))
Print(a, n, vec);
delete a;
return 0;
}
2
3
4
5
6
7
8
9
10
begin
if length(S1) > 1 then
for var i:=1 to length(S1) do Per(S0+S1[i],copy(S1,1,i-1) +
copy(S1,i+1,length(S1)))
else Writeln(S0+S1);
end;
begin
Per('','12345'); //S0 =0, S1 = Text
end.
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
var n := 4; // Перестановки для n различных элементов без повторений
var a := new integer [n + 2]; //массив для перестановки
for var e := 1 to n do a[e] := e; //начальная перестановка a = 012..n0 (c нулями по краям)
var j: integer;
repeat
a[1:n+1].Println; //вывод очередной перестановки 12..n
var i := n;
while (a[i - 1] > a[i]) do i -= 1;
j := i - 1; // индекс1 = стоящий слева от MAX двигаясь справа налево
while (a[i + 1] > a[j]) do i += 1; {индекс2 = 'элемент справа от индекс1
со значением большим значения индекс1}
( a[j], a[i] ) := ( a[i], a[j] ); //поменять местаами
{цикл зеркально переворачивает в текущей перестановке
значения справа от индекс1, и т.о. сортирует по возрастанию}
var o := j + 1;
var k := n;
While (o < k) do
begin
( a[o], a[k] ) := ( a[k], a[o] );
o += 1;
k -= 1;
end;
until j = 0;
end.
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
integer :: i,j,o,k,n,e,t,iperm,a(0:n+1)
integer,allocatable,save:: perm(:,:)
integer,save:: nperm
a = 0; iperm = 0
nperm = product([(i,i=1,n)])
allocate(perm(nperm,n))
do e = 1, n; a(e) = e; enddo
do
iperm = iperm + 1
write(*,*) a(1:n)
perm(iperm,:) = a(1:n)
i = n
do while (a(i - 1) > a(i))
i = i - 1
enddo
j = i - 1
do while (a(i + 1) > a(j))
i = i + 1
enddo
t = a(i); a(i) = a(j); a(j) = t
o = j + 1
k = n
do while (o < k)
t = a(o); a(o) = a(k); a(k) = t
o = o + 1
k = k - 1
enddo
if (j == 0) exit
enddo
endsubroutine Permutation
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdbool.h>
void swap(int *a, int i, int j)
{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
/*--------------------------------------------------*/
bool seting (int *a, int n)
{
int b = true;
int j = n - 2;
while (j != -1 && a[j] >= a[j + 1])
{
j--;
}
if (j == -1)
{
b = false; // больше перестановок нет
}
int k = n - 1;
while (a[j] >= a[k])
{
k--;
}
swap(a, j, k);
int l = j + 1;
int r = n - 1; // сортируем оставшуюся часть последовательности
while (l<r)
{
swap(a, l++, r--);
}
return b;
}
/*--------------------------------------------------*/
int out(int *a, int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += a[i] * a[i + 1];
}
return sum;
}
/*-----------------------------------------------*/
void outArr(int *a, int n)
{
for (int i = 0; i < n; i++) printf("%d ",a[i]);
}
/*----------------------------------------------*/
int main()
{
int n = 5;
int c[n];
int a[] = { 1, 2, 3, 4, 5 };
printf ("Input array: ");
outArr (a, n);
for (int i = 0; i < n - 1; i++)
{
if (a[i] > a[i + 1]);
swap (a, i, (i + 1));
}
int min = out(a, n);
while (seting(a, n))
{
if (min > out(a, n))
{
min = out(a, n);
for (int j = 0; j < n; j++)
c[j] = a[j];
}
}
printf ("\n\n\nMin sum = ");
printf ("%d\nNew array: ", min);
outArr(c, n);
return 0;
}
В Вашем примере числа стоят не в лексикографическом порядке (не по возрастанию), поэтому и теряются начальные комбинации.
Отсортируйте числа по возрастанию прежде, чем генерировать перестановки.
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
И т.д.
Если одно число повторяется, то количество перестановок будет в 2 разр меньше, т.е 60.
Все коды реализации есть в тексте статьи.
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
47
48
49
50
#include <iostream>
using namespace std;
int main()
{
int count = 1;
for (int n1 = 1; n1 <= 6; n1++)
{
for (int n2 = 1; n2 <= 6; n2++)
{
if (n2 == n1) continue;
for (int n3 = 1; n3 <= 6; n3++)
{
if (n3 == n1) continue;
if (n3 == n2) continue;
for (int n4 = 1; n4 <= 6; n4++)
{
if (n4 == n1) continue;
if (n4 == n2) continue;
if (n4 == n3) continue;
for (int n5 = 1; n5 <= 6; n5++)
{
if (n5 == n1) continue;
if (n5 == n2) continue;
if (n5 == n3) continue;
if (n5 == n4) continue;
for (int n6 = 1; n6 <= 6; n6++)
{
if (n6 == n1) continue;
if (n6 == n2) continue;
if (n6 == n3) continue;
if (n6 == n4) continue;
if (n6 == n5) continue;
if (n1 > n2) continue;
if (n3 > n4) continue;
if (n5 > n6) continue;
cout << fixed;
cout.width(3);
cout << count++ << ": ";
cout << n1 << " " << n2 << " " << n3 << " ";
cout << n4 << " " << n5 << " " << n6 << endl;
}
}
}
}
}
}
getchar();
return 0;
}
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
#include <malloc.h>
void swapInts(int pos1, int pos2, int arr[]) {
int temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
}
void printArray(int length, int arr[]) {
for (int i=0; i < length; i++) {
printf("%d ", arr[i]);
}
putchar('\n');
}
void printPermutations(int index, int length, int arr[]) {
if (index == length) {
printArray(length, arr);
return;
}
for (int i=index; i < length; i++) {
swapInts(i, index, arr);
printPermutations(index + 1, length, arr);
swapInts(i, index, arr);
}
}
int main(int argc, char *argv[]) {
int length;
printf("Type length of array: ");
scanf("%d", &length);
int *arr = malloc(length*sizeof(int));
printf("Type elements of array: ");
for (int i=0; i < length; i++) {
scanf("%d", &arr[i]);
}
printPermutations(0, length, arr);
return 0;
}
2
3
4
5
6
7
{
case 1: cout << word1 << " "; break;
case 2: cout << word2 << " "; break;
case 3: cout << word3 << " "; break;
case 4: cout << word4 << " "; break;
}