दो दिए गए क्रमबद्ध सरणियों के वैकल्पिक तत्वों से सभी संभव सॉर्ट किए गए सरणियों को उत्पन्न करें


कठिनाई स्तर मध्यम
में अक्सर पूछा डायरेक्टी खरात पेपैल Twilio Yandex
ऐरे Recursion

समस्या "दो दिए गए क्रमबद्ध सरणियों के वैकल्पिक तत्वों से सभी संभव सॉर्ट किए गए सरणियों को उत्पन्न करें" कहती है कि मान लें कि आपके पास दो सॉर्ट किए गए सरणियाँ हैं। समस्या बयान सभी संभावित हल किए गए सरणियों का पता लगाने के लिए कहता है, जैसे कि दो अलग-अलग सरणियों से वैकल्पिक रूप से नंबर की व्यवस्था की जानी चाहिए।

उदाहरण

ArrA[] = {9, 12, 66}
ArrB[] = {10, 15, 25}
9 10
9 10 12 15
9 10 12 25
9 15
9 25
12 15
12 25

व्याख्या

सभी वैकल्पिक नंबर अलग-अलग सरणियों से हैं और क्रमबद्ध हैं।

दो दिए गए क्रमबद्ध सरणियों के वैकल्पिक तत्वों से सभी संभव सॉर्ट किए गए सरणियों को उत्पन्न करें

 

कलन विधि

  1. आकार का एक आउटपुट सरणी घोषित करें m + n (दोनों सरणियों की कुल लंबाई)।
  2. अगर जांच मल सच हैं,
    1. फिर जांचें कि यदि आउटपुट ऐरे की लंबाई 0 के बराबर नहीं है, तो आउटपुट ऐरे को प्रिंट करें।
      1. सरणी को पीछे छोड़ें अर्रा और निम्नलिखित की जाँच करें
        1. यदि आउटपुट ऐरे की लंबाई 0 है, तो आउटपुट एलिमेंट के करंट एलिमेंट को कॉपी करें और फिर फंक्शन को कॉल करें।
    2. यदि वर्तमान सरणी तत्व पिछले आउटपुट सरणी तत्व से अधिक है, तो उस तत्व को कॉपी करें अर्रा आउटपुट सरणी में और पुनरावर्ती रूप से फ़ंक्शन को कॉल करें।
  3. वरना अगर बूलॉन्डिशन झूठा है, तो ट्रैवस करें एआरआरबी और अगर मौजूदा तत्व की जाँच करें एआरआरबी आउटपुट सरणी के वर्तमान तत्व से अधिक है
      1. यदि सत्य है तो तत्व को कॉपी करें एआरआरबी आउटपुट सरणी और पुनरावर्ती फ़ंक्शन को कॉल करने के लिए।

व्याख्या

समस्या "दो दिए गए क्रमबद्ध सरणियों के वैकल्पिक तत्वों से सभी संभव सॉर्ट किए गए सरणियों को उत्पन्न करें" को निम्न तरीके से हल किया जा सकता है। यहां हमें दो क्रमबद्ध एरेज़ दिए गए हैं अर्रा और एआरआरबी। दिए गए दोनों सरणियाँ क्रमबद्ध क्रम में हैं। इसलिए, हमें हर संभव पता लगाने की जरूरत है सरणियों जिसका निर्माण क्रमबद्ध तरीके से किया जा सकता है। एक और शर्त यह भी है कि आउटपुट में प्रत्येक वैकल्पिक तत्व विभिन्न सरणियों से आना चाहिए।

हम सभी संभावित आउटपुट सरणियों का पता लगाने के लिए उस फ़ंक्शन को पुन: कॉल करेंगे। फिर हम एक बूलियन वैरिएबल रखते हैं जो चुने जाने वाले तत्वों का ट्रैक रखता है। वह या तो तत्व वर्तमान अर्रा या आरआरबी से है। यदि बूलियन चर सच है, तो हम पहले सरणी अर्रा से एक तत्व का चयन करते हैं। वरना अगर बूलियन वैरिएबल गलत है, तो हम दूसरे एरे Arb से एलिमेंट का चयन करते हैं। यदि बूलियन चर सच है, तो हम यह जांचने जा रहे हैं कि सरणी की लंबाई 0 के बराबर नहीं है या केवल 0 से अधिक है, तो हर बार हम आउटपुट सरणी को प्रिंट करने जा रहे हैं।

यदि बूलियन स्थिति सत्य है, तो हम सरणी अर्रा को ट्रैस करने जा रहे हैं। फिर आउटपुट सरणी में वर्तमान सरणी तत्व की प्रतिलिपि बनाएँ। फिर हम पुनरावर्ती रूप से सभी आवश्यक तर्कों को पारित करने वाले फ़ंक्शन को कॉल करते हैं। यदि बूलियन स्थिति झूठी है। फिर हम अपने आउटपुट ऐरे से कॉपी और अपडेट करने के लिए ArrB का उपयोग करते हैं। और हर बार जब आउटपुट ऐरे की लंबाई 0 होती है, तब ऐरे को प्रिंट करें।

कोड

C ++ कोड सभी संभव सॉर्ट किए गए सरणियों को उत्पन्न करने के लिए

#include<iostream>
using namespace std;

void printArray(int arr[], int n);

void getSortedArr(int ArrA[], int ArrB[], int output[], int i, int j, int m, int n, int len, bool flag)
{
    if (flag)
    {
        if (len)
            printArray(output, len+1);

        for (int k = i; k < m; k++)
        {
            if (!len)
            {
                output[len] = ArrA [k];
                getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len, !flag);
            }
            else
            {
                if (ArrA [k] > output[len])
                {
                    output[len+1] = ArrA [k];
                    getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len+1, !flag);
                }
            }
        }
    }
    else
    {
        for (int l = j; l < n; l++)
        {
            if (ArrB[l] > output[len])
            {
                output[len+1] = ArrB[l];
                getSortedArr(ArrA, ArrB, output, i, l+1, m, n, len+1, !flag);
            }
        }
    }
}

void generate(int ArrA [], int ArrB[], int m, int n)
{
    int output[m+n];
    getSortedArr(ArrA, ArrB, output, 0, 0, m, n, 0, true);
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int ArrA [] = {9, 12, 66};
    int ArrB[] = {10, 15, 25};
    int n = sizeof(ArrA)/sizeof(ArrA [0]);
    int m = sizeof(ArrB)/sizeof(ArrB[0]);
    generate(ArrA, ArrB, n, m);
    return 0;
}
9 10
9 10 12 15
9 10 12 25
9 15
9 25
12 15
12 25

सभी संभावित सॉर्ट किए गए सरणियों को बनाने के लिए जावा कोड

class GeneratedSortedArray
{
    public static void getSortedArr(int ArrA[], int ArrB[], int output[], int i, int j, int m, int n, int len, boolean flag)
    {
        if (flag)
        {
            if (len!=0)
                printArray(output, len+1);

            for (int k = i; k < m; k++)
            {
                if (len==0)
                {
                    output[len] = ArrA [k];
                    getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len, !flag);
                }
                else
                {
                    if (ArrA [k] > output[len])
                    {
                        output[len+1] = ArrA [k];
                        getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len+1, !flag);
                    }
                }
            }
        }
        else
        {
            for (int l = j; l < n; l++)
            {
                if (ArrB[l] > output[len])
                {
                    output[len+1] = ArrB[l];
                    getSortedArr(ArrA, ArrB, output, i, l+1, m, n, len+1, !flag);
                }
            }
        }
    }

    public static void generate(int ArrA [], int ArrB[], int m, int n)
    {
        int output[]=new int[m+n];
        getSortedArr(ArrA, ArrB, output, 0, 0, m, n, 0, true);
    }
    
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    
    public static void main(String [] args)
    {
        int ArrA [] = {9, 12, 66};
        int ArrB[] = {10, 15, 25};
        int n = ArrA.length;
        int m = ArrB.length;
        generate(ArrA, ArrB, n, m);
    }
}
9 10
9 10 12 15
9 10 12 25
9 15
9 25
12 15
12 25

जटिलता विश्लेषण

समय जटिलता

O (n1 ^ 2 + n2 ^ 2) जहां "एन 1" और "एन 2" ArrA और ArrB की लंबाई हैं। जब तत्व बारी-बारी से होते हैं, तो वह ArrA [0] <ArrB [0] <ArrA [1] <ArrB [1] ... इस मामले में, हमारे पास कुल n1 ^ 2 + n2 ^ 2 सबसेट हो सकते हैं। इस प्रकार एक बहुपद समय जटिलता।

अंतरिक्ष जटिलता

O (n1 + n2) जहां "एन 1" और "एन 2" ArrA और ArrB की लंबाई हैं। स्पेस आउटपुट सरणी द्वारा लिया गया है और चूंकि आकार n1 + n2 है। अंतरिक्ष की जटिलता रैखिक है।