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

C++ में क्रमचय अनुक्रम (Permutation Sequence)


मान लीजिए समूह [1,2,3,...,n] है, जिसमें कुल n! अद्वितीय क्रमचय (permutations) होते हैं। सभी क्रमचयों को क्रम में सूचीबद्ध और लेबल करने पर, n = 3 के लिए हमें यह अनुक्रम मिलता है: ["123","132","213","231","312","321"]। यदि n और k दिए गए हैं, तो k-वां क्रमचय अनुक्रम वापस करें। n 1 से 9 (सम्मिलित) के बीच होगा और k 1 से n! (सम्मिलित) के बीच होगा।

आइए चरण देखें:

  • ans := खाली स्ट्रिंग, candidates नामक सरणी परिभाषित करें आकार n की
  • i को 0 से n – 1 तक की रेंज में:
    • candidates[i] := ((i + 1) + वर्ण '0')
  • fact नामक एक सरणी बनाएं आकार n + 1 की, fact[0] := 1 सेट करें
  • i को 1 से n तक की रेंज में:
    • fact[i] := fact[i – 1] * i
  • k को 1 घटाएं
  • i := n – 1 से 0 तक डाउन करें:
    • idx := k / fact[i]
    • ans := ans + candidates[idx]
    • j := idx से, j + 1 < candidates का आकार:
      • candidates[j] := candidates[j + 1]
    • k := k mod fact[i]
  • ans वापस करें

उदाहरण

#include <bits/stdc++.h>
using namespace std;

typedef long long int lli;

class Solution {
public:
    string getPermutation(int n, int k) {
        string ans = "";
        vector <char> candidates(n);
        for(lli i = 0; i < n; i++)
            candidates[i] = ((i + 1) + '0');
        vector <lli> fact(n + 1);
        fact[0] = 1;
        for(lli i = 1; i <= n; i++)
            fact[i] = fact[i - 1] * i;
        k--;
        for(lli i = n - 1; i >= 0; i--){
            lli idx = k / fact[i];
            ans += candidates[idx];
            for(lli j = idx; j + 1 < candidates.size(); j++)
                candidates[j] = candidates[j + 1];
            k = k % fact[i];
        }
        return ans;
    }
};

int main(){
    Solution ob;
    cout << ob.getPermutation(4, 9);
}

इनपुट

4 9

आउटपुट

2314
  1. - C++ में लेटर केस क्रमपरिवर्तन (Letter Case Permutation)

    मान लीजिए हमारे पास अक्षरों और संख्याओं वाली एक स्ट्रिंग है। हमें उस स्ट्रिंग के सभी संभावित संयोजन उत्पन्न करने हैं जो स्ट्रिंग में मौजूद अक्षरों के अपरकेस और लोअरकेस संस्करण लेकर बनाए जाते हैं। इसलिए यदि एक स्ट्रिंग में केवल संख्याएं हैं, तो केवल वही वापस की जाएगी। मान लीजिए स्ट्रिंग 1ab2 जैसी है,

  1. - C++ में एलिक्वोट अनुक्रम

    एलिक्वोट अनुक्रम संख्याओं का एक विशेष अनुक्रम है। अनुक्रम संख्या से ही शुरू होता है और अनुक्रम की अगली संख्या पिछले पदों के उचित भाजकों का योग होती है। आइए अनुक्रम का एक उदाहरण लेते हैं अवधारणा को बेहतर ढंग से सीखने के लिए: इनपुट: 8 आउटपुट: 8 7 1 0 व्याख्या:    8 के उचित भाजक 4, 2, 1 हैं।

  1. - C++ में लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन

    लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन यहां हम देखेंगे कि C++ में स्ट्रिंग के लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन को कैसे जनरेट करें। लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन मूल रूप से बड़ा पर्मुटेशन है। उदाहरण के लिए, ACB का नेक्स्ट BAC होगा। कुछ मामलों में, लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन मौजूद नहीं