Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम: दी गई स्ट्रिंग के क्रमचय (Permutations) की संख्या ज्ञात करना


हम एक स्ट्रिंग के कैरेक्टर्स को अलग-अलग क्रम में व्यवस्थित कर सकते हैं। यहां हम देखेंगे कि दी गई स्ट्रिंग से कितने क्रमचय बनाए जा सकते हैं।

हम जानते हैं कि यदि एक स्ट्रिंग '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;
}
  1. दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स और m एज वाला एक अनभारित, निदेश रहित ग्राफ दिया गया है। ग्राफ में एक ब्रिज एज वह एज है जिसे हटाने से ग्राफ असंबद्ध हो जाता है। हमें दिए गए ग्राफ में ऐसी एज की संख्या ज्ञात करनी है। ग्राफ में समानांतर एज या सेल्फ-लूप नहीं हैं। उदाहरण के लिए, यदि इनपुट है n = 5, m = 6, edges = {{1

  1. - C++ में दिए गए संख्या N के भाजकों में सबसे बड़ी अच्छी संख्या ज्ञात करें

    इस समस्या में, हमें एक संख्या N दी गई है। हमारा कार्य दिए गए संख्या N के भाजकों में सबसे बड़ी अच्छी संख्या ज्ञात करना है। एक अच्छी संख्या वह संख्या है जिसमें प्रत्येक अंक उसके दाईं ओर के अंकों के योग से बड़ा होता है (उससे कम महत्वपूर्ण सभी बिट्स)। उदाहरण के लिए, 732 एक अच्छी संख्या है, 7> 3+2 और

  1. C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना

    इस लेख में, आप एक दी गई स्ट्रिंग में बनने वाले सबस्ट्रिंग्स (गैर-खाली) की संख्या निकालने के दृष्टिकोण के बारे में जानेंगे।इनपुट: string = moon आउटपुट: 10 व्याख्या: सबस्ट्रिंग्स हैं m, o, o, n, mo, oo, on, moo, oon और moon। इनपुट: string = yellow आउटपुट: 21समाधान खोजने का दृष्टिकोणमान लें स्ट्रिंग की