Выводим сочетания и размещения для выборки по K элементов из N

Основные комбинаторные формулы описаны у меня, например, в этой статье, а программы к ним частично можно найти здесь.

В этой заметке также приведены функции на консольном C++ для расчёта базовых комбинаторных функций для выборок по k элементов из n:

Сочетания (комбинации) без повторения, их количество C_n^k = n! / [k! * (n-k)!]
Сочетания (комбинации) с повторением их количество C_n^k = C_n+k-1^k = (n+k-1)! / [k! * (n-1)!]
Размещения (перестановки) без повторения, количество A_n^k = n! / (n-k)! , при n=k получаем все перестановки элементов множества, которых будет n!
Размещения (перестановки) с повторением, количество A_n^k = n^k

Функции печатают получающиеся сочетания и размещения чисел 0, 1, ..., K-1 в лексикографическом порядке, возвращают общее количество найденных сочетаний или размещений. Где смог, использовал стандартные алгоритмы C++. У всех функций только 2 аргумента - K и N, их корректность не контролируется. Программа запускалась в актуальной сборке Visual Studio 2019, ниже приводится полный листинг и результат теста для k=2, n=5.

#include <algorithm>
#include <vector>
#include <numeric>
#include <iostream>
using namespace std;

//Комбинации (сочетания) без повторения C(n,k) = n! / (k! * (n-k)!)
int comb(int N, int K) {
 string bitmask(K, 1); //K лидирующих единиц
 bitmask.resize(N, 0); //дополнить до N позиций нулями
 int res = 0;
 vector <int> v;
 do {
  for (int i = 0; i < N; i++) {
   if (bitmask[i]) v.push_back(i+1);
  }
  cout << '{';
  for (int i = 0; i < v.size(); i++) {
   cout << v[i];
   if (i < v.size() - 1) cout << ", ";
  }
  cout << '}' << endl;
  v.clear();
  res++;
 } while (prev_permutation(bitmask.begin(), bitmask.end()));
 return res;
}

//Комбинации (сочетания) с повторением C(n+k-1,k) = (n+k-1)! / (k! * (n-1)!)
int comb_with_repetitions(int N, int K) {
 vector <int> d(N);
 iota(d.begin(), d.end(), 0);
 N--;
 vector <int> v(K + 1, 0);
 int res = 0;
 while (1) {
  for (int i = 0; i < K; i++) {
   if (v[i] > N) {
    v[i + 1] += 1;
    for (int k = i; k >= 0; k--) v[k] = v[i + 1];
   }
  }
  if (v[K] > 0) break;
  cout << '{';
  for (int i = K - 1; i > -1; i--) {
   cout << (d[v[i]]+1);
   if (i > 0) cout << ", ";
  }
  cout << '}' << endl;
  v[0]++;
  res++;
 }
 return res;
}

//Размещения без повторения P(n,k) = n! / (n-k)!
//При N == K имеем перестановки из N элементов, P(n) = n!
int perm(int N, int K) {
 vector <int> d(N);
 iota(d.begin(), d.end(), 0);
 int res = 0;
 do {
  cout << '{';
  for (int i = 0; i < K; i++) {
   cout << (d[i]+1);
   if (i < K - 1) cout << ", ";
  }
  cout << '}' << endl;
  reverse(d.begin() + K, d.end());
  res++;
 } while (next_permutation(d.begin(), d.end()));
 return res;
}

//Размещения с повторением P_n(k) = n^k
int perm_with_repetitions(int N, int K) {
 vector <int> d(K, 1); d[K - 1] = 0;
 int j = K, res = 0;
 while (1) {
  if (d[j - 1] == N) {
   j--;
   if (j == 0) return res;
  }
  else {
   d[j - 1]++;
   while (j < K) {
    d[j] = 1; j++;
   }
   cout << '{';
   for (int i = 0; i < K; i++) {
    cout << d[i];
    if (i < K - 1) cout << ", ";
   }
   cout << '}' << endl;
   res++;
  }
 }
}

int main() {
 const int N = 5, K = 2; // N >= K, K >= 1
 cout << "All: " << N << " Selected: " << K << endl;

 cout << "Combinations: " << endl;
 int r = comb(N, K);
 cout << "Count of Combinations = " << r << endl;

 cout << "Combinations with repetitions: " << endl;
 r = comb_with_repetitions(N, K);
 cout << "Count of Combinations with repetitions = " << r << endl;

 cout << "Permutations: " << endl;
 r = perm(N, K);
 cout << "Count of Permutations = " << r << endl;

 cout << "Permutations with repetitions: " << endl;
 r = perm_with_repetitions(N, K);
 cout << "Count of Permutations with repetitions = " << r << endl;

 return 0;
}

All: 5 Selected: 2
Combinations:
{1, 2}
{1, 3}
{1, 4}
{1, 5}
{2, 3}
{2, 4}
{2, 5}
{3, 4}
{3, 5}
{4, 5}
Count of Combinations = 10
Combinations with repetitions:
{1, 1}
{1, 2}
{1, 3}
{1, 4}
{1, 5}
{2, 2}
{2, 3}
{2, 4}
{2, 5}
{3, 3}
{3, 4}
{3, 5}
{4, 4}
{4, 5}
{5, 5}
Count of Combinations with repetitions = 15
Permutations:
{1, 2}
{1, 3}
{1, 4}
{1, 5}
{2, 1}
{2, 3}
{2, 4}
{2, 5}
{3, 1}
{3, 2}
{3, 4}
{3, 5}
{4, 1}
{4, 2}
{4, 3}
{4, 5}
{5, 1}
{5, 2}
{5, 3}
{5, 4}
Count of Permutations = 20
Permutations with repetitions:
{1, 1}
{1, 2}
{1, 3}
{1, 4}
{1, 5}
{2, 1}
{2, 2}
{2, 3}
{2, 4}
{2, 5}
{3, 1}
{3, 2}
{3, 3}
{3, 4}
{3, 5}
{4, 1}
{4, 2}
{4, 3}
{4, 4}
{4, 5}
{5, 1}
{5, 2}
{5, 3}
{5, 4}
{5, 5}
Count of Permutations with repetitions = 25

В листинге показано, что функцию perm можно использовать и для генерации всех перестановок элементов множества (без повторений).

Что касается всех перестановок элементов множества с повторениями (часть 2 по ссылке,п.4), попробуем их вывести, например, так:

#include <iostream>
#include <algorithm>
using namespace std;

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], a[k]);
 int l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
 while (l < r) {
  swap(a[l], a[r]);
  l++; r--;
 }
 return true;
}

void Print(int* a, int n) { // вывод перестановки
 cout << '{';
 for (int i = 0; i < n; i++) {
  cout << a[i];
  if (i < n - 1) cout << ", ";
 }
 cout << '}' << endl;
}

int main() {
 const int n = 5;
 int a[n] = { 1,1,3,4,5 }; // есть повторяющийся элемент
 Print(a, n);
 int cnt = 1;
 while (NextSet(a, n)) { 
  Print(a, n); cnt++; 
 }
 cout << "Count = " << cnt << endl;
 return 0;
}

{1, 1, 3, 4, 5}
{1, 1, 3, 5, 4}
{1, 1, 4, 3, 5}
{1, 1, 4, 5, 3}
{1, 1, 5, 3, 4}
{1, 1, 5, 4, 3}
{1, 3, 1, 4, 5}
{1, 3, 1, 5, 4}
{1, 3, 4, 1, 5}
{1, 3, 4, 5, 1}
{1, 3, 5, 1, 4}
{1, 3, 5, 4, 1}
{1, 4, 1, 3, 5}
{1, 4, 1, 5, 3}
{1, 4, 3, 1, 5}
{1, 4, 3, 5, 1}
{1, 4, 5, 1, 3}
{1, 4, 5, 3, 1}
{1, 5, 1, 3, 4}
{1, 5, 1, 4, 3}
{1, 5, 3, 1, 4}
{1, 5, 3, 4, 1}
{1, 5, 4, 1, 3}
{1, 5, 4, 3, 1}
{3, 1, 1, 4, 5}
{3, 1, 1, 5, 4}
{3, 1, 4, 1, 5}
{3, 1, 4, 5, 1}
{3, 1, 5, 1, 4}
{3, 1, 5, 4, 1}
{3, 4, 1, 1, 5}
{3, 4, 1, 5, 1}
{3, 4, 5, 1, 1}
{3, 5, 1, 1, 4}
{3, 5, 1, 4, 1}
{3, 5, 4, 1, 1}
{4, 1, 1, 3, 5}
{4, 1, 1, 5, 3}
{4, 1, 3, 1, 5}
{4, 1, 3, 5, 1}
{4, 1, 5, 1, 3}
{4, 1, 5, 3, 1}
{4, 3, 1, 1, 5}
{4, 3, 1, 5, 1}
{4, 3, 5, 1, 1}
{4, 5, 1, 1, 3}
{4, 5, 1, 3, 1}
{4, 5, 3, 1, 1}
{5, 1, 1, 3, 4}
{5, 1, 1, 4, 3}
{5, 1, 3, 1, 4}
{5, 1, 3, 4, 1}
{5, 1, 4, 1, 3}
{5, 1, 4, 3, 1}
{5, 3, 1, 1, 4}
{5, 3, 1, 4, 1}
{5, 3, 4, 1, 1}
{5, 4, 1, 1, 3}
{5, 4, 1, 3, 1}
{5, 4, 3, 1, 1}
Count = 60

Здесь только один из элементов повторяется дважды, задавая повторения других элементов массива, можно посмотреть и расчёты в более общем случае, когда "сортов" объектов более двух. Предполагается, что исходный массив упорядочен, например, {1, 1, 2, 2, 3}.

Ниже прикреплён документ, содержащий все шесть основных комбинаторных формул для сочетаний, размещений и перестановок всех элементов (то и другое без повторений и с повторениями), а также сами комбинации чисел для случая N = 5 и K = 2.

Скачать документ Word 2007 и выше в архиве .zip (15 Кб)

Далее прикреплён документ, содержащий таблицы значений сочетаний (С) и размещений (A) без повторений и с повторениями (r) для значений n, k от 1 до 20 включительно.

Скачать документ Excel 2007 и выше в архиве .zip (53 Кб)

14.09.2021, 12:16 [3828 просмотров]

теги: c++ числа алгоритм математика

Для добавления комментариев нужен включённый в Вашем браузере Javascript. Как включить? Вернуться к статье