Algoritmo de permutación desordenada de Alexander Bogomolny

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. 
 

  1. Inicializa el valor del nivel actual y permuta los valores restantes a los niveles superiores.
  2. A medida que la acción de asignación de los valores alcanza el nivel más alto, imprime la permutación obtenida.
  3. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *