Các cách để chọn một hoặc nhiều cặp từ hai tập hợp khác nhau trong C ++

Trong bài toán này, ta được hai số dương n và m (n <=m) là tổng số phần tử của hai tập hợp tương ứng. Nhiệm vụ của chúng ta là tìm tổng số cách để chọn các cặp (một hoặc nhiều) từ các mục của các bộ này.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

2 2

Đầu ra

6

Giải thích

chúng ta có hai bộ đều có hai phần tử

Set A = {1, 2}
Set B = {3, 4}

Cách sắp xếp từng cặp một, (1..3), (1 ... 4), (2..3), (2 ... 4)

Cách sắp xếp hai cặp cùng một lúc, (1 ... 3, 2 ... 4), (1 ... 4, 2 ... 3)

Để giải quyết vấn đề này, chúng ta sẽ sử dụng kết hợp các phần tử của các tập hợp. Sau đây là một công thức kết hợp đơn giản có thể tìm ra số lượng.

Ways = Σn i=1n Ci* mCi* i!
= Σni=1 ( nPi * mPi) /i

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

Ví dụ

#include <iostream>
using namespace std;
int* fact, *inverseMod;
const int mod = 1e9 + 7;
int power(int x, int y, int p){
   int res = 1;
   x = x % p;
   while (y) {
      if (y & 1)
         res = (1LL * res * x) % p;
      y = y >> 1;
      x = (1LL * x * x) % p;
   }
   return res;
}
void calculate(int n){
   fact[0] = inverseMod[0] = 1;
   for (int i = 1; i <= n; ++i) {
      fact[i] = (1LL * fact[i - 1] * i) % mod;
      inverseMod[i] = power(fact[i], mod - 2, mod);
   }
}
int nPr(int a, int b) {
   return (1LL * fact[a] * inverseMod[a - b]) % mod;
}
int selectPairCount(int n, int m){
   fact = new int[m + 1];
   inverseMod = new int[m + 1];
   calculate(m);
   int ans = 0;
   for (int i = 1; i <= n; ++i) {
      ans += (1LL * ((1LL * nPr(n, i)
      * nPr(m, i)) % mod)
      * inverseMod[i]) % mod;
      if (ans >= mod)
      ans %= mod;
   }
   return ans;
}
int main() {
   int n = 2, m = 2;
   cout<<"The number of ways to select pairs is : "<<selectPairCount(n, m);
   return 0;
}

Đầu ra

The number of ways to select pairs is : 6