Alexander Bogomolny的无序排列算法-yiteyi-C++库

Alexander Bogomolny算法用于排列前N个自然数。给定N的值，我们必须输出从1到N的所有数字排列。 例如：

null

Input : 2Output : 1 2         2 1Input : 3Output : 1 2 3         1 3 2         2 1 3         3 1 2         2 3 1         3 2 1

其想法是维护一个数组来存储当前的排列。静态整数级别变量用于定义这些排列。

它初始化当前级别的值，并将剩余值置换到更高级别。
当值的赋值操作达到最高级别时，它会打印获得的排列。
这种方法是递归实现的，以获得所有可能的排列。

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

C++

                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         void                                     solve(vector<                                     int                                     > &v,                                     int                                     n,string &s,vector<vector<                                     int                                     >> &vv)                       
                         {                       
                                                 if                                     (v.size()==n)                       
                                                 {                       
                                                 vv.push_back(v);                       
                                                 return                                     ;                       
                                                 }                       
                                                 for                                     (                                     int                                     i=0;i<n;i++)                       
                                                 {                       
                                                 if                                     (s[i]!=                                     '1'                                     )                       
                                                 {                       
                                                 s[i]=                                     '1'                                     ;                       
                                                 v.push_back(i+1);                       
                                                 solve(v,n,s,vv);                       
                                                 s[i]=                                     '0'                                     ;                       
                                                 v.pop_back();                       
                                                 }                       
                                                 }                       
                                   
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 int                                     n=3                       
                                                 vector<                                     int                                     > v;                       
                                                 vector<vector<                                     int                                     >> vv;                       
                                                 string s;                       
                                                 for                                     (                                     int                                     i=0;i<n;i++) s+=                                     '0'                                     ;                       
                                                 solve(v,n,s,vv);                       
                                                 for                                     (                                     int                                     i=0;i<vv.size();i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j=0;j<vv[i].size();j++)                       
                                                 {                       
                                                 cout<<vv[i][j]<<                                     " "                                     ;                       
                                                 }                       
                                                 cout<<endl;                       
                                                 }                       
                         }                       

JAVA

                         // Java program to implement                       
                         // Alexander Bogomolny UnOrdered                       
                         // Permutation Algorithm                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                         static                                     int                                     level = -                                     1                                     ;                       
           
                         // A function to print                       
                         // the permutation.                       
                         static                                     void                                     print(                                     int                                     perm[],                                     int                                     N)                       
                         {                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < N; i++)                       
                                                 System.out.print(                                     " "                                     + perm[i]);                       
                                                 System.out.println();                       
                         }                       
           
                         // A function implementing                       
                         // Alexander Bogomolny algorithm.                       
                         static                                     void                                     AlexanderBogomolyn(                                     int                                     perm[],                       
                                                 int                                     N,                                     int                                     k)                       
                         {                       
           
                                                 // Assign level to                       
                                                 // zero at start.                       
                                                 level = level +                                     1                                     ;                       
                                                 perm[k] = level;                       
           
                                                 if                                     (level == N)                       
                                                 print(perm, N);                       
                                                 else                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < N; i++)                       
           
                                                 // Assign values                       
                                                 // to the array                       
                                                 // if it is zero.                       
                                                 if                                     (perm[i] ==                                     0                                     )                       
                                                 AlexanderBogomolyn(perm, N, i);                       
           
                                                 // Decrement the level                       
                                                 // after all possible                       
                                                 // permutation after                       
                                                 // that level.                       
                                                 level = level -                                     1                                     ;                       
                                   
                                                 perm[k] =                                     0                                     ;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     i, N =                                     3                                     ;                       
                                                 int                                     perm[] =                                     new                                     int                                     [N];                       
                                                 AlexanderBogomolyn(perm, N,                                     0                                     );                       
                         }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

Python3

                         # Python3 program to implement Alexander                       
                         # Bogomolny’s UnOrdered Permutation Algorithm                       
           
                         # A function to print permutation.                       
                         def                                     printn(perm, N):                       
                                                 for                                     i                                     in                                     range                                     (N):                       
                                                 print                                     (                                     " "                                     ,perm[i], sep                                     =                                     "                                     ", end = "                                     ")                       
                                                 print                                     ()                       
                                   
                         # A function implementing Alexander Bogomolny                       
                         # algorithm.                       
                         level                                     =                                     [                                     -                                     1                                     ]                       
                         def                                     AlexanderBogomolyn(perm, N, k):                       
           
                                                 # Assign level to zero at start.                       
                                                 level[                                     0                                     ]                                     =                                     level[                                     0                                     ]                                     +                                     1                       
                                                 perm[k]                                     =                                     level[                                     0                                     ]                       
                                                 if                                     (level[                                     0                                     ]                                     =                                     =                                     N):                       
                                                 printn(perm, N)                       
                                                 else                                     :                       
                                                 for                                     i                                     in                                     range                                     (N):                       
                                   
                                                 # Assign values to the array                       
                                                 # if it is zero.                       
                                                 if                                     (perm[i]                                     =                                     =                                     0                                     ):                       
                                                 AlexanderBogomolyn(perm, N, i)                       
                                   
                                                 # Decrement the level after all possible                       
                                                 # permutation after that level.                       
                                                 level[                                     0                                     ]                                     =                                     level[                                     0                                     ]                                     -                                     1                       
                                   
                                                 perm[k]                                     =                                     0                       
                                                 return                       
           
                         # Driver code                       
                         N                                     =                                     3                       
                         perm                                     =                                     [                                     0                                     ]                                     *                                     N                       
                         AlexanderBogomolyn(perm, N,                                     0                                     )                       
           
                         # This code is contributed by SHUBHAMSINGH10                       

C#

                         // C# program to implement                       
                         // Alexander Bogomolny UnOrdered                       
                         // Permutation Algorithm                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         static                                     int                                     level = -1;                       
           
                         // A function to print                       
                         // the permutation.                       
                         static                                     void                                     print(                                     int                                     []perm,                       
                                                 int                                     N)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; i < N; i++)                       
                                                 Console.Write(                                     " "                                     + perm[i]);                       
                                                 Console.WriteLine();                       
                         }                       
           
                         // A function implementing                       
                         // Alexander Bogomolny algorithm.                       
                         static                                     void                                     AlexanderBogomolyn(                                     int                                     []perm,                       
                                                 int                                     N,                                     int                                     k)                       
                         {                       
           
                                                 // Assign level to                       
                                                 // zero at start.                       
                                                 level = level + 1;                       
                                                 perm[k] = level;                       
           
                                                 if                                     (level == N)                       
                                                 print(perm, N);                       
                                                 else                       
                                                 for                                     (                                     int                                     i = 0; i < N; i++)                       
           
                                                 // Assign values                       
                                                 // to the array                       
                                                 // if it is zero.                       
                                                 if                                     (perm[i] == 0)                       
                                                 AlexanderBogomolyn(perm, N, i);                       
           
                                                 // Decrement the level                       
                                                 // after all possible                       
                                                 // permutation after                       
                                                 // that level.                       
                                                 level = level - 1;                       
                                   
                                                 perm[k] = 0;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main ()                       
                         {                       
                                                 int                                     N = 3;                       
                                                 int                                     []perm =                                     new                                     int                                     [N];                       
                                                 AlexanderBogomolyn(perm, N, 0);                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by anuj_67.                       

Javascript

                         <script>                       
           
                         // Javascript program to implement                       
                         // Alexander Bogomolny UnOrdered                       
                         // Permutation Algorithm                       
           
                         let level = -1;                       
                                   
                         // A function to print                       
                         // the permutation.                       
                         function                                     print(perm, N)                       
                         {                       
                                                 for                                     (let i = 0; i < N; i++)                       
                                                 document.write(                                     " "                                     + perm[i]);                       
                                                 document.write(                                     "<br/>"                                     );                       
                         }                       
                                   
                         // A function implementing                       
                         // Alexander Bogomolny algorithm.                       
                         function                                     AlexanderBogomolyn(perm, N, k)                       
                         {                       
                                   
                                                 // Assign level to                       
                                                 // zero at start.                       
                                                 level = level + 1;                       
                                                 perm[k] = level;                       
                                   
                                                 if                                     (level == N)                       
                                                 print(perm, N);                       
                                                 else                       
                                                 for                                     (let i = 0; i < N; i++)                       
                                   
                                                 // Assign values                       
                                                 // to the array                       
                                                 // if it is zero.                       
                                                 if                                     (perm[i] == 0)                       
                                                 AlexanderBogomolny(perm, N, i);                       
                                   
                                                 // Decrement the level                       
                                                 // after all possible                       
                                                 // permutation after                       
                                                 // that level.                       
                                                 level = level - 1;                       
                                   
                                                 perm[k] = 0;                       
                         }                       
                         // driver program                       
           
                                                 let i, N = 3;                       
                                                 let perm = Array.from({length: N}, (_, i) => 0);                       
                                                 AlexanderBogomolny(perm, N, 0);                       
                                   
                         </script>                       

输出：

1 2 31 3 22 1 33 1 22 3 13 2 1

本文由 维尼特·乔希 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章