Permutations

Permutations.java

import java.util.*;

public class Permutations {
    private Permutations() {
    }

    public static void main(String[] args) {
        for (List<Integer> li : permutate(Arrays.asList(1, 2, 4, 9))) {
            System.out.println(li);
        }
    }

    public static <T> List<List<T>> permutate(List<T> list) {
        List<List<T>> result = new ArrayList<>();
        backtrack(list, new int[list.size()], 0, new BitSet(list.size()), result);
        return result;
    }

    private static <T> void backtrack(final List<T> data,
                                      final int[] indexes,
                                      final int k,
                                      final BitSet bs,
                                      final List<List<T>> result) {
        if (k == data.size()) {
            List<T> list = new ArrayList<>(k);
            for (int i : indexes) {
                list.add(data.get(i));
            }
            result.add(list);
        } else {
           for (int i=0; i<data.size(); ++i) {
               if (!bs.get(i)) {
                 indexes[k] = i;
                 bs.set(i);
                 backtrack(data, indexes, k+1, bs, result);
                 bs.set(i, false);
             }
         }
     }
 }
}