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

11/07/2018

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

Comentarios Recientes