एक N-ary ट्री दिया गया है और हमें इस ट्री को पार करने के कुल तरीकों की संख्या निकालने का कार्य दिया गया है, उदाहरण के लिए -

उपरोक्त ट्री के लिए, हमारा आउटपुट 192 होगा।
इस समस्या के लिए, हमें कॉम्बिनेटोरिक्स के बारे में कुछ ज्ञान होना चाहिए। अब इस समस्या में, हमें बस हर पथ के लिए सभी संभावित संयोजनों की जांच करने की आवश्यकता है और यह हमें हमारा उत्तर देगा।
समाधान खोजने का दृष्टिकोण
इस दृष्टिकोण में, हमें बस एक लेवल ऑर्डर ट्रैवर्सल करने की आवश्यकता है और प्रत्येक नोड के बच्चों की संख्या जांचें और फिर बस उसके फैक्टोरियल को उत्तर से गुणा करें।
उदाहरण
उपरोक्त दृष्टिकोण के लिए C++ कोड
#include<bits/stdc++.h> using namespace std; struct Node{ // हमारे नोड की संरचना char key; vector<Node *> child; }; Node *createNode(int key){ // नया नोड इनिशियलाइज़ करने का फंक्शन Node *temp = new Node; temp->key = key; return temp; } long long fact(int n){ if(n <= 1) return 1; return n * fact(n-1); } int main(){ Node *root = createNode('A'); (root->child).push_back(createNode('B')); (root->child).push_back(createNode('F')); (root->child).push_back(createNode('D')); (root->child).push_back(createNode('E')); (root->child[2]->child).push_back(createNode('K')); (root->child[1]->child).push_back(createNode('J')); (root->child[3]->child).push_back(createNode('G')); (root->child[0]->child).push_back(createNode('C')); (root->child[2]->child).push_back(createNode('H')); (root->child[1]->child).push_back(createNode('I')); (root->child[2]->child[0]->child).push_back(createNode('N')); (root->child[2]->child[0]->child).push_back(createNode('M')); (root->child[1]->child[1]->child).push_back(createNode('L')); queue<Node*> q; q.push(root); long long ans = 1; while(!q.empty()){ auto z = q.front(); q.pop(); ans *= fact(z -> child.size()); cout << z->child.size() << " "; for(auto x : z -> child) q.push(x); } cout << ans << "\n"; return 0; }आउटपुट
4 1 2 2 1 0 0 1 2 0 0 0 0 0 192
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम BFS (ब्रेडथ-फर्स्ट सर्च) या लेवल ऑर्डर ट्रैवर्सल लागू करते हैं और प्रत्येक नोड के बच्चों की संख्या जांचते हैं। फिर, उस संख्या के फैक्टोरियल को अपने उत्तर से गुणा करते हैं।
निष्कर्ष
यह ट्यूटोरियल N-ary ट्री को पार करने के कई तरीकों को कॉम्बिनेटोरिक्स और BFS लागू करके ढूंढता है। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण भी सीखा जिसे हमने हल किया।
हम यही प्रोग्राम C, Java, Python, और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह ट्यूटोरियल उपयोगी लगा होगा।