Gegeben sind eine linke, eine rechte und eine Nebenspur, wie in der folgenden Abbildung gezeigt. In der linken Spur sind N Lastwagen von Wert 1 bis N angeordnet. Wir können N Lastwagen direkt auf das rechte Gleis bewegen, aber es kann mehr Möglichkeiten geben, die Lastwagen unter Verwendung des Stichgleises auf das rechte Gleis zu bewegen. Wir können jeden LKW auf ein Spurgleis und dann auf das richtige Gleis bewegen. Die Aufgabe besteht darin, alle möglichen Permutationsreihenfolgen auszudrucken, in denen alle N Lastwagen von der linken Spur auf die rechte Spur bewegt werden können.
Hinweis: Sobald ein LKW vom linken LKW auf das rechte Gleis/Sporngleis bewegt wurde, kann es nicht mehr auf das linke Gleis bewegt werden.

Beispiele:

Eingabe: N = 2
Ausgabe:
1 2
2 1
Erläuterung:
Für die erste Permutation:
left[] = {1, 2} right[] = {}, and spur[] = {}

Der Truck mit dem Wert 2 bewegte sich auf das rechte Gleis, dann
left[] = {1} right[] = {2} und spur[] = {}

Bewegen Sie sich nun mit dem Wert 1 zum rechten Gleis, dann
left[] = {} right[] = {1, 2} , and spur[] = {}



Für die zweite Permutation:
left[] = {1, 2} right[] = {} und spur[] = {}

Der Truck mit dem Wert 2 bewegt sich auf die Spornspur, dann
left[] = {1} right[] = {}, and spur[] = {2}

Der Truck mit dem Wert 1 bewegt sich auf das rechte Gleis, dann
left[] = {} right[] = {1} und spur[] = {2}

Der Truck mit dem Wert 2 in der Spornspur bewegt sich auf die rechte Spur, dann
left[] = {} right[] = {2, 1} , and spur[] = {}

Eingang: N = 3
Ausgang:
1 2 3
2 1 3
3 2 1
3 1 2
2 3 1

Ansatz: Dieses Problem ist eine Variation von Tower Of Hanoi und kann mit Recursion gelöst werden . Nachfolgend sind die folgenden Fälle aufgeführt:

  • Fall 1: Wir können den Lastwagen von der linken Spur auf die Stichspur bewegen und rekursiv nach den verbleibenden Lastwagen auf der linken Spur und den Stichspuren suchen.
  • Fall 2: Wir können den Lastwagen von der Nebenspur auf die rechte Spur bewegen und nach den verbleibenden Lastwagen der linken Spur und der Nebenspur suchen.

Unten sind die Schritte:

  1. Bei jedem Schritt können wir entweder den LKW vom linken Gleis auf das Nebengleis oder vom Nebengleis auf das rechte Gleis bewegen.
  2. Bewege einen Lastwagen vom linken Gleis zum Nebengleis und rufe rekursiv nach verbleibenden Lastwagen auf dem linken und dem Nebengleis.
  3. Wenn bei jedem rekursiven Aufruf das Eingabegleis leer ist, verschieben Sie jeden Lastwagen auf dem Stichgleis auf das rechte Gleis und geben Sie die aktuelle Permutation auf dem rechten Gleis aus

    Unten ist die Implementierung des obigen Ansatzes:




    // C++ program for the above approach
    #include "bits/stdc++.h"
    using namespace std;
      
    // Helper function to print all the
    // possible permutation
    void printPermute(vector<int>&input,
                      vector<int>&spur,
                      vector<int>&output)
    {
      
        // If at any recursive call input
        // array is empty, then we got our
        // one of the permutation
        if(input.empty())
        {
              
            // Print the right track trucks
            for(auto &it : output) {
                cout << it << ' ';
            }
              
            // Print the spur track trucks
            for(auto &it : spur) {
                cout << it << ' ';
            }
              
            cout << endl;
        }
        else
        {
            int temp;
              
            // Pop the element from input
            // track and move it to spur
            temp=input.back();
            input.pop_back();
              
            // Case 1
            // Push the popped truck from
            // input to spur track
            spur.push_back(temp);
              
            // Recursive call for remaining
            // trucks on input, spur and
            // output track
            printPermute(input,spur,output);
              
            // remove the top truck from spur
            // track and push it in input for
            // Case 2 iteration
            spur.pop_back();
            input.push_back(temp);
              
            // Case 2
            if(!spur.empty()) {
                  
                // Remove the truck from the spur
                // track and move it to the 
                // output track
                temp=spur.back();
                spur.pop_back();
                output.push_back(temp);
                  
                // Recursive call for remaining
                // truck on input, spur and
                // output track
                printPermute(input,spur,output);
                  
                // Remove the top truck from the
                // output track and move it to
                // the spur track for the next
                // iteration
                output.pop_back();
                spur.push_back(temp);
            }
        }
    }
      
    // Function to print all the possible
    // permutation of trucks
    void possiblePermute(int n)
    {
        // Array for left, spur and right track
        vector<int>spur;
        vector<int>output;
        vector<int>input;
          
        // Insert all truck value 1 to N
        for(int i = 1; i <= n; i++) {
            input.push_back(i);
        }
          
        // Helper function to find
        // possible arrangement
        printPermute(input, spur, output);
    }
      
    // Driver Code
    int main()
    {
        // Input number of truck
        int N = 4;
          
        // Function Call
        possiblePermute(N);
    }
    Ausgabe:
    1 2 3 4
2 1 3 4
3 2 1 4
4 3 2 1
3 1 2 4
2 3 1 4
4 2 3 1
4 3 1 2
2 4 3 1
4 1 2 3
2 4 1 3
3 2 4 1
3 4 1 2
2 3 4 1

    Achtung Leser! Hören Sie jetzt nicht auf zu lernen. Holen Sie sich mit dem Essential Maths for CP-Kurs alle wichtigen mathematischen Konzepte für wettbewerbsfähiges Programmieren zu einem schülerfreundlichen Preis. Um Ihre Vorbereitung vom Erlernen einer Sprache auf DS Algo und vieles mehr abzuschließen, lesen Sie bitte Vollständiger Vorbereitungskurs für ein Vorstellungsgespräch .