Java code for generating permutations of a list using Heap’s algorithm.

/** * Uses Heap's algorithm to produce all permutations of a given list. * We use an iterator to avoid having to use too much memory. * * @author t.wood * * @param <T> The type of item being permuted * @param <R> The type resulting from decorating the permutation */ public final class PermutationIterator<T,R> implements Iterator<R> { private final Function<List<T>, R> defensiveDecorator; private final List<T> a; private R pending; private final int[] skel; private int i; /** * An iterator of permutations * * @param a the list to permute * @param decorator a decorator to apply to the permutation, a defensive copy * of the permutation is taken before it is passed to the decorator */ public PermutationIterator(final List<T> a, final Function<List<T>,R> decorator) { defensiveDecorator = t -> decorator.apply(new ArrayList<>(t)); pending = defensiveDecorator.apply(a); this.a = new ArrayList<>(a); skel = new int[a.size()]; i = 0; } @Override public boolean hasNext() { return pending != null; } @Override public R next() { if(pending == null) { throw new IndexOutOfBoundsException(); } final R result = pending; pending = permute(); return result; } private R permute() { while(i < a.size()) { if (skel[i] < i) { if (even(i)) { swap(a, 0, i); } else { swap(a, skel[i], i); } skel[i] += 1; i = 0; return defensiveDecorator.apply(a); } else { skel[i] = 0; i += 1; } } return null; } private void swap(final List<T> a, final int i0, final int i1) { final T t = a.get(i0); a.set(i0, a.get(i1)); a.set(i1, t); } private boolean even(final int i) { return i % 2 == 0; } } |