দেওয়া সমস্যায়, আমাদের একটি স্ট্রিং দেওয়া আছে যা শুধু ০ এবং ১ দিয়ে গঠিত। আমাদের সেই স্ট্রিংয়ের এমন পারমুটেশনের (বিন্যাসের) মোট সংখ্যা বের করতে হবে যাতে স্ট্রিংটি ১ দিয়ে শুরু হয়। উত্তর খুব বড় হতে পারার কারণে, আমরা এটিকে ১০০০০০০০০৭ (১০⁹+৭) দিয়ে মডুলো করে প্রিন্ট করব।
ইনপুট: str = "10101001001" আউটপুট: 210 ইনপুট: str = "101110011" আউটপুট: 56
আমরা এই সমস্যাটি কৌম্বিনেটরিক্স (Combinatorics) এবং কিছু সূত্র প্রয়োগ করে সমাধান করব।
এই পদ্ধতিতে, আমরা স্ট্রিংয়েতে ০ এবং ১-এর সংখ্যা গণনা করব। ধরি, n = ১-এর সংখ্যা, m = ০-এর সংখ্যা, এবং L = স্ট্রিংয়ের দৈর্ঘ্য। তাহলে সমাধানের সূত্র হবে: (L-1)! / ((n-1)! * m!)।
#include <bits/stdc++.h> #define MOD 1000000007 using namespace std; long long fact(long long n) { if(n <= 1) return 1; return ((n % MOD) * (fact(n-1) % MOD)) % MOD; } int main() { string s = "101110011"; long long L = s.size(); long long count_1 = 0, count_0 = 0; for(auto x : s) { if(x == '1') count_1++; else count_0++; } if(count_1 == 0){ cout << "0\n"; } else { long long factL = fact(L-1); long long factn = fact(count_1 - 1); long long factm = fact(count_0); long long ans = factL / (factn * factm); cout << ans << "\n"; } return 0; }
56
উপরোক্ত প্রোগ্রামটির টাইম কমপ্লেক্সিটি O(N), যেখানে N হলো দেওয়া স্ট্রিংয়ের দৈর্ঘ্য।
এই পদ্ধতিতে, আমরা স্ট্রিংয়েতে ১ এবং ০-এর ফ্রিকোয়েন্সি গণনা করি। তারপর প্রথমে একটি ১ ঠিকিয়ে দিয়ে, বাকি L-1 দৈর্ঘ্যের স্ট্রিংয়ে বাকি ১ এবং ০-গুলোকে কতভাবে বিন্যাস করা যায় তা বের করি। এখান থেকে উপরের সূত্রটি প্রাপ্ত হয়: (L-1)! / ((n-1)! * m!)। এখানে (n-1)! হলো বাকি ১-দের পারমুটেশন এবং m! হলো ০-দের পারমুটেশন।
এই আর্টিকেলে আমরা একটি বাইনারি স্ট্রিংয়ের ১ দিয়ে শুরু হওয়া অনন্য পারমুটেশনের সংখ্যা বের করার সমস্যা সমাধান করেছি কৌম্বিনেটরিক্স এবং সূত্র প্রয়োগ করে। আমরা এই সমস্যার C++ প্রোগ্রামও দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটি সহায়ক পাবেন।
