Esta es la solución más exacta que encomtrarás brindar, sin embargo mírala detenidamente y valora si es compatible a tu trabajo.
Solución:
Así es como puede imprimir todas las permutaciones en 10 líneas de código:
public class Permute
static void permute(java.util.List arr, int k)
for(int i = k; i < arr.size(); i++)
java.util.Collections.swap(arr, i, k);
permute(arr, k+1);
java.util.Collections.swap(arr, k, i);
if (k == arr.size() -1)
System.out.println(java.util.Arrays.toString(arr.toArray()));
public static void main(String[] args)
Permute.permute(java.util.Arrays.asList(3,4,6,2,1), 0);
Tomas el primer elemento de un array (k = 0) e intercambiarlo con cualquier elemento (i) del array. Luego aplica de forma recursiva la permutación en array comenzando con el segundo elemento. De esta manera, obtienes todas las permutaciones que comienzan con el elemento i-ésimo. La parte complicada es que después de la llamada recursiva debe intercambiar el elemento i-ésimo con el primer elemento, de lo contrario, podría obtener valores repetidos en el primer lugar. Al intercambiarlo, restauramos el orden de los elementos (básicamente, retrocede).
Iteradores y extensión al caso de valores repetidos
El inconveniente del algoritmo anterior es que es recursivo y no funciona bien con los iteradores. Otro problema es que si permite elementos repetidos en su entrada, entonces no funcionará como está.
Por ejemplo, una entrada dada [3,3,4,4] todas las posibles permutaciones (sin repeticiones) son
[3, 3, 4, 4]
[3, 4, 3, 4]
[3, 4, 4, 3]
[4, 3, 3, 4]
[4, 3, 4, 3]
[4, 4, 3, 3]
(si simplemente aplica permute función desde arriba obtendrás [3,3,4,4] cuatro veces, y esto no es lo que naturalmente desea ver en este caso; y el número de tales permutaciones es 4! / (2! * 2!) = 6)
Es posible modificar el algoritmo anterior para manejar este caso, pero no se verá bien. Afortunadamente, hay un algoritmo mejor (lo encontré aquí) que maneja valores repetidos y no es recursivo.
Primera nota, esa permutación de array de cualquier objeto se puede reducir a permutaciones de números enteros enumerándolos en cualquier orden.
Para obtener permutaciones de un número entero array, empiezas con un array ordenados en orden ascendente. Tu 'objetivo' es hacerlo descender. Para generar la siguiente permutación, está tratando de encontrar el primer índice desde la parte inferior donde la secuencia no puede descender, y mejora el valor en ese índice mientras cambia el orden del resto de la cola de descendente a ascendente en este caso.
Aquí está el núcleo del algoritmo:
//ind is an array of integers
for(int tail = ind.length - 1;tail > 0;tail--)
if (ind[tail - 1] < ind[tail])//still increasing
//find last element which does not exceed ind[tail-1]
int s = ind.length - 1;
while(ind[tail-1] >= ind[s])
s--;
swap(ind, tail-1, s);
//reverse order of elements in the tail
for(int i = tail, j = ind.length - 1; i < j; i++, j--)
swap(ind, i, j);
break;
Aquí está el código completo del iterador. El constructor acepta un array de objetos, y los mapea en un array de enteros usando HashMap.
import java.lang.reflect.Array;
import java.util.*;
class Permutations implements Iterator
private E[] arr;
private int[] ind;
private boolean has_next;
public E[] output;//next() returns this array, make it public
Permutations(E[] arr)
this.arr = arr.clone();
ind = new int[arr.length];
//convert an array of any elements into array of integers - first occurrence is used to enumerate
Map hm = new HashMap();
for(int i = 0; i < arr.length; i++)
Integer n = hm.get(arr[i]);
if (n == null)
hm.put(arr[i], i);
n = i;
ind[i] = n.intValue();
Arrays.sort(ind);//start with ascending sequence of integers
//output = new E[arr.length]; <-- cannot do in Java with generics, so use reflection
output = (E[]) Array.newInstance(arr.getClass().getComponentType(), arr.length);
has_next = true;
public boolean hasNext()
return has_next;
/**
* Computes next permutations. Same array instance is returned every time!
* @return
*/
public E[] next()
if (!has_next)
throw new NoSuchElementException();
for(int i = 0; i < ind.length; i++)
output[i] = arr[ind[i]];
//get next permutation
has_next = false;
for(int tail = ind.length - 1;tail > 0;tail--)
if (ind[tail - 1] < ind[tail])//still increasing
//find last element which does not exceed ind[tail-1]
int s = ind.length - 1;
while(ind[tail-1] >= ind[s])
s--;
swap(ind, tail-1, s);
//reverse order of elements in the tail
for(int i = tail, j = ind.length - 1; i < j; i++, j--)
swap(ind, i, j);
has_next = true;
break;
return output;
private void swap(int[] arr, int i, int j)
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
public void remove()
Uso / prueba:
TCMath.Permutations perm = new TCMath.Permutations(new Integer[]3,3,4,4,4,5,5);
int count = 0;
while(perm.hasNext())
System.out.println(Arrays.toString(perm.next()));
count++;
System.out.println("total: " + count);
Imprime todo 7!/(2!*3!*2!)=210 permutaciones.
Si está usando C ++, puede usar std::next_permutation desde el
int a[] = 3,4,6,2,1;
int size = sizeof(a)/sizeof(a[0]);
std::sort(a, a+size);
do
// print a's elements
while(std::next_permutation(a, a+size));
Aquí hay una implementación de la Permutación en Java:
Permutación - Java
¡Deberías comprobarlo!
Editar: código pegado a continuación para proteger contra la muerte del enlace:
// Permute.java -- A class generating all permutations
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.lang.reflect.Array;
public class Permute implements Iterator
private final int size;
private final Object [] elements; // copy of original 0 .. size-1
private final Object ar; // array for output, 0 .. size-1
private final int [] permutation; // perm of nums 1..size, perm[0]=0
private boolean next = true;
// int[], double[] array won't work :-(
public Permute (Object [] e)
size = e.length;
elements = new Object [size]; // not suitable for primitives
System.arraycopy (e, 0, elements, 0, size);
ar = Array.newInstance (e.getClass().getComponentType(), size);
System.arraycopy (e, 0, ar, 0, size);
permutation = new int [size+1];
for (int i=0; ipermutation[i+1]) i--;
if (i==0)
next = false;
for (int j=0; jpermutation[j]) j--;
swap (i,j);
int r = size;
int s = i+1;
while (r>s) swap(r,s); r--; s++;
return ar;
public String toString ()
final int n = Array.getLength(ar);
final StringBuffer sb = new StringBuffer ("[");
for (int j=0; j Comentarios y puntuaciones
Tienes la posibilidad comunicar este escrito si te valió la pena.