Posibles permutaciones en una vía férrea

Dada una pista izquierda, derecha y una recta como se muestra en la figura a continuación. Hay N camiones de valor 1 a N dispuestos en la vía izquierda. Podemos mover directamente N camiones a la vía correcta pero puede haber más posibilidades de mover los camiones a la vía correcta utilizando la vía secundaria. Podemos mover cualquier camión a la vía secundaria y luego moverlo a la vía correcta. La tarea es imprimir todo el orden de permutación posible en el que todos los camiones N se pueden mover de la vía izquierda a la vía derecha.
Nota: Una vez que un camión se mueve del camión izquierdo a la vía derecha/espuela, no se puede volver a mover a la vía izquierda.

Ejemplos:

Entrada: N = 2
Salida:
1 2
2 1
Explicación:
Para la primera permutación:
izquierda[] = {1, 2} derecha[] = {}, y spur[] = {}

El camión con valor 2 se movió a la vía derecha, luego a la
izquierda[] = {1} a la derecha[] = {2}, y desvío[] = {}

Ahora moviéndonos con el valor 1 hacia la pista derecha, luego
left[] = {} right[] = {1, 2} , y spur[] = {}

Para la segunda permutación:
left[] = {1, 2} right[] = {}, y spur[] = {}

El camión con valor 2 se mueve a la vía secundaria, luego
izquierda[] = {1} derecha[] = {}, y ramal[] = {2}

El camión con valor 1 se mueve a la vía derecha, luego
izquierda[] = {} derecha[] = {1}, y desvío[] = {2}

El camión con el valor 2 en la vía secundaria se mueve a la vía derecha, luego
izquierda[] = {} derecha[] = {2, 1} , y desvío[] = {}

Entrada: N = 3
Salida:
1 2 3
2 1 3
3 2 1
3 1 2
2 3 1

Enfoque: Este problema es una variación de Tower Of Hanoi y se puede resolver usando Recursion . A continuación se presentan los siguientes casos:

• Caso 1: Podemos mover el camión de la vía izquierda a la vía secundaria y verificar recursivamente los camiones restantes en las vías izquierda y secundaria.
• Caso 2: Podemos mover el camión de la vía de espuela a la vía de la derecha y verificar los camiones restantes de las vías de la izquierda y de la vía de derivación.

A continuación se muestran los pasos:

1. En cada paso, podemos mover cualquiera de los camiones de la vía izquierda a la vía de derivación o de la vía de derivación a la vía derecha.
2. Mueva un camión de la vía izquierda a la vía secundaria y llame recursivamente a los camiones restantes en la vía izquierda y la vía secundaria.
3. En cualquier llamada recursiva, si la vía de entrada está vacía, mueva todos los camiones de la vía secundaria a la vía derecha e imprima la permutación actual en la vía derecha.

A continuación se muestra la implementación del enfoque anterior:

// 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); }

Producción:

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