给定一个左、右和一个支线Rails，如下图所示。从值 1 到 N 有 N 辆卡车排列在左边的Rails上。我们可以将 N 辆卡车直接移动到正确的Rails上，但是使用支线Rails将卡车移动到正确的Rails上的可能性更大。我们可以将任何卡车移动到支线，然后将其移动到正确的Rails上。任务是打印所有可能的排列顺序，其中所有 N 辆卡车可以从左Rails移动到右Rails。注意：一旦卡车从左卡车移动到右/支线Rails，它就不能移动到左边再次跟踪。

例子：

输入：N = 2输出：1 22 1说明：对于第一个排列：left[] = {1, 2} right[] = {}，spur[] = {}

值为 2 的卡车移动到正确的Rails，然后left[] = {1} right[] = {2}，spur[] = {}

现在以值 1 移动到正确的Rails，然后left[] = {} right[] = {1, 2}，spur[] = {}

对于第二个排列：left[] = {1, 2} right[] = {}，spur[] = {}

值为 2 的卡车移动到支线Rails，然后左[] = {1} 右[] = {}，支线[] = {2}

值为1的卡车移动到正确的Rails，然后left[] = {} right[] = {1}，spur[] = {2}

支线Rails中值为 2 的卡车移动到右侧Rails，然后left[] = {} right[] = {2, 1}，spur[] = {}

输入：N = 3输出：1 2 32 1 33 2 13 1 22 3 1

方法：这个问题是 河内塔的变体，可以使用 递归。以下是以下几种情况：

• 案例 1：我们可以将卡车从左侧Rails移动到支线Rails，并递归检查左侧和支线Rails上剩余的卡车。
• 案例 2：我们可以将卡车从支线Rails移动到右线Rails，并检查左支线和支线Rails的剩余卡车。

以下是步骤：

1. 在每个步骤中，我们都可以将卡车从左Rails移动到支线Rails或从支线Rails移动到右Rails。
2. 将一辆卡车从左侧Rails移动到支线Rails，并递归调用左侧和支线Rails上的剩余卡车。
3. 在任何递归调用中，如果输入Rails为空，则将支线Rails上的每辆卡车移动到正确Rails，并在正确Rails上打印当前排列

   下面是上述方法的实现：

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

   输出：

   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