Dada una array arr[] de tamaño N , la tarea es generar e imprimir todas las permutaciones de la array dada.
Ejemplos:
Entrada: arr[] = {1, 2}
Salida:
1 2
2 1Entrada: {0, 1, 2}
Salida:
0 1 2
1 0 2
0 2 1
2 0 1
1 2 0
2 1 0
Enfoque: Los métodos recursivos para resolver los problemas anteriores se discuten aquí y aquí . En esta publicación, se discutirá un método iterativo para generar todas las permutaciones para una array dada.
El método iterativo actúa como una máquina de estados. Cuando se llama a la máquina, genera una permutación y pasa a la siguiente.
Para comenzar, necesitamos una array de enteros Indexes para almacenar todos los índices de la array de entrada, y los valores en la array Indexes se inicializan para que sean 0 a n – 1 . Lo que debemos hacer es permutar la array de índices .
Durante la iteración, encontramos el aumento de índice más pequeño en la array de índices , de modo que Indexes[Increase] < Indexes[Increase + 1] , que es el primer «aumento de valor». Luego, tenemos Indexes[0] > Indexes[1] > Indexes[2] > … > Indexes[Increase] , que es un tramo de valores decrecientes de index[0] . Los próximos pasos serán:
- Encuentre el índice medio tal que Índices[medio] sea el mayor con las restricciones de que 0 ≤ medio ≤ Incremento e Índices[medio] < Índices[Incremento + 1] ; dado que los índices de array se ordenan inversamente de 0 a Incremento , este paso puede usar la búsqueda binaria.
- Intercambiar índices[Incremento + 1] e Índices[medio] .
- Invertir Índices[0] a Índices[Incremento] .
Cuando los valores en los índices se vuelven n – 1 a 0 , no hay un “aumento de valor” y el algoritmo termina.
Para generar la combinación, recorremos la array de índices y los valores de la array de enteros son los índices de la array de entrada.
La siguiente imagen ilustra la iteración en el algoritmo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
template <typename T>
class AllPermutation {
private:
// The input array for permutation
const T* Arr;
// Length of the input array
const int Length;
// Index array to store indexes of input array
int* Indexes;
// The index of the first "increase"
// in the Index array which is the smallest
// i such that Indexes[i] < Indexes[i + 1]
int Increase;
public:
// Constructor
AllPermutation(T* arr, int length)
: Arr(arr), Length(length)
{
this->Indexes = nullptr;
this->Increase = -1;
}
// Destructor
~AllPermutation()
{
if (this->Indexes != nullptr) {
delete[] this->Indexes;
}
}
// Initialize and output
// the first permutation
void GetFirst()
{
// Allocate memory for Indexes array
this->Indexes = new int[this->Length];
// Initialize the values in Index array
// from 0 to n - 1
for (int i = 0; i < this->Length; ++i) {
this->Indexes[i] = i;
}
// Set the Increase to 0
// since Indexes[0] = 0 < Indexes[1] = 1
this->Increase = 0;
// Output the first permutation
this->Output();
}
// Function that returns true if it is
// possible to generate the next permutation
bool HasNext()
{
// When Increase is in the end of the array,
// it is not possible to have next one
return this->Increase != (this->Length - 1);
}
// Output the next permutation
void GetNext()
{
// Increase is at the very beginning
if (this->Increase == 0) {
// Swap Index[0] and Index[1]
this->Swap(this->Increase, this->Increase + 1);
// Update Increase
this->Increase += 1;
while (this->Increase < this->Length - 1
&& this->Indexes[this->Increase]
> this->Indexes[this->Increase + 1]) {
++this->Increase;
}
}
else {
// Value at Indexes[Increase + 1] is greater than Indexes[0]
// no need for binary search,
// just swap Indexes[Increase + 1] and Indexes[0]
if (this->Indexes[this->Increase + 1] > this->Indexes[0]) {
this->Swap(this->Increase + 1, 0);
}
else {
// Binary search to find the greatest value
// which is less than Indexes[Increase + 1]
int start = 0;
int end = this->Increase;
int mid = (start + end) / 2;
int tVal = this->Indexes[this->Increase + 1];
while (!(this->Indexes[mid] < tVal
&& this->Indexes[mid - 1] > tVal)) {
if (this->Indexes[mid] < tVal) {
end = mid - 1;
}
else {
start = mid + 1;
}
mid = (start + end) / 2;
}
// Swap
this->Swap(this->Increase + 1, mid);
}
// Invert 0 to Increase
for (int i = 0; i <= this->Increase / 2; ++i) {
this->Swap(i, this->Increase - i);
}
// Reset Increase
this->Increase = 0;
}
this->Output();
}
private:
// Function to output the input array
void Output()
{
for (int i = 0; i < this->Length; ++i) {
// Indexes of the input array
// are at the Indexes array
cout << (this->Arr[this->Indexes[i]]) << " ";
}
cout << endl;
}
// Swap two values in the Indexes array
void Swap(int p, int q)
{
int tmp = this->Indexes[p];
this->Indexes[p] = this->Indexes[q];
this->Indexes[q] = tmp;
}
};
// Driver code
int main()
{
int arr[] = { 0, 1, 2 };
AllPermutation<int> perm(arr, sizeof(arr) / sizeof(int));
perm.GetFirst();
while (perm.HasNext()) {
perm.GetNext();
}
return 0;
}
Java
// Java implementation of the approach
class AllPermutation
{
// The input array for permutation
private final int Arr[];
// Index array to store indexes of input array
private int Indexes[];
// The index of the first "increase"
// in the Index array which is the smallest
// i such that Indexes[i] < Indexes[i + 1]
private int Increase;
// Constructor
public AllPermutation(int arr[])
{
this.Arr = arr;
this.Increase = -1;
this.Indexes = new int[this.Arr.length];
}
// Initialize and output
// the first permutation
public void GetFirst()
{
// Allocate memory for Indexes array
this.Indexes = new int[this.Arr.length];
// Initialize the values in Index array
// from 0 to n - 1
for (int i = 0; i < Indexes.length; ++i)
{
this.Indexes[i] = i;
}
// Set the Increase to 0
// since Indexes[0] = 0 < Indexes[1] = 1
this.Increase = 0;
// Output the first permutation
this.Output();
}
// Function that returns true if it is
// possible to generate the next permutation
public boolean HasNext()
{
// When Increase is in the end of the array,
// it is not possible to have next one
return this.Increase != (this.Indexes.length - 1);
}
// Output the next permutation
public void GetNext()
{
// Increase is at the very beginning
if (this.Increase == 0)
{
// Swap Index[0] and Index[1]
this.Swap(this.Increase, this.Increase + 1);
// Update Increase
this.Increase += 1;
while (this.Increase < this.Indexes.length - 1
&& this.Indexes[this.Increase]
> this.Indexes[this.Increase + 1])
{
++this.Increase;
}
}
else
{
// Value at Indexes[Increase + 1] is greater than Indexes[0]
// no need for binary search,
// just swap Indexes[Increase + 1] and Indexes[0]
if (this.Indexes[this.Increase + 1] > this.Indexes[0])
{
this.Swap(this.Increase + 1, 0);
}
else
{
// Binary search to find the greatest value
// which is less than Indexes[Increase + 1]
int start = 0;
int end = this.Increase;
int mid = (start + end) / 2;
int tVal = this.Indexes[this.Increase + 1];
while (!(this.Indexes[mid]<tVal&& this.Indexes[mid - 1]> tVal))
{
if (this.Indexes[mid] < tVal)
{
end = mid - 1;
}
else
{
start = mid + 1;
}
mid = (start + end) / 2;
}
// Swap
this.Swap(this.Increase + 1, mid);
}
// Invert 0 to Increase
for (int i = 0; i <= this.Increase / 2; ++i)
{
this.Swap(i, this.Increase - i);
}
// Reset Increase
this.Increase = 0;
}
this.Output();
}
// Function to output the input array
private void Output()
{
for (int i = 0; i < this.Indexes.length; ++i)
{
// Indexes of the input array
// are at the Indexes array
System.out.print(this.Arr[this.Indexes[i]]);
System.out.print(" ");
}
System.out.println();
}
// Swap two values in the Indexes array
private void Swap(int p, int q)
{
int tmp = this.Indexes[p];
this.Indexes[p] = this.Indexes[q];
this.Indexes[q] = tmp;
}
}
// Driver code
class AppDriver
{
public static void main(String args[])
{
int[] arr = { 0, 1, 2 };
AllPermutation perm = new AllPermutation(arr);
perm.GetFirst();
while (perm.HasNext())
{
perm.GetNext();
}
}
}
// This code is contributed by ghanshyampandey
C#
// C# implementation of the approach
using System;
namespace Permutation {
class AllPermutation<T> {
// The input array for permutation
private readonly T[] Arr;
// Index array to store indexes of input array
private int[] Indexes;
// The index of the first "increase"
// in the Index array which is the smallest
// i such that Indexes[i] < Indexes[i + 1]
private int Increase;
// Constructor
public AllPermutation(T[] arr)
{
this.Arr = arr;
this.Increase = -1;
}
// Initialize and output
// the first permutation
public void GetFirst()
{
// Allocate memory for Indexes array
this.Indexes = new int[this.Arr.Length];
// Initialize the values in Index array
// from 0 to n - 1
for (int i = 0; i < Indexes.Length; ++i) {
this.Indexes[i] = i;
}
// Set the Increase to 0
// since Indexes[0] = 0 < Indexes[1] = 1
this.Increase = 0;
// Output the first permutation
this.Output();
}
// Function that returns true if it is
// possible to generate the next permutation
public bool HasNext()
{
// When Increase is in the end of the array,
// it is not possible to have next one
return this.Increase != (this.Indexes.Length - 1);
}
// Output the next permutation
public void GetNext()
{
// Increase is at the very beginning
if (this.Increase == 0) {
// Swap Index[0] and Index[1]
this.Swap(this.Increase, this.Increase + 1);
// Update Increase
this.Increase += 1;
while (this.Increase < this.Indexes.Length - 1
&& this.Indexes[this.Increase]
> this.Indexes[this.Increase + 1]) {
++this.Increase;
}
}
else {
// Value at Indexes[Increase + 1] is greater than Indexes[0]
// no need for binary search,
// just swap Indexes[Increase + 1] and Indexes[0]
if (this.Indexes[this.Increase + 1] > this.Indexes[0]) {
this.Swap(this.Increase + 1, 0);
}
else {
// Binary search to find the greatest value
// which is less than Indexes[Increase + 1]
int start = 0;
int end = this.Increase;
int mid = (start + end) / 2;
int tVal = this.Indexes[this.Increase + 1];
while (!(this.Indexes[mid]<tVal&& this.Indexes[mid - 1]> tVal)) {
if (this.Indexes[mid] < tVal) {
end = mid - 1;
}
else {
start = mid + 1;
}
mid = (start + end) / 2;
}
// Swap
this.Swap(this.Increase + 1, mid);
}
// Invert 0 to Increase
for (int i = 0; i <= this.Increase / 2; ++i) {
this.Swap(i, this.Increase - i);
}
// Reset Increase
this.Increase = 0;
}
this.Output();
}
// Function to output the input array
private void Output()
{
for (int i = 0; i < this.Indexes.Length; ++i) {
// Indexes of the input array
// are at the Indexes array
Console.Write(this.Arr[this.Indexes[i]]);
Console.Write(" ");
}
Console.WriteLine();
}
// Swap two values in the Indexes array
private void Swap(int p, int q)
{
int tmp = this.Indexes[p];
this.Indexes[p] = this.Indexes[q];
this.Indexes[q] = tmp;
}
}
// Driver code
class AppDriver {
static void Main()
{
int[] arr = { 0, 1, 2 };
AllPermutation<int> perm = new AllPermutation<int>(arr);
perm.GetFirst();
while (perm.HasNext()) {
perm.GetNext();
}
}
}
}
Producción:
0 1 2 1 0 2 0 2 1 2 0 1 1 2 0 2 1 0
Publicación traducida automáticamente
Artículo escrito por chenchen98 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA