Generate all permutations

Question

I have written this Java snippet to generate all permutations of a given array of integers. Can somebody review it and give some pointers as to how to make it more generic? I.e. instead of dealing with only ints, it should be able to handle a collection of any data type.

import java.util.Arrays;
public class PrintPermutations{
        private int[] taperedArray(int[] arr,int idx){
                int nArray[] = new int[arr.length-1];
                for(int i=0,j=0;i<nArray.length;i++,j++){
                  if(j == idx){j+=1;}
                  nArray[i] = arr[j];
                }
                return nArray;
        }

        public void printPermutations(String prefix,int[] arr){
                if(arr.length == 1){
                  System.out.println(prefix + arr[0]);
                }else{
                 for(int i=0;i<arr.length;i++){
                   printPermutations(prefix+arr[i]+",",taperedArray(arr,i));
                 }
                }
        }

        public static void main(String[] args){
                PrintPermutations pp = new PrintPermutations();
                int data[] = new int[]{1,2,3};
                pp.printPermutations("",data);
        }
}

Answer 1

public class PrintPermutations{

Classes are types of things, so they usually get noun names, e.g.

public class PermutationPrinter<T> {

You mention that you want this to work with generic types. The way to do that is to add a generic parameter.

        public void printPermutations(String prefix,int[] arr){

Unfortunately, there are no generic arrays in Java, so you have to switch to a different data type. You have a list of items, so let's switch to List.

    public void permuteAndPrint(String prefix, List<T> items) {

Your method actually does two things, not one. Thus, the compound name. This actually violates something called the Single Responsibility Principle, but I'm going to ignore that for now.

I prefer plural names for collections, so I changed the now inaccurate arr to items.

Side note: you use eight column indent for the first two levels and then use smaller indents thereafter. The usual suggestion is to always tab the same amount. I switched to a consistent four column tab, as that's pretty common (standard) in Java programming.

                if(arr.length == 1){
                  System.out.println(prefix + arr[0]);
                }else{

Rather than use an if/else construct, it is common to return from the base case of a recursive function:

        if (items.size() == 1) {
            System.out.println(prefix + items.get(0));
            return;
        }

This allows the rest of the function to work without extra indent and makes it more recognizable as a base case.

                 for(int i=0;i<arr.length;i++){
                   printPermutations(prefix+arr[i]+",",taperedArray(arr,i));
                 }

There are several things that I don't like about this, starting with the index-based for loop. I'd rather use the foreach format:

        for ( T item : items ) {
            List<T> remnants = new ArrayList<T>(items);
            remnants.remove(item);
            permuteAndPrint(prefix + item + ",", remnants);
        }

A useful feature of List is that it includes a remove function that replaces your taperedArray function.

Now rather than saying arr[i], we can say a more readable item.

So the whole class is now

public class PermutationPrinter<T> {

    public void permuteAndPrint(String prefix, List<T> items) {
        if (items.size() == 1) {
            System.out.println(prefix + items.get(0));
            return;
        }

        for ( T item : items ) {
            List<T> remnants = new ArrayList<T>(items);
            remnants.remove(item);
            permuteAndPrint(prefix + item + ",", remnants);
        }
    }

    public static void main(String[] args) {
        PermutationPrinter<Integer> printer = new PermutationPrinter<Integer>();
        List<Integer> data = Arrays.asList(1,2,3);
        printer.permuteAndPrint("", data);
    }

}

This does mostly the same steps as your original and still violates the Single Responsibility Principle. Normally we'd write main something like

    public static void main(String[] args) {
        List<Integer> data = Arrays.asList(1,2,3);
        PermutationPrinter<Integer> printer = new PermutationPrinter<Integer>(data);
        printer.permute();
        printer.print();
    }

This has several advantages. For one, it saves the caller from passing an empty string to the recursive function. Instead, we can now write

public class PermutationPrinter<T> {
    List<T> items;
    List<List<T>> permutations = new ArrayList<>(); 

    public PermutationPrinter(List<T> data) {
        items = data;
    }

    private void _permute(List<T> permutation, List<T> data) {
        if (data.size() <= 0) {
            permutations.add(permutation);
            return;
        }

        for ( T datum : data ) {
            List<T> remnants = new ArrayList<T>(data);
            remnants.remove(datum);
            List<T> elements = new ArrayList<T>(permutation);
            elements.add(datum);
            _permute(elements, remnants);
        }
    }

    private void permute() {
        List<T> permutation = new ArrayList<T>();
        _permute(permutation, items);
    }

    private void print() {
        for ( List<T> permutation : permutations ) {
            T last = permutation.remove(permutation.size() - 1);

            for ( T element : permutation ) {
                System.out.print(element + ", ");
            }

            System.out.println(last);
        }
    }

}

Notice how this hides the details of how the recursive function works inside a public method. This allows the recursive method to be private. We could change its interface tomorrow with no impact outside this class.

Another advantage is that it is easier to unit test the state of variables than output. So we may not be able to unit test print, but we can certainly unit test permute and _permute.

This also allows us to move main out of the class and into its own class. This class shouldn't need a main method.

Note: I haven't attempted to optimize the algorithm. I just rewrote it in a new style.