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