В комбинаторике сочетанием из {\displaystyle{N}} различных элементов по {\displaystyle{M}} называется набор {\displaystyle{M}} элементов, выбранных из множества {\displaystyle{N}} элементов.
Такие наборы отличаются только вхождением в них {\displaystyle{M}} определенных элементов, порядок следования элементов в таком наборе не важен.
Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, и этим сочетания отличаются от размещений.
Сочетания без повторений
Задача: Найти все возможные сочетания без повторений из множества элементов {1,2,3} по 2.
Существуют следующие сочетания:
- 1: 1 2
- 2: 1 3
- 3: 2 3
Количество возможных сочетаний без повторений из {\displaystyle{N}} элементов по {\displaystyle{M}} можно определить по формуле ({\displaystyle{N \geq M}}):
{\displaystyle{\frac {N!}{(N-M)! \cdot M!}}}
что в {\displaystyle{M!}} раз меньше соответствующего количества размещений без повторений (поскольку сочетания без повторений не зависят от порядка следования элементов).
Рассмотрим задачу получения всех сочетаний для чисел {\displaystyle{1…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
#include <iostream>
using namespace std;
bool NextSet(int *a, int n, int m)
{
int k = m;
for (int i = k - 1; i >= 0; --i)
if (a[i] < n - k + i + 1)
{
++a[i];
for (int j = i + 1; j < k; ++j)
a[j] = a[j - 1] + 1;
return true;
}
return false;
}
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, m, *a;
cout << "N = ";
cin >> n;
cout << "M = ";
cin >> m;
a = new int[n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
Print(a, m);
if (n >= m)
{
while (NextSet(a, n, m))
Print(a, m);
}
delete []a;
cin.get(); cin.get();
return 0;
}
Сочетания с повторениями
Сочетаниями с повторениями называются наборы по {\displaystyle{M}} элементов, в которых каждый элемент множества {\displaystyle{N}} может участвовать несколько раз. При этом на соотношение значений {\displaystyle{M}} и {\displaystyle{N}} не накладывается никаких ограничений, а общее количество сочетаний с повторениями составляет
{\displaystyle{\frac {(N+M-1)!}{(N-1)! \cdot M!}}}
Примером такой задачи может служить выбор {\displaystyle{M}} открыток из {\displaystyle{N}} всеми возможными способами.
Для генерации сочетаний с повторениями воспользуемся решением для генерации размещений с повторениями, рассмотренным в этой статье.
Реализация на С++
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
#include <iostream>
using namespace std;
bool NextSet(int *a, int n, int m)
{
int j = m - 1;
while (a[j] == n && j >= 0) j--;
if (j < 0) return false;
if (a[j] >= n)
j--;
a[j]++;
if (j == m - 1) return true;
for (int k = j + 1; k < m; k++)
a[k] = a[j];
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, m, *a;
cout << "N = ";
cin >> n;
cout << "M = ";
cin >> m;
int h = n > m ? n : m; // размер массива а выбирается как max(n,m)
a = new int[h];
for (int i = 0; i < h; i++)
a[i] = 1;
Print(a, m);
while (NextSet(a, n, m))
Print(a, m);
delete []a;
cin.get(); cin.get();
return 0;
}
Реализация на VBA
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
Dim k%, i%, j%
k = m
For i = k — 1 To 0 Step -1
If (a(i) < n — k + i + 1) Then
a(i) = a(i) + 1
j = i + 1
Do While j < k
a(j) = a(j — 1) + 1
j = j + 1
Loop
nextSet = True
Exit Function
End If
Next i
nextSet = False
End Function
Sub main()
Dim n%, m%, a() As Integer, k%, i%, j%
Cells.ClearContents
n = 4
m = 2
ReDim a(0 To n — 1)
For i = 0 To n — 1
a(i) = i + 1
Next i
k = 1
If n >= m Then
For j = 0 To m — 1
Cells(k, j + 1) = a(j)
Next j
Do While nextSet(a, n, m)
k = k + 1
For j = 0 To m — 1
Cells(k, j + 1) = a(j)
Next j
Loop
End If
End Sub
Реализация на PascalABC
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var (m, n) := (4, 6); // Сочетания по m из n без повторений;
var a := n.Range.ToArray; // создаем и заполняем массив а[1..n] = 12…n
a[0:m].Println; //выводим первый элемент
var i := m-1;
repeat
if a[i] < n — m + i + 1 then
begin
a[i] += 1;
for var j := i+1 to m-1 do a[j] := a[j-1] +1;
a[0:m].Println;
i := m;
end;
i -= 1;
until i = -1;
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
#include <conio.h>
void main(void)
{ int n=6, k=4,
p, counter=1;
int *A = new int[k];
for (int i = 1; i <=k; i++)
A[i]=i;
p=k;
while (p>=1)
{ printf("%i)\t",counter);
for (int i = 1; i <=k; i++)
printf("%i ", A[i]);
printf("\n");
counter++;
if (A[k]==n)
p=p-1;
else
p=k;
for(int i=k; i>=p; i—)
A[i]=A[p]+i-p+1;
}
printf("Press any key…");
getch();
delete A;
return;
}
Уважаемая Елена, прошу ликбеза: если i — это переменная цикла, то чем отличается "i++" от "++i"?
Просто в Вашем коде встречается и то, и другое.
i++ сначала производит действие с переменной i, а затем увеличивает ее на 1.
++i сначала увеличивает переменную на 1, а затем производит с ней действие.
Само по себе это понятно, мой вопрос был в другом: какая разница между постинкрементом и преинкрементом, когда речь идёт о ПЕРЕМЕННОЙ ЦИКЛА? Не вообще переменной, а именно переменной цикла.
В цикле for разницы нет. Модификация переменной всегда происходит после итерации цикла.
как сделать то же самое, но для заданного множества?
Сделать выводимые числа индексами массива.
Сочетания с повторениями. А где вариант из примера, например 2 2 1? Если N=4, M=3, то количество сочетаний равно 4^3.
Сочетание под номером 5. Не путайте с размещениями, где важен порядок следования элементов.
Очень даже понятный и РАБОТАЮЩИЙ код. Спасибо.