Пусть задано некоторое конечное множество из {\displaystyle{N}} различных элементов. И требуется выбрать из него {\displaystyle{M}} элементов. Выбранные {\displaystyle{M}} из предложенных {\displaystyle{N}} элементов называются выборкой.
Если важен порядок, в котором произведена выборка элементов, то говорят об упорядоченной выборке, если порядок не важен, то говорят о неупорядоченной выборке.
В комбинаторике упорядоченная выборка объемом {\displaystyle{M}} элементов из предложенного множества {\displaystyle{N}} различных элементов называется размещением из {\displaystyle{N}} элементов по {\displaystyle{M}}.
Все комбинации внутри размещения могут отличаться друг от друга как самими элементами, так и порядком их расположения.
Различают также размещения без повторений (когда все {\displaystyle{M}} элементов внутри выборки различны) и размещения с повторениями.
Задача: Найти все возможные размещения из множества элементов {1,2,3} по 2.
Существуют следующие размещения:
- 1: 1 2
- 2: 1 3
- 3: 2 1
- 4: 2 3
- 5: 3 1
- 6: 3 2
Размещения без повторений
В случае размещения без повторений количество элементов множества {\displaystyle{N}}.
Количество размещений без повторений для {\displaystyle{N}} различных элементов по {\displaystyle{M}} составляет составляет
{\displaystyle{K= \frac {N!} {(N-M)!}}}
В случае если {\displaystyle{N=M}}, количество размещений совпадает с количеством перестановок без повторений и составляет {\displaystyle{N!}}. Такое же количество размещений получится в случае если {\displaystyle{M=N-1}}.
Рассмотрим задачу получения всех размещений без повторений для чисел {\displaystyle{1…N}} по {\displaystyle{M}}.
Для генерации всех возможных размещений из {\displaystyle{N}} по {\displaystyle{M}} в лексикографическом порядке воспользуемся ранее рассмотренным решением для генерации перестановок без повторений.
Реализация на С++
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;
Print(a, n);
while (NextSet(a, n))
Print(a, n);
delete [] a;
cin.get(); cin.get();
return 0;
}Результат выполнения
Размещения с повторениями
В случае если элементы из множества {\displaystyle{N}} могут повторяться в выборках по {\displaystyle{M}} элементов, общее количество таких размещений составляет
{\displaystyle{N^M}}
При этом не накладывается ограничений на размерность рассматриваемого массива {\displaystyle{N}} по сравнению с {\displaystyle{M}} (может быть как {\displaystyle{N \geq M}}, так и {\displaystyle{N \lt M}}).
Примером такой задачи может служить подбор шифра сейфа из {\displaystyle{M \lt 10}} цифр, которые должны набираться последовательно и могут повторяться.
Для генерации размещений с повторениями удобно было бы использовать {\displaystyle{M}} вложенных циклов, однако такое решение применимо только к задаче, в которой заранее известно число {\displaystyle{M}}. Поэтому рассмотрим более общий вариант генерации размещений с повторениями.
Реализация на С++
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
#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);
delete [] a;
cin.get(); cin.get();
return 0;
}
