El algoritmo de Alexander Bogomolny se usa para permutar los primeros N números naturales.
Dado el valor de N, tenemos que generar todas las permutaciones de números del 1 al N.
Ejemplos:
Input : 2 Output : 1 2 2 1 Input : 3 Output : 1 2 3 1 3 2 2 1 3 3 1 2 2 3 1 3 2 1
La idea es mantener una array para almacenar la permutación actual. Se utiliza una variable de nivel entero estático para definir estas permutaciones.
- Inicializa el valor del nivel actual y permuta los valores restantes a los niveles superiores.
- A medida que la acción de asignación de los valores alcanza el nivel más alto, imprime la permutación obtenida.
- Este enfoque se implementa recursivamente para obtener todas las permutaciones posibles.
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>
Producción:
1 2 3 1 3 2 2 1 3 3 1 2 2 3 1 3 2 1
Este artículo es una contribución de Vineet Joshi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA