समस्या विवरण
दो संख्याएं e और p दी गई हैं। लक्ष्य उन तरीकों की संख्या गिनना है जिनसे हम एक सेट के e तत्वों को p पार्टीशन/उपसमुच्चयों में विभाजित कर सकते हैं।
उदाहरण
इनपुट
e=4 p=2
आउटपुट
सेट को k उपसमुच्चयों में विभाजित करने के तरीकों की संख्या: 7
व्याख्या
यदि तत्व हैं: a b c d तो उन्हें 2 पार्टीशन में विभाजित करने के तरीके: (a,b,c)-(d), (a,b)-(c,d), (a,b,c)-(d), (a)-(b,c,d), (a,c)-(b,d), (a,c,d)-(b), (a,b,d)-(c)। कुल 7 तरीके।
इनपुट
e=2 p=2
आउटपुट
सेट को k उपसमुच्चयों में विभाजित करने के तरीकों की संख्या: 1
व्याख्या
यदि तत्व हैं: a b तो उन्हें 2 पार्टीशन में विभाजित करने के तरीके: (a)-(b)। केवल 1 तरीका।
दृष्टिकोण
इस दृष्टिकोण में हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। समाधान में उपयोग की जाने वाली गणनाएं हमेशा पुनरावर्ती होंगी। यदि हम तत्वों को p पार्टीशन में विभाजित करते हैं तो:
- यदि
e-1तत्वों कोpपार्टीशन मेंways(e-1,p)तरीकों से विभाजित किया जा सकता है। तब हम वर्तमान तत्व को इनpपार्टीशन में से किसी एक मेंp * ways(e-1,p)तरीकों से रख सकते हैं। - यदि
e-1तत्वों कोp-1पार्टीशन मेंways(e-1,p-1)तरीकों से विभाजित किया जाता है तो उस अलग 1 पार्टीशन में 1 तत्व रखने के1 * ways(e-1,p-1)तरीके होंगे। कुल तरीके होंगेp * ways(e-1,p) + ways(e-1,p-1)। यह विधि पुनरावर्ती हो जाएगी।
जैसा कि ऊपर दिखाया गया है, डुप्लिकेट गणनाएं की जाएंगी। इससे बचने के लिए हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे।
एल्गोरिदम चरण
- चर
elementsऔरpartitionsइनपुट के रूप में लें। - फंक्शन
partition_k(int elements, int partition)दोनों चर लेता है और सेट को k उपसमुच्चयों में विभाजित करने के तरीकों की संख्या लौटाता है। - मान
ways(e,p)कोarr[e][p]में संग्रहीत करने के लिए 2D सरणीarr[elements + 1][partition + 1]लें। forलूप का उपयोग करकेi=0सेi=elementsतक,arr[i][0] = 0सेट करें क्योंकि पार्टीशन की संख्या 0 है तोways(i,0)=0।- फिर से
forलूप का उपयोग करकेj=0सेj=partitionsतक,arr[0][j] = 0सेट करें क्योंकि तत्वों की संख्या 0 है तोways(0,j)=0। - अब दो
forलूप का उपयोग करकेi=1सेi<=elementsऔरj=1सेj<=iतकarr[][]को पार करें और शेष मान भरें। - एकल तत्व के लिए, तरीके=1 या
xतत्वों कोxपार्टीशन में विभाजित करने के लिए केवल 1 तरीका है। इसलिएarr[i][j] = 1सेट करें यदिi==jयाj==1। - अन्यथा
temp_1 = arr[i-1][j-1]औरtemp_2 = arr[i-1][j]लें औरarr[i][j] = j * temp_2 + temp_1अपडेट करें। - सभी लूप के अंत में हमारे पास
arr[elements][partition]कुल तरीकों के रूप में होगा। - परिणाम के रूप में
arr[elements][partition]लौटाएं।
C++ कोड उदाहरण
#include <iostream>
using namespace std;
int partition_k(int elements, int partition) {
int arr[elements + 1][partition + 1];
for(int i = 0; i <= elements; i++) {
arr[i][0] = 0;
}
for(int j = 0; j <= partition; j++) {
arr[0][j] = 0;
}
for(int i = 1; i <= elements; i++) {
for (int j = 1; j <= i; j++) {
if (j == 1 || i == j) {
arr[i][j] = 1;
} else {
int temp_1 = arr[i-1][j-1];
int temp_2 = arr[i-1][j];
arr[i][j] = j * temp_2 + temp_1;
}
}
}
return arr[elements][partition];
}
int main() {
int elements = 4;
int partition = 2;
cout << "सेट को k उपसमुच्चयों में विभाजित करने के तरीकों की संख्या: " << partition_k(elements, partition);
return 0;
}
आउटपुट
सेट को k उपसमुच्चयों में विभाजित करने के तरीकों की संख्या: 7
