Given a set of objects, sometimes it's useful to find out all the permutation of these objects, and perform some action upon each permutation. The order of the permutation generation would preferably be in some natural order such as lexicographic i.e. the order they would appear if they were sorted numerically.

How would you go about writing such utility efficiently in Java ?

One possible answer:

public class Permutation<T> {
    public static interface Visitor<T> {
        /** Visits each permutation of objects. */
        public void visit(T[] entry);
    }
    private final T[] objects;
    private T tmp;
    private final Visitor<T> visitor;
    
    /**
     * @param objects set of n objects
     * @param visitor used to visit each permutation
     */
    public Permutation(T[] objects, Visitor<T> visitor) {
        this.objects = objects.clone();
        this.visitor = visitor;
    }
    
    public void compute() { doCompute(0); }
    
    private void doCompute(final int pos) {
        if (pos == objects.length) {
            visitor.visit(objects);
            return;
        }

        doCompute(pos+1);
        
        for (int i=pos+1; i < objects.length; i++) {
            swap(pos, i);
            doCompute(pos+1);
        }
        
        if (pos > 0)
            for (int i=pos+1; i < objects.length; i++)
                swap(i-1, i);
    }
    
    private void swap(int p1, int p2) {
        tmp = objects[p1];
        objects[p1] = objects[p2];
        objects[p2] = tmp;
    }
}

Demo:

Visitor<Character> visitor = new Visitor<Character>() {
    private Set<String> set = new HashSet<String>();

    @Override
    public void visit(Character[] entry) {
        String s = Arrays.toString(entry);
        set.add(s);
        System.out.println(set.size() + ": " + s);
    }
};
String s = "abc";
Character[] ca = new Character[s.length()];

for (int i = s.length() - 1; i > -1; i--)
    ca[i] = s.charAt(i);
new Permutation<Character>(ca, visitor).compute();

Would yield:

1: [a, b, c]
2: [a, c, b]
3: [b, a, c]
4: [b, c, a]
5: [c, a, b]
6: [c, b, a]