PermutationEncoding.java

PermutationEncoding.java

import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.PrimitiveIterator;
import java.util.function.IntConsumer;

/**
 * @author Devin Smith
 */
public class PermutationEncoding {

    /**
     * Returns a primitive int iterator with each of the values 0, 1, ..., n - 1 exactly once.
     *
     * Note: is easily generalized w/ long or BigInteger
     */
    private static PrimitiveIterator.OfInt permutation(final int permutationIndex, final int n) {
        if (!(n >= 0 && n <= 12)) {
            // fact(13) too large for int
            throw new IllegalStateException("Only works with 0 <= n <= 12");
        }

        return new PrimitiveIterator.OfInt() {
            int[] indices = new int[n];
            int index = 0;
            int value = permutationIndex;

            {
                Arrays.setAll(indices, i -> i);
            }

            @Override
            public boolean hasNext() {
                return index < n;
            }

            @Override
            public int nextInt() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                // This is essentially a lazy shuffle algorithm, where our permutation order is
                // given by the permutationIndex

                // our first chosen will be between [0, N - 1]
                // our next chosen will be between [0, N - 2]
                // etc
                final int chosen = value % (n - index);
                value /= (n - index);

                // swap indices
                final int tmp = indices[chosen + index];
                indices[chosen + index] = indices[index];
                indices[index] = tmp;

                // I *think* there are more efficient ways to go from a permutationIndex to returned
                // index. In particular, the array seems inefficient. Of course, if we are keeping
                // the full state around (permutationIndex), that takes up O(N log N) space, same as
                // the array.

                ++index;
                return tmp;
            }
        };
    }

    private static int fact(int n) {
        return n == 0 ? 1 : n * fact(n - 1);
    }

    public static void main(String[] args) {
        final int N = 4;
        final int L = fact(N);
        for (int i = 0; i < L; ++i) {
            permutation(i, N)
                .forEachRemaining((IntConsumer)System.out::print);
            System.out.println();
        }
    }
}