How to generate all the permutations from an array of numbers.

11/07/2018

This example generates all the permutations of an array of numbers. The processing is done recurcively by generating all the permutations for the first number and combining it with the processing of the remaining numbers in the array. If the list contains only one elements there is nothing to do.

Create the following java file:

import java.util.ArrayList;

public class InterviewPermutations {

    public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> a) {
	// Input validation
	if( a == null )
	    throw new IllegalArgumentException( "Input cannot be null" );
	        
	ArrayList<ArrayList<Integer>> toReturn = new ArrayList<ArrayList<Integer>>();

	if( a.size() == 1 ){
	    toReturn.add( new ArrayList<Integer>(a) );
	    return toReturn;
	}
	
	// Loop on all the elements. 
	for( int i = 0 ; i < a.size(); i++ ){
	    int current = a.get( i );
	    ArrayList<Integer> tmp = new ArrayList<Integer>(a);
	    tmp.remove( i );

	   // Call recursively with subset 
	   ArrayList<ArrayList<Integer>> res = permute(tmp);
	       
	   // Create the result from the returned sub list
	   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 );
	   }
	}
	   
	// return the results
	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( "Starting array:" );
	System.out.println( a );

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

    }

}

The output will be:

Starting array:
[1, 2, 3]
Result:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

This example contains 3 elements, the number of permutations is 3! or 3 * 2 * 1 or 6.

References:

java io

Recent Comments