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

Алгоритмизация / Генерация сочетаний

В комбинаторике сочетанием из N различных элементов по M называется набор M элементов, выбранных из множества N элементов. Такие наборы отличаются только вхождением в них M определенных элементов, порядок следования элементов в таком наборе не важен. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, и этим сочетания отличаются от размещений.

Сочетания без повторений

Задача: Найти все возможные сочетания без повторений из множества элементов {1,2,3} по 2.
Существуют следующие сочетания:
1: 1 2
2: 1 3
3: 2 3

Количество возможных сочетаний без повторений из N элементов по M можно определить по формуле (N≥M):

Количество сечетаний из N по M

что в M! раз меньше соответствующего количества размещений без повторений (поскольку сочетания без повторений не зависят от порядка следования элементов).

Рассмотрим задачу получения всех сочетаний для чисел 1...N по M.

Реализация

#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 m) {
  static int last = n;
  int j = m;
  while (a[j] < a[m-1] && j < last) j++;
  if (j < last) {
    swap(a, m - 1, j);
    return true;
  }
  for (int i = m - 1; i < last - 1; i++)
    swap(a, i, i + 1);
  int d = a[0];
  for (int i = 0; i < last - 1; i++)
    a[i] = a[i + 1];
  a[last - 1] = d;
  last--;
  if (last < m)
    return false;
  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;
  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);
  }
  cin.get(); cin.get();
  return 0;
}

Результат выполнения
Генерация сочетаний без повторений

Сочетания с повторениями

Сочетаниями с повторениями называются наборы по M элементов, в которых каждый элемент множества N может участвовать несколько раз. При этом на соотношение значений M и N не накладывается никаких ограничений, а общее количество сочетаний с повторениями составляет

Количество сочетаний с повторениями

Примером такой задачи может служить выбор M открыток из N всеми возможными способами.

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

Реализация

#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]; // значения меньше 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);
  cin.get(); cin.get();
  return 0;
}

Результат работы приведенного выше алгоритма:
Генерация сочетаний с повторениямиГенерация сочетаний с повторениями
Назад

Добавить комментарий

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