גענעראַטע אַלע מעגלעך סאָרטירט ערייז פֿון אָלטערנאַטיוו עלעמענטן פון צוויי געגעבן סאָרטירט ערייז


שוועריקייט לעוועל מיטל
אָפט געבעטן אין דירעקטי קאַראַט פּייַפּאַל טוויליאָ יאַנדעקס
מענגע רעקורסיאָן

די פּראָבלעם "גענעראַטע אַלע מעגלעך סאָרטירט ערייז פון אָלטערנאַטיוו יסודות פון צוויי געגעבן סאָרטירט ערייז" שטאַטן אַז רעכן איר האָבן צוויי סאָרטעד ערייז. די פּראָבלעם ויסזאָגונג פרעגט צו געפֿינען אַלע די מעגלעך סאָרטירט ערייז, אַזאַ ווי די נומער זאָל זיין עריינדזשד אַלטערנאַטיוועלי פֿון די צוויי פאַרשידענע ערייז.

בייַשפּיל

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. אַריבער די מענגע ArrA און קאָנטראָלירן די פאלגענדע
        1. אויב די לענג פון די רעזולטאַט מענגע איז 0, נאָכמאַכן די קראַנט עלעמענט צו דער רעזולטאַט מענגע און רעקורסיוועלי רופן די פונקציע.
    2. אַנדערש אויב די קראַנט מענגע עלעמענט איז גרעסער ווי די פֿריִערדיקע רעזולטאַט מענגע עלעמענט, דעמאָלט קאָפּיע די עלעמענט פֿון ArrA אין די רעזולטאַט מענגע און רעקורסיוועלי רופן די פֿונקציע.
  3. אַנדערש אויב באָאָלקאַנדישאַן איז פאַלש, דאַן דורך די אַררב און קאָנטראָלירן צי די קראַנט עלעמענט פון אַררב איז גרעסער ווי די קראַנט עלעמענט פון דער רעזולטאַט מענגע
      1. אויב אמת, קאָפּיע די עלעמענט פֿון אַררב צו די רעזולטאַט מענגע און רעקורסיוועלי רופן די פֿונקציע.

דערקלערונג

דער פּראָבלעם "גענעראַטע אַלע מעגלעך סאָרטירט ערייז פון אָלטערנאַטיוו עלעמענטן פון צוויי געגעבן סאָרטירט ערייז" קענען זיין סאַלווד אין די פאלגענדע שטייגער. דאָ מיר באַקומען צוויי סאָרטעד ערייז ArrA און אַררב. ביידע די ערייז זענען אין סאָרטירט סדר. מיר דאַרפֿן צו געפֿינען אַלע מעגלעך ערייז וואָס קענען זיין קאַנסטראַקטאַד אין אַ סאָרטעד שטייגער. עס איז אויך אן אנדער צושטאַנד אַז יעדער אָלטערנאַטיוו עלעמענט אין דער רעזולטאַט זאָל זיין פֿון פאַרשידענע ערייז.

מיר וועלן רעקורסיוועלי רופן דעם פֿונקציע צו געפֿינען אַלע די מעגלעך רעזולטאַט ערייז. דערנאָך מיר האַלטן אַ באָאָלעאַן בייַטעוודיק וואָס האלט שפּור פון עלעמענטן צו זיין פּיקט. דאָס איז אָדער דער עלעמענט איז פֿון די קראַנט ArrA אָדער ArrB. אויב די באָאָלעאַן בייַטעוודיק איז אמת, מיר סעלעקטירן אַן עלעמענט פֿון דער ערשטער מענגע ArrA. אַנדערש אויב די באָאָלעאַן בייַטעוודיק איז פאַלש, מיר סעלעקטירן דעם עלעמענט פון די רגע מענגע ArrB. אויב די באָאָלעאַן בייַטעוודיק איז אמת, מיר וועלן קאָנטראָלירן אויב די לענג פון די מענגע איז נישט גלייַך צו 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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (נ 1 ^ 2 + נ 2 ^ 2) ווו “N1” און “N2” זענען די לענג פון ArrA און ArrB. ווען די עלעמענטן זענען אָלטערנאַטיוו, דאָס איז אַרראַ [0] <אַררב [0] <אַרראַ [1] <אַררב [1] ... אין דעם פאַל, מיר קענען האָבן אַ גאַנץ פון נ 1 ^ 2 + נ 2 ^ 2 מעגלעך סובסעץ. אזוי אַ פּאַלינאָומיאַל צייט קאַמפּלעקסיטי.

ספעיס קאַמפּלעקסיטי

אָ (n1 + n2) ווו “N1” און “N2” זענען די לענג פון ArrA און ArrB. אָרט איז גענומען דורך די רעזולטאַט מענגע און זינט די גרייס איז N1 + N2. די פּלאַץ קאַמפּלעקסיטי איז לינעאַר.