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

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

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

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

  • Комбинации (сочетания) без повторения, их количество Cnk = n! / [k! * (n-k)!]
  • Комбинации (сочетания) с повторением их количество Cnk = Cn+k-1k = (n+k-1)! / [k! * (n-1)!]
  • Перестановки (размещения) без повторения, количество Ank = n! / (n-k)! , при n=k получаем все перестановки элементов множества, которых будет n!
  • Перестановки (размещения) с повторением, количество Ank = nk

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

#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;
 do {
  for (int i = 0; i < N; i++) if (bitmask[i]) cout << i << ' ';
  cout << endl;
  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;
  for (int i = K - 1; i > -1; i--) cout << d[v[i]] << ' ';
  cout << endl;
  v[0]++;
  res++;
 }
 return res;
}

//Перестановки (размещения) без повторения P(n,k) = n! / (n-k)!
int perm (int N, int K) {
 vector <int> d(N);
 iota(d.begin(), d.end(), 0);
 int res = 0;
 do {
  for (int i = 0; i < K; i++) cout << d[i] << ' ';
  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++;
   }
   for (int i = 0; i < K; i++) cout << d[i]-1 << ' ';
   cout << endl;
   res++;
  }
 }
}

int main() {
 const int N = 3, K = 2;
 
 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;
}
Combinations:
0 1
0 2
1 2
Count of Combinations = 3
Combinations with repetitions:
0 0
0 1
0 2
1 1
1 2
2 2
Count of Combinations with repetitions = 6
Permutations:
0 1
0 2
1 0
1 2
2 0
2 1
Count of Permutations = 6
Permutations with repetitions:
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
Count of Permutations with repetitions = 9

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


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