इस समस्या में, हमें दो धनात्मक संख्याएँ n और m (n <=m) दी गई हैं जो क्रमशः दो समुच्चयों के मदों की कुल संख्या है। हमारा काम इन सेटों के आइटम से जोड़े (एक या अधिक) चुनने के तरीकों की कुल संख्या का पता लगाना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
2 2
आउटपुट
6
स्पष्टीकरण
हमारे पास दो तत्वों के साथ दो सेट हैं
Set A = {1, 2}
Set B = {3, 4} एक समय में एक जोड़ी को व्यवस्थित करने का तरीका,(1..3), (1...4), (2..3), (2...4)
एक बार में दो जोड़ियों को व्यवस्थित करने के तरीके,(1...3, 2...4) , (1...4, 2...3)
इस समस्या को हल करने के लिए, हम समुच्चय के तत्वों के संयोजन का उपयोग करेंगे। निम्नलिखित एक सरल संयोजन सूत्र है जो गिनती का पता लगा सकता है।
Ways = Σn i=1n Ci* mCi* i! = Σni=1 ( nPi * mPi) /i
हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम,
उदाहरण
#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;
} आउटपुट
The number of ways to select pairs is : 6