Permutation implementation in Java

Permutation is a very basic and important mathematic concept we learned in school. It has very practical applications in real world. For example, in football.

In simple, permutation describes all possible ways of doing something. For example, there are six permutations of the set {1,2,3}, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). In general, for n items, there are n! number of permutations to arrange these items. How can we implement this algorithm in programming programming language such as Java? Below is a simple code snippet which uses the recursive method. It's quite self-explained.

import java.io.FileNotFoundException;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class Permutation {
    //The entry of the permutation method
    public static <T> List<T[]> permute(T[] arr){
        List<T[]> result = new ArrayList<T[]>();
        permute(new ArrayList(), Arrays.asList(arr), result);
        return result;
    }
     
    // This is the actual method doing the permutation
    // The rationale here is pre will contain the elements which have been permuted,
    // cur will contain the elements to be permuted. If the cur contains no element,
    // the pre will contain the permuted elements, hence it will be outputed.
    // For example : assume we have [1, 2, 3], at the beginning, pre will be empty and
    // cur will contain [1, 2, 3], in the first loop, pre will become [1] and cur will
    // be [2, 3], then in the recursive permute(0 call, pre will be [1, 2] and cur will
    // be [3]....when cur contains no element, pre will be [1, 2, 3] and it will be out.
    // Then we are going to next loop ...
    private static <T> void permute(List pre, List cur, List<T[]> out){
        int size = cur.size();
         
        if(size == 0){
            out.add((T[])pre.toArray());
        } else {
            for(int i=0; i<size; ++i){
                List tmpPre = new ArrayList(pre);
                List tmpCur = new ArrayList(cur);
                tmpPre.add(cur.get(i));
                tmpCur.remove((T)cur.get(i));
                 
                permute(tmpPre, tmpCur, out);      
            }
        }
    }
     
    //Print each row of the permuted values
    public static <T>  void print(List<T[]> list, OutputStream out, char delim){
        try{
            for(T[] i : list){
                int count = 0;
                for(T t : i){
                    if(++count == i.length){
                        out.write((t.toString()).getBytes());
                    } else{
                        out.write((t.toString()+delim).getBytes());
                    }
                }
                out.write("\n".getBytes());
            }
        } catch (Exception ex){
            ex.printStackTrace();
        }
    }
 
    public static void main(String[] args) throws FileNotFoundException {
        Integer[] ints = new Integer[] {1, 2, 3, 4};
        Permutation.print(Permutation.permute(ints), System.out, ',');
         
        Character[] chars = {'a', 'b', 'c', 'd', 'e'};
        Permutation.print(Permutation.permute(chars), new PrintStream("permute.txt"), ' ');
         
        String[] strs = {"abc", "123"};
        Permutation.print(Permutation.permute(strs), System.err, ' ');
    }
}

After calling Permutation.permute(), you will get a result set which contains all the permutations of the items you want to permute. Thereafter the result set can be printed out or written in a file. The delimiter can also be specified to separate the items in each permutation.

This implementation can be reimplemented in other languages as well. Here is one implemented with JavaScript.