Permutación de matriz

Así es como puedes imprimir todas las permutaciones en 10 líneas de código:

public class Permute{
    static void permute(java.util.List<Integer> 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);
    }
}

Toma el primer elemento de una matriz (k = 0) y lo intercambia con cualquier elemento (i) de la matriz. Luego aplica recursivamente la permutación en la matriz comenzando con el segundo elemento. De esta manera obtienes todas las permutaciones que comienzan con el i-ésimo elemento. La parte complicada es que después de la llamada recursiva debes intercambiar el i-ésimo elemento con el primer elemento; de lo contrario, podrías obtener valores repetidos en el primer lugar. Al volver a intercambiarlo, restauramos el orden de los elementos (básicamente se 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, no funcionará como está.

Por ejemplo, dada la entrada [3,3,4,4] todas las permutaciones posibles (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 permutela función anterior obtendrá [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 quedará bien. Afortunadamente, existe un algoritmo mejor (lo encontré aquí ) que maneja valores repetidos y no es recursivo.

En primer lugar, tenga en cuenta que la permutación de una matriz de cualquier objeto se puede reducir a permutaciones de números enteros enumerándolos en cualquier orden.

Para obtener permutaciones de una matriz de números enteros, comience con una matriz ordenada en orden ascendente. Tu 'objetivo' es hacerlo descender. Para generar la siguiente permutación, intenta encontrar el primer índice desde abajo donde la secuencia no es descendente 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. Constructor acepta una matriz de objetos y los asigna a una matriz de números enteros usando HashMap.

import java.lang.reflect.Array;
import java.util.*;
class Permutations<E> implements  Iterator<E[]>{

    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<E, Integer> hm = new HashMap<E, Integer>();
        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<Integer> perm = new TCMath.Permutations<Integer>(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 todas 7!/(2!*3!*2!)=210las permutaciones.

Jan 21 '2013 17:01 Yevgen Yampolskiy