ٻن ممڪن ترتيب وارين شين جي متبادل عنصرن مان تمام ممڪن ترتيب واريون ٺاھيون ٺاھيو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ سڌو خرات ٿي PayPal Twilio ياندڪس
ڪيريو ٻيھر

مسئلو “ٻن ڏنل ترتيب وارين بندن جي متبادل عنصرن مان هر ممڪن ترتيب وار بنديون ٺاھيو” بيان ڪري ٿو ته سمجھو ته توهان وٽ ٻه مختلف ترتيبون آهن مسئلو بيان ڪندڙ سڀني ممڪن ترتيب وارين بندن کي ڳولڻ لاءِ پڇي ٿو ، اهڙي نمبر کي ٻن ڏنل مختلف عددن کان متبادل طور ترتيب ڏنو وڃي.

مثال

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

وضاحت

سڀ متبادل نمبر مختلف arrays مان آھن ۽ ترتيب ڏنل آھن.

ٻن ممڪن ترتيب وارين شين جي متبادل عنصرن مان تمام ممڪن ترتيب واريون ٺاھيون ٺاھيو

 

الورورٿم

  1. ھڪڙي ٻاھرائي ٻا array جو سائيز ڏيکاريو ن + ن (ٻنهي حڪمن جي ڪل ڊيگهه)
  2. چيڪ ڪريو بولڊ ڪنڊيشن سچ آهي،
    1. پوءِ چڪاس ڪريو ته ٻاھرين صف جي ڊيگھ 0 جي برابر نه آھي ، وري ٻاھرائي ٻاھرين قطار کي پرنٽ ڪريو.
      1. ترتيب کي ترتيب ڏيو آر اي ۽ هيٺيان چيڪ ڪريو
        1. جيڪڏهن ٻاھرين صف جي ڊيگهه 0 آھي ته موجوده عنصر کي ٻاھرين صف ۾ ڪاپي ڪريو پوءِ وقتي طور تي ڪم کي سڏ ڪريو.
    2. ٻي صورت ۾ جيڪڏهن موجوده صف جو عنصر پوئين آئوٽٽ آرٽ عنصر کان وڌيڪ آهي ، پوء عنصر کي نقل ڪريو آر اي ٻاھرين صف ۾ ۽ فعل کي تفاوت سان سڏ ڪندا آھن.
  3. ٻئي صورت ۾ جيڪڏهن بول ڪنڊيشن غلط آهي ، ان کان پوءِ آر بي بي ۽ اهو چيڪ ڪيو ته موجوده عنصر جو آر بي بي موجوده آئوٽ جي عنصر کان وڏو آهي
      1. جيڪڏھن صحيح آھي ته پوءِ عنصر کي نقل ڪريو آر بي بي ٻاھرين صف ۾ ۽ عامل طور تي فنڪشن کي سڏ ڪندا آھن.

وضاحت

مسئلو ”ٻن ڏنل ترتيب وارين بندن جي متبادل عنصرن مان هر ممڪن ترتيب واري ترتيب ٺاھيو” هيٺين طريقي سان حل ٿي سگهي ٿو. هتي اسان کي ٻن ترتيب وارين ترتيب ڏني وئي آهي آر اي ۽ آر بي بي. ٻنهي گرفتارن کي ترتيب وار ترتيب سان ڏنو ويو آهي. تنهن ڪري ، اسان کي سڀني ممڪن ڳولڻ جي ضرورت آهي قطارون جيڪو ٺاهيل طريقي سان تعمير ڪري سگهجي ٿو. هتي پڻ هڪ ٻي شرط آهي ته محصول ۾ هر متبادل عنصر مختلف وهمن کان اچڻ گهرجي.

اسان ٻهراڙي جي سموري ممڪن طريقي سان ڳولڻ لاءِ وري اهو ڪم پاڻ دهرائي ڇڏينداسين. ان کان پوءِ اسان هڪ بولين متغير رکون ٿا جيڪو عناصر جي چونڊ ڪرڻ لاءِ رڪاوٽ رکي ٿو. اهو عنصر آهي موجوده ايرا يا اي آر بي کان. جيڪڏهن بولانن جو متغير صحيح آهي ، ته پوءِ اسان پهرين قطار ArrA مان هڪ عنصر چونڊيو. ٻي صورت ۾ ، اگر بولن جو متغير غلط آهي ، ته پوءِ اسين عنصر کي ٻي صف ArrB مان چونڊيندا آهيون. جيڪڏهن بولين جي متغير صحيح آهي ، اسان اهو جانچڻ وارا آهيون ته صف جي ڊيگهه 0 جي برابر يا 0 کان وڌيڪ برابر ناهي ، هر دفعي اسان ٻاٽ واري صف کي پرنٽ ڪرڻ وارا آهيون.

جيڪڏهن اسان بولين جي حالت صحيح آهي ته اسان صف ايرا کي ڪراس ڪرڻ وارا آهيون. ان کان پوء موجوده صف واري عنصر کي آئوٽٽ لسٽ ۾ نقل ڪريو. پوءِ اسان ورجائي ورجائي هن فنڪشن کي سڀني ضروري دليلن ڏانهن هن ڏانهن وڌو. جيڪڏهن بولين واري حالت غلط آهي. ان کان پوء اسان اسان کي پنهنجي آئوٽ آرٽ تان ڪاپي ۽ تازه ڪاري لاءِ استعمال ڪندا آهيون. ۽ هر وقت جڏهن آئوٽ پيس جي ڊيگهه 0 آهي ، ته صف پرنٽ ڪريو.

ڪوڊ

سي ++ ڪوڊ ھر ممڪن ترتيب سان ٺاھڻ لاءِ

#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) جتي “ن 1” ۽ “ن 2” اي آر اي ۽ آر آر بي جي ڊيگهه آهي. جڏهن عنصر متبادل ٿي رهيا آهن ، اهو آر آر اي آهي [0] <آر آر بي [0] <آر آر اي [1] <ArrB [1]… انهي صورت ۾ ، اسان مجموعي طور تي اين 1 ^ 2 + n2 ^ 2 ممڪن سبسڪيٽ ڪري سگھون ٿا. اھڙي طرح پوليوملائل وقت جي پيچيدگي.

خلائي پيچيدگي

اي (ن 1 + ن 2) جتي “ن 1” ۽ “ن 2” اي آر اي ۽ آر آر بي جي ڊيگهه آهي. ٻاھر ٻاھرين ترتيب جي طرفان ورتو ويو آھي ۽ جتان سائز n1 + n2 آھي. خلائي پيچيدگي لڪير آھي.