Generate permutations (in lexicographic order) using Java. #permutation #java #lexicographic-permutation

Permutation.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.Collectors;
import java.util.stream.Stream;

import org.apache.commons.lang3.ArrayUtils;

import static java.lang.System.out;

/**
 * Generate permutations in lexicographic order.
 */
public class Permutation <T extends Comparable<T>> 
    implements Iterable<List<T>>
{
    private static class Iter <T extends Comparable<T>> 
        implements Iterator<List<T>>
    {
        private final int n;
        private T[] current;
        
        private Iter(T[] items)
        {
            current = Arrays.copyOf(items, items.length);
            n = items.length;
        }
        
        /**
         * Compute next (in lexicographic order) permutation and advance to it. 
         * 
         * <p>
         * Find greater index {@code i} for which a {@code j} exists, such that:
         *   {@code j > i and a[i] < a[j]} (i.e. the 1st non-inversion).
         * For those {@code j} satisfying the above, we pick the greatest.
         * The next permutation is provided by swapping items at i,j and reversing the
         * range {@code a[i+1..n]}<br/>
         * 
         * <p>
         * Note: Prove that the range {@code a[i+1..n]} (after swap) is reverse sorted 
         */
        private void advanceToNext()
        {
            // Find i when 1st non-inversion happens
            
            int i = n - 2;
            while (i >= 0 && current[i].compareTo(current[i + 1]) >= 0)
                --i;
            
            if (i < 0) { 
                // No next permutation exists (curr is fully reversed)
                current = null;
                return;
            }
            
            // Find greater j for given i for 1st non-inversion
            
            int j = n - 1;
            while (current[j].compareTo(current[i]) <= 0)
                --j;
            
            // Swap i,j and reverse range [i+1..n]
            
            swap(current, i, j);
            
            assert ArrayUtils.isSorted(
                Arrays.copyOfRange(current, i + 1, n), (u, v) -> v.compareTo(u));
            
            reverse(current, i + 1, n);
        }
        
        @Override
        public boolean hasNext()
        {
            return current != null;
        }

        @Override
        public List<T> next()
        {
            // Take a snapshot of current state
            List<T> output = new ArrayList<>(Arrays.asList(current));      
            
            // Advance to next
            advanceToNext();
            
            // Return snapshot
            return Collections.unmodifiableList(output);
        }
        
        private static <T> void swap(T[] a, int i, int j)
        {
            T t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        
        private static <T> void reverse(T[] a, int start, int end)
        {
            int i = start, j = end - 1;
            while (i < j) {
                swap(a, i, j);
                ++i;
                --j;
            }
        }
    }
    
    private final T[] items;
    
    private Permutation(T[] items)
    {
        this.items = Arrays.copyOf(items, items.length);
    }
        
    @Override
    public Iterator<List<T>> iterator()
    {
        return new Iter<T>(items);
    }
        
    public static <U extends Comparable<U>> Permutation<U> from(U[] items)
    {
        if (items == null)
            throw new NullPointerException("Expected a non-null array");
        if (items.length == 0)
            throw new IllegalArgumentException("Expected a non-empty array");
        
        return new Permutation<U>(items);
    }
    
    public static <U extends Comparable<U>> Permutation<U> from(List<U> items)
    {
        if (items == null)
            throw new NullPointerException("Expected a non-null list");
        if (items.isEmpty())
            throw new IllegalArgumentException("Expected a non-empty list");
        
        final int n = items.size();
        
        @SuppressWarnings("unchecked") // needed due to type erasure ...
        U[] u = (U[]) items.toArray(new Comparable[n]);
        
        return new Permutation<U>(u);
    }
    
    public static int numberOfPermutations(int n)
    {
        return factorial(n);
    }
    
    private static int factorial(int n)
    {
        int f = 1;
        for (int i = 1; i <= n; ++i)
            f *= i;
        return f;
    }
    
    //
    // Tests / Demos
    // 
    
    public static void main(String[] args)
    {
        test1(9);
    }
    
    public static void demo()
    {
        Integer[] input = new Integer[] {1, 2, 3, 4, 5};
        
        int cnt = 0;
        for (List<Integer> x: Permutation.from(input)) {
            out.println(x);
            cnt++; 
        }
        
        out.printf("Generated %d permutations%n", cnt);
    }
    
    public static void test1(final int n)
    {
        if (n < 0)
            throw new IllegalArgumentException("n");
        
        final int N = numberOfPermutations(n);
        
        final Integer[] input = Stream.<Integer>iterate(1, k -> k + 1)
            .limit(n)
            .toArray(Integer[]::new);   
        out.printf("Using input: %s%n", Arrays.toString(input));
        
        Set<String> output = new TreeSet<String>();
        int np = 0;
        for (List<Integer> x: Permutation.from(input)) {
            output.add(x.stream()
                .map(u -> u.toString())
                .collect(Collectors.joining()));
            ++np;
        }
        
        assert N == np;
        assert N == output.size();
        
        out.printf("Generated %d! = %d permutations%n", n, np);
    }
}