हम एक स्ट्रिंग के कैरेक्टर्स को अलग-अलग क्रम में व्यवस्थित कर सकते हैं। यहां हम देखेंगे कि दी गई स्ट्रिंग से कितने क्रमचय बनाए जा सकते हैं।
हम जानते हैं कि यदि एक स्ट्रिंग 'abc' है। इसमें तीन कैरेक्टर्स हैं; हम उन्हें 3! = 6 अलग-अलग तरीकों से व्यवस्थित कर सकते हैं। इसलिए n कैरेक्टर्स वाली स्ट्रिंग के लिए, हम उन्हें n! अलग-अलग तरीकों से व्यवस्थित कर सकते हैं। लेकिन अब यदि समान कैरेक्टर्स कई बार मौजूद हैं, जैसे aab, तो 6 क्रमचय नहीं होंगे।
- aba
- aab
- baa
- baa
- aab
- aba
यहां (1,6), (2,5), (3,4) समान हैं। इसलिए यहां क्रमचयों की संख्या 3 है। यह मूल रूप से (n!)/(उन सभी कैरेक्टर्स के फैक्टोरियल का योग जो एक से अधिक बार आ रहे हैं) है।
इस समस्या को हल करने के लिए, पहले हमें सभी कैरेक्टर्स की आवृत्ति (frequency) की गणना करनी होगी। फिर n का फैक्टोरियल गिनें, फिर इसे उन सभी आवृत्ति मानों के फैक्टोरियल के योग से विभाजित करें जो 1 से अधिक हैं।
उदाहरण कोड
#include <iostream>
#include <string>
using namespace std;
long fact(long n) {
if (n == 0 || n == 1)
return 1;
return n * fact(n - 1);
}
int countPermutation(string str) {
int freq[26] = {0};
for (int i = 0; i < str.size(); i++) {
freq[str[i] - 'a']++; // प्रत्येक कैरेक्टर की आवृत्ति प्राप्त करें
}
int res = fact(str.size()); // लंबाई n की स्ट्रिंग के लिए n!
for (int i = 0; i < 26; i++) {
if (freq[i] > 1)
res /= fact(freq[i]); // n! को (प्रत्येक कैरेक्टर की घटनाओं)! से विभाजित करें
}
return res;
}
int main() {
string n;
cout << "क्रमचय गिनने के लिए स्ट्रिंग दर्ज करें: ";
cin >> n;
cout << "\nक्रमचयों की संख्या: " << countPermutation(n);
return 0;
}
आउटपुट
क्रमचय गिनने के लिए स्ट्रिंग दर्ज करें: abbc क्रमचयों की संख्या: 12
व्याख्या
स्ट्रिंग "abbc": लंबाई = 4, आवृत्तियाँ: a=1, b=2, c=1
कुल क्रमचय = 4! / (2!) = 24 / 2 = 12
सुधार और विचार
- बड़े स्ट्रिंग्स के लिए: फैक्टोरियल जल्दी ओवरफ्लो होता है।
long longया बिग इंटीजर लाइब्रेरी का उपयोग करें। - केस-सेंसिटिविटी: वर्तमान कोड केवल लोअरकेस मानता है। सभी ASCII के लिए, 256 आकार की सरणी का उपयोग करें।
- मॉड्यूलो अंकगणित: प्रतिस्पर्धात्मक प्रोग्रामिंग में, परिणाम को मॉड्यूलो (जैसे 10⁹+7) में पूछा जाता है। मॉड्यूलर व्युत्क्रम का उपयोग करें।
- STL विकल्प:
next_permutationका उपयोग करके सभी क्रमचय उत्पन्न करें (केवल छोटे n के लिए संभव)।
// मॉड्यूलो संस्करण (1e9+7)
const long long MOD = 1000000007;
long long modFact(long long n) {
long long res = 1;
for (long long i = 2; i <= n; i++)
res = (res * i) % MOD;
return res;
}
long long modInverse(long long a) {
// फर्मेट का लिटिल थ्योरम: a^(MOD-2) % MOD
long long res = 1, exp = MOD - 2;
while (exp) {
if (exp & 1) res = (res * a) % MOD;
a = (a * a) % MOD;
exp >>= 1;
}
return res;
}