Cómo generar todas las permutaciones de una matriz de números.

Este ejemplo genera todas las permutaciones de una matriz de números. El procesamiento se realiza de forma recurrente al generar todas las permutaciones para el primer número y combinarlo con el procesamiento de los números restantes en la matriz. Si la lista contiene solo un elemento, no hay nada que hacer.

Crea el siguiente archivo java:

import java.util.ArrayList;

public class InterviewPermutations {

    public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> a) {
	// Validación de entrada
	if( a == null )
	    throw new IllegalArgumentException( "La entrada no puede ser nula" );
	        
	ArrayList<ArrayList<Integer>> toReturn = new ArrayList<ArrayList<Integer>>();

	if( a.size() == 1 ){
	    toReturn.add( new ArrayList<Integer>(a) );
	    return toReturn;
	}
	
	// Bucle en todos los elementos. 
	for( int i = 0 ; i < a.size(); i++ ){
	    int current = a.get( i );
	    ArrayList<Integer> tmp = new ArrayList<Integer>(a);
	    tmp.remove( i );

	   // Llamada recursiva con subconjunto 
	   ArrayList<ArrayList<Integer>> res = permute(tmp);
	       
	   // Crear el resultado de la sub lista devuelta
	   for( int j = 0 ; j < res.size() ; j++ ){
	       ArrayList<Integer> toAdd = new ArrayList<Integer>();
	       toAdd.add( current );
	       toAdd.addAll( res.get( j ) );
	       
	       toReturn.add( toAdd );
	   }
	}
	   
	// devolver los resultados
	return toReturn;
    }
    
    public static void main(String[] argv) throws Exception {
	InterviewPermutations t = new InterviewPermutations();

	ArrayList<Integer> a = new ArrayList<Integer>();
	a.add( 1 );
	a.add( 2 );
	a.add( 3 );
	
	
	System.out.println( "Array inicial:" );
	System.out.println( a );

	
	ArrayList<ArrayList<Integer>> res = t.permute(a);
	
	System.out.println( "Resultado:" );
	for(ArrayList<Integer> c : res ){
	    System.out.println( c );
	}

    }

}

El resultado será:

Array inicial:
[1, 2, 3]
Resultado:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Este ejemplo contiene 3 elementos, el número de permutaciones es 3! o 3 * 2 * 1 o 6.

Referencias

java io