दो अंक e और p दिए गए हैं। लक्ष्य उन तरीकों की संख्या गिनना है जिनसे हम एक सेट के e तत्वों को p विभाजन/सबसेट में विभाजित कर सकते हैं।
उदाहरण के लिए
इनपुट
e=4 p=2
आउटपुट
Count of number of ways to partition a set into k subsets are: 7
स्पष्टीकरण
If elements are: a b c d then ways to divide them into 2 partitions are: (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). Total 7 ways.
इनपुट
e=2 p=2
आउटपुट
Count of number of ways to partition a set into k subsets are: 1
स्पष्टीकरण
If elements are: a b then ways to divide them into 2 partitions are: (a)− (b). Total 1 way only.
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
इस दृष्टिकोण में हम एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। समाधान में प्रयुक्त गणना हमेशा पुनरावर्ती होगी। यदि हम तत्वों को p विभाजनों में विभाजित करते हैं तो -
-
यदि e−1 तत्वों को p विभाजनों में विभाजित किया जा सकता है (e-1,p)। फिर हम p*ways(e-1,p) में इन p विभाजनों में से एक में वर्तमान तत्व डाल सकते हैं।
-
यदि e−1 तत्वों को p−1 विभाजनों में विभाजित किया जाता है (e−1,p−1) तो उस अलग 1 विभाजन में 1 तत्व डालने पर 1* तरीके (e−1,p−1) होंगे। कुल तरीके bep*ways(e−1,p)+ways(e−1,p−1) होंगे। यह विधि पुनरावर्ती हो जाएगी -
जैसा कि ऊपर दिखाया गया है, डुप्लिकेट गणना की जाएगी। इससे बचने के लिए हम गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे।
-
इनपुट के रूप में चर, तत्व और विभाजन लें।
-
फंक्शन पार्टीशन_के(इंट एलीमेंट, इंट पार्टीशन) दोनों चर लेता है और सेट को k सबसेट में विभाजित करने के तरीकों की संख्या देता है।
-
एआर [ई] [पी] में तरीकों (ई, पी) के मूल्यों को स्टोर करने के लिए 2 डी सरणी गिरफ्तारी [तत्व + 1] [विभाजन + 1] लें।
-
i=0 से i=elements तक लूप के लिए का उपयोग करते हुए, arr[i][0] =0 सेट करें क्योंकि विभाजनों की संख्या 0 है तो तरीके (i,0)=0.
-
फिर से j=0 से i=partitions के लिए लूप का उपयोग करते हुए, arr[0][j] =0 सेट करें क्योंकि तत्वों की संख्या 0 है तो तरीके (0,i)=0.
-
अब i=1 से i<=elements और j=1 से j<=i तक दो लूप के लिए ट्रैवर्स arr[][] का उपयोग करें। और बाकी मान भरें।
-
एकल तत्व के लिए, तरीके =1 या x तत्वों को x विभाजन में विभाजित करने के लिए केवल 1 तरीका है। इसलिए i==j या j==1 के मामले में arr[i][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] कुल तरीकों के रूप में होगा।
-
परिणाम के रूप में वापसी गिरफ्तारी [तत्व] [विभाजन]।
उदाहरण
#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][partition] = 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<<"Count of number of ways to partition a set into k subsets are: "<<partition_k(elements, partition);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of number of ways to partition a set into k subsets are: 7