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 * * Copyright 2016 Tim Wood * * Permission is hereby granted, free of charge, to any person * obtaining a copy of this software and associated documentation * files (the "Software"), to deal in the Software without restriction, * including without limitation the rights to use, copy, modify, merge, * publish, distribute, sublicense, and/or sell copies of the Software, * and to permit persons to whom the Software is furnished to do so, * subject to the following conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. * * @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; } } |