Генерация сочетаний : с повторениями и без повторений

Генерация сочетаний

В комбинаторике сочетанием из {\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}}.

Реализация на С++

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
#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}} всеми возможными способами.

Для генерации сочетаний с повторениями воспользуемся решением для генерации размещений с повторениями, рассмотренным в этой статье.

Реализация на С++

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
#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;
}

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

12 комментариев к “Генерация сочетаний”

  1. Александр Ермаков

    Реализация на VBA

    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
    Function nextSet(ByRef a() As Integer, n%, m%) As Boolean
    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

  2. Антон

    Реализация на PascalABC

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    begin 
       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.
  3. Александр

    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
    #include <stdio.h>
    #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;
    }

  4. Константин Ситников

    Уважаемая Елена, прошу ликбеза: если i — это переменная цикла, то чем отличается "i++" от "++i"?
    Просто в Вашем коде встречается и то, и другое.

    1. Елена Вставская

      i++ сначала производит действие с переменной i, а затем увеличивает ее на 1.
      ++i сначала увеличивает переменную на 1, а затем производит с ней действие.

      1. Константин Ситников

        Само по себе это понятно, мой вопрос был в другом: какая разница между постинкрементом и преинкрементом, когда речь идёт о ПЕРЕМЕННОЙ ЦИКЛА? Не вообще переменной, а именно переменной цикла.

        1. Елена Вставская

          В цикле for разницы нет. Модификация переменной всегда происходит после итерации цикла.

  5. София

    Сочетания с повторениями. А где вариант из примера, например 2 2 1? Если N=4, M=3, то количество сочетаний равно 4^3.

    1. Елена Вставская

      Сочетание под номером 5. Не путайте с размещениями, где важен порядок следования элементов.

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Прокрутить вверх