Nos dan una secuencia de números del 1 al n. Cada permutación en la secuencia que necesitamos generar debe diferir de la permutación anterior intercambiando solo dos elementos adyacentes de la secuencia.
Ejemplos:
Input : n = 3
Output : 123 132 312 321 231 213
Input : n = 4
Output : 1234 1243 1423 4123 4132
1432 1342 1324 3124 3142 3412 4312
4321 3421 3241 3214 2314 2341 2431
4231 4213 2413 2143 2134
Una solución simple para usar permutaciones de n-1 elementos para generar permutaciones de n elementos.
Por ejemplo, veamos cómo generar permutaciones de tamaño 3 usando permutaciones de tamaño 2.
Las permutaciones de dos elementos son 1 2 y 2 1. Las
permutaciones de tres elementos se pueden obtener insertando 3 en diferentes posiciones en todas las permutaciones de tamaño 2.
Insertar 3 en diferentes posiciones de 1 2 conduce a 1 2 3 , 1 3 2 y 3 1 2.
Insertar 3 en diferentes posiciones de 2 1 conduce a 2 1 3 , 2 3 1 y 3 2 1.
Para generar permutaciones de tamaño cuatro, consideramos las seis permutaciones anteriores de tamaño tres e insertamos 4 en diferentes posiciones en cada permutación.
Algoritmo de Johnson y Trotter El algoritmo
de Johnson y Trotter no requiere almacenar todas las permutaciones de tamaño n-1 y no requiere pasar por todas las permutaciones más cortas. En su lugar, realiza un seguimiento de la dirección de cada elemento de la permutación.
- Averigüe el entero móvil más grande en una secuencia particular. Se dice que un entero dirigido es móvil si es mayor que su vecino inmediato en la dirección en la que está mirando .
- Cambie este entero móvil y el entero adyacente al que apunta su dirección.
- Cambia la dirección de todos los elementos cuyo valor es mayor que el valor entero móvil.
- Repita el paso 1 hasta que no quede ningún entero móvil en la secuencia.
Let us see how to generate permutations of size four. We first print 1 2 3 4. Initially all directions are right to left. <1 <2 <3 <4 All mobile numbers are 2, 3 and 4. The largest mobile number is 4. We swap 3 and 4. Since 4 is largest, we don't change any direction. <1 <2 <4 <3 4 is the largest mobile. We swap it with 2. <1 <4 <2 <3 4 is the largest mobile. We swap it with 1. <4 <1 <2 <3 3 is largest mobile. We swap it with 2 and change directions of greater elements. 4> <1 <3 <2 4 is largest mobile. We swap it with 3. <4 1> <2 <3 We proceed this way and print all permutations.
A continuación se muestra la implementación del enfoque.
C++
// CPP program to print all permutations using
// Johnson and Trotter algorithm.
#include <bits/stdc++.h>
using namespace std;
bool LEFT_TO_RIGHT = true;
bool RIGHT_TO_LEFT = false;
// Utility functions for finding the
// position of largest mobile integer in a[].
int searchArr(int a[], int n, int mobile)
{
for (int i = 0; i < n; i++)
if (a[i] == mobile)
return i + 1;
}
// To carry out step 1 of the algorithm i.e.
// to find the largest mobile integer.
int getMobile(int a[], bool dir[], int n)
{
int mobile_prev = 0, mobile = 0;
for (int i = 0; i < n; i++)
{
// direction 0 represents RIGHT TO LEFT.
if (dir[a[i]-1] == RIGHT_TO_LEFT && i!=0)
{
if (a[i] > a[i-1] && a[i] > mobile_prev)
{
mobile = a[i];
mobile_prev = mobile;
}
}
// direction 1 represents LEFT TO RIGHT.
if (dir[a[i]-1] == LEFT_TO_RIGHT && i!=n-1)
{
if (a[i] > a[i+1] && a[i] > mobile_prev)
{
mobile = a[i];
mobile_prev = mobile;
}
}
}
if (mobile == 0 && mobile_prev == 0)
return 0;
else
return mobile;
}
// Prints a single permutation
int printOnePerm(int a[], bool dir[], int n)
{
int mobile = getMobile(a, dir, n);
int pos = searchArr(a, n, mobile);
// swapping the elements according to the
// direction i.e. dir[].
if (dir[a[pos - 1] - 1] == RIGHT_TO_LEFT)
swap(a[pos-1], a[pos-2]);
else if (dir[a[pos - 1] - 1] == LEFT_TO_RIGHT)
swap(a[pos], a[pos-1]);
// changing the directions for elements
// greater than largest mobile integer.
for (int i = 0; i < n; i++)
{
if (a[i] > mobile)
{
if (dir[a[i] - 1] == LEFT_TO_RIGHT)
dir[a[i] - 1] = RIGHT_TO_LEFT;
else if (dir[a[i] - 1] == RIGHT_TO_LEFT)
dir[a[i] - 1] = LEFT_TO_RIGHT;
}
}
for (int i = 0; i < n; i++)
cout << a[i];
cout << " ";
}
// To end the algorithm for efficiency it ends
// at the factorial of n because number of
// permutations possible is just n!.
int fact(int n)
{
int res = 1;
for (int i = 1; i <= n; i++)
res = res * i;
return res;
}
// This function mainly calls printOnePerm()
// one by one to print all permutations.
void printPermutation(int n)
{
// To store current permutation
int a[n];
// To store current directions
bool dir[n];
// storing the elements from 1 to n and
// printing first permutation.
for (int i = 0; i < n; i++)
{
a[i] = i + 1;
cout << a[i];
}
cout << endl;
// initially all directions are set
// to RIGHT TO LEFT i.e. 0.
for (int i = 0; i < n; i++)
dir[i] = RIGHT_TO_LEFT;
// for generating permutations in the order.
for (int i = 1; i < fact(n); i++)
printOnePerm(a, dir, n);
}
// Driver code
int main()
{
int n = 4;
printPermutation(n);
return 0;
}
Java
// Java program to print all
// permutations using Johnson
// and Trotter algorithm.
import java.util.*;
import java.lang.*;
public class GfG{
private final static boolean LEFT_TO_RIGHT = true;
private final static boolean RIGHT_TO_LEFT = false;
// Utility functions for
// finding the position
// of largest mobile
// integer in a[].
public static int searchArr(int a[], int n,
int mobile)
{
for (int i = 0; i < n; i++)
if (a[i] == mobile)
return i + 1;
return 0;
}
// To carry out step 1
// of the algorithm i.e.
// to find the largest
// mobile integer.
public static int getMobile(int a[],
boolean dir[], int n)
{
int mobile_prev = 0, mobile = 0;
for (int i = 0; i < n; i++)
{
// direction 0 represents
// RIGHT TO LEFT.
if (dir[a[i] - 1] == RIGHT_TO_LEFT &&
i != 0)
{
if (a[i] > a[i - 1] &&
a[i] > mobile_prev)
{
mobile = a[i];
mobile_prev = mobile;
}
}
// direction 1 represents
// LEFT TO RIGHT.
if (dir[a[i] - 1] == LEFT_TO_RIGHT &&
i ! =n - 1)
{
if (a[i] > a[i + 1] &&
a[i] > mobile_prev)
{
mobile = a[i];
mobile_prev = mobile;
}
}
}
if (mobile == 0 && mobile_prev == 0)
return 0;
else
return mobile;
}
// Prints a single
// permutation
public static int printOnePerm(int a[], boolean dir[],
int n)
{
int mobile = getMobile(a, dir, n);
int pos = searchArr(a, n, mobile);
// swapping the elements
// according to the
// direction i.e. dir[].
if (dir[a[pos - 1] - 1] == RIGHT_TO_LEFT)
{
int temp = a[pos - 1];
a[pos - 1] = a[pos - 2];
a[pos - 2] = temp;
}
else if (dir[a[pos - 1] - 1] == LEFT_TO_RIGHT)
{
int temp = a[pos];
a[pos] = a[pos - 1];
a[pos - 1] = temp;
}
// changing the directions
// for elements greater
// than largest mobile integer.
for (int i = 0; i < n; i++)
{
if (a[i] > mobile)
{
if (dir[a[i] - 1] == LEFT_TO_RIGHT)
dir[a[i] - 1] = RIGHT_TO_LEFT;
else if (dir[a[i] - 1] == RIGHT_TO_LEFT)
dir[a[i] - 1] = LEFT_TO_RIGHT;
}
}
for (int i = 0; i < n; i++)
System.out.print(a[i]);
System.out.print(" ");
return 0;
}
// To end the algorithm
// for efficiency it ends
// at the factorial of n
// because number of
// permutations possible
// is just n!.
public static int fact(int n)
{
int res = 1;
for (int i = 1; i <= n; i++)
res = res * i;
return res;
}
// This function mainly
// calls printOnePerm()
// one by one to print
// all permutations.
public static void printPermutation(int n)
{
// To store current
// permutation
int[] a = new int[n];
// To store current
// directions
boolean[] dir = new boolean[n];
// storing the elements
// from 1 to n and
// printing first permutation.
for (int i = 0; i < n; i++)
{
a[i] = i + 1;
System.out.print(a[i]);
}
System.out.print("\n");
// initially all directions
// are set to RIGHT TO
// LEFT i.e. 0.
for (int i = 0; i < n; i++)
dir[i] = RIGHT_TO_LEFT;
// for generating permutations
// in the order.
for (int i = 1; i < fact(n); i++)
printOnePerm(a, dir, n);
}
// Driver function
public static void main(String argc[])
{
int n = 4;
printPermutation(n);
}
}
// This code is contributed by Sagar Shukla
C#
// Java program to print all
// permutations using Johnson
// and Trotter algorithm.
using System;
public class GfG{
private static bool LEFT_TO_RIGHT = true;
private static bool RIGHT_TO_LEFT = false;
// Utility functions for
// finding the position
// of largest mobile
// integer in a[].
public static int searchArr(int []a, int n,
int mobile)
{
for (int i = 0; i < n; i++)
if (a[i] == mobile)
return i + 1;
return 0;
}
// To carry out step 1
// of the algorithm i.e.
// to find the largest
// mobile integer.
public static int getMobile(int []a,
bool []dir, int n)
{
int mobile_prev = 0, mobile = 0;
for (int i = 0; i < n; i++)
{
// direction 0 represents
// RIGHT TO LEFT.
if (dir[a[i] - 1] == RIGHT_TO_LEFT &&
i != 0)
{
if (a[i] > a[i - 1] &&
a[i] > mobile_prev)
{
mobile = a[i];
mobile_prev = mobile;
}
}
// direction 1 represents
// LEFT TO RIGHT.
if (dir[a[i] - 1] == LEFT_TO_RIGHT && i!=n - 1)
{
if (a[i] > a[i + 1] &&
a[i] > mobile_prev)
{
mobile = a[i];
mobile_prev = mobile;
}
}
}
if (mobile == 0 && mobile_prev == 0)
return 0;
else
return mobile;
}
// Prints a single
// permutation
public static int printOnePerm(int []a, bool []dir,
int n)
{
int mobile = getMobile(a, dir, n);
int pos = searchArr(a, n, mobile);
// swapping the elements
// according to the
// direction i.e. dir[].
if (dir[a[pos - 1] - 1] == RIGHT_TO_LEFT)
{
int temp = a[pos - 1];
a[pos - 1] = a[pos - 2];
a[pos - 2] = temp;
}
else if (dir[a[pos - 1] - 1] == LEFT_TO_RIGHT)
{
int temp = a[pos];
a[pos] = a[pos - 1];
a[pos - 1] = temp;
}
// changing the directions
// for elements greater
// than largest mobile integer.
for (int i = 0; i < n; i++)
{
if (a[i] > mobile)
{
if (dir[a[i] - 1] == LEFT_TO_RIGHT)
dir[a[i] - 1] = RIGHT_TO_LEFT;
else if (dir[a[i] - 1] == RIGHT_TO_LEFT)
dir[a[i] - 1] = LEFT_TO_RIGHT;
}
}
for (int i = 0; i < n; i++)
Console.Write(a[i]);
Console.Write(" ");
return 0;
}
// To end the algorithm
// for efficiency it ends
// at the factorial of n
// because number of
// permutations possible
// is just n!.
public static int fact(int n)
{
int res = 1;
for (int i = 1; i <= n; i++)
res = res * i;
return res;
}
// This function mainly
// calls printOnePerm()
// one by one to print
// all permutations.
public static void printPermutation(int n)
{
// To store current
// permutation
int []a = new int[n];
// To store current
// directions
bool []dir = new bool[n];
// storing the elements
// from 1 to n and
// printing first permutation.
for (int i = 0; i < n; i++)
{
a[i] = i + 1;
Console.Write(a[i]);
}
Console.Write("\n");
// initially all directions
// are set to RIGHT TO
// LEFT i.e. 0.
for (int i = 0; i < n; i++)
dir[i] = RIGHT_TO_LEFT;
// for generating permutations
// in the order.
for (int i = 1; i < fact(n); i++)
printOnePerm(a, dir, n);
}
// Driver function
public static void Main()
{
int n = 4;
printPermutation(n);
}
}
// This code is contributed by nitin mittal.
Producción:
1234 1243 1423 4123 4132 1432 1342 1324 3124 3142 3412 4312 4321 3421 3241 3214 2314 2341 2431 4231 4213 2413 2143 2134
Publicación traducida automáticamente
Artículo escrito por Shubhendra Singhal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA