একটি N-ary ট্রি দেওয়া আছে এবং আমাদের এই ট্রি ট্রাভার্স (traverse) করার মোট উপায়ের (number of ways) সংখ্যা বের করতে হবে। উদাহরণ −

উপরের ট্রির জন্য আউটপুট হবে ১৯২।
এই সমস্যা সমাধানের জন্য কৌম্বিনেট্রিক্স (Combinatorics) সম্পর্কে জ্ঞান প্রয়োজন। এই সমস্যায় আমরা সহজে প্রতিটি পথের সব সম্ভাব্য কম্বিনেশন চেক করব এবং সেটিই উত্তর দেবে।
এই পদ্ধতিতে, আমরা সিম্পলি লেভেল অর্ডার ট্রাভার্সাল (level order traversal) করব এবং প্রতিটি নোডের কতটি চাইল্ড (child) আছে সেটি চেক করব এবং তার ফ্যাক্টোরিয়াল (factorial) কে আন্সারের সাথে গুণ করব।
উপরোক্ত পদ্ধতির 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 (Breadth-First Search) বা লেভেল অর্ডার ট্রাভার্সাল প্রয়োগ করি এবং প্রতিটি নোডের চাইল্ড সংখ্যা চেক করি। তারপর সেই সংখ্যার ফ্যাক্টোরিয়ালকে আন্সারের সাথে গুণ করি।
এই টিউটোরিয়ালে N-ary ট্রি ট্রাভার্স করার উপায়ের সংখ্যা বের করা হয়েছে কৌম্বিনেট্রিক্স এবং BFS প্রয়োগ করে। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই টিউটোরিয়ালটি সহায়ক পাবেন।