com.bric.util

Class PermutationIterator<T>

  • Type Parameters:
    T -
    All Implemented Interfaces:
    Iterator<List<T>> 

    public class PermutationIterator<T>
extends Object
implements Iterator<List<T>>
    This creates all the possible permutations of a collection of objects. For example, given the elements "A", "B", "C", this will return all 6 possible ways to rearrange these letters: ABC, ACB, BAC, BCA, CAB, CBA.

    • Field Detail

      • allElements

        protected final List<T> allElements

      • ctr

        protected long ctr

      • max

        protected final long max

    • Constructor Detail

      • PermutationIterator

        public PermutationIterator(Collection<T> allElements)
        Create a PermutationIterator.
        Parameters:
        allElements - all the elements this iterator will provide permutations of. Note the number of permutations this iterator creates is the factorial of the size of this list, which means it gets very large very fast. The getFactorial(int) method will throw an ArithmeticException if there are over 20 elements. (This logic could be safely rewritten using BigIntegers to avoid that limitation, but that raises the question: should we?)

    • Method Detail

      • getFactorial

        public static long getFactorial(int k)
                         throws ArithmeticException
        Return the factorial of the argument.
        Parameters:
        k - the input value for the factorial function.
        Returns:
        the factorial of the argument.
        Throws:
        ArithmeticException - if the factorial is too large to be computed using longs. Unit tests suggest this occurs around k=21.

      • hasNext

        public boolean hasNext()

      • next

        public List<T> next()

      • remove

        public void remove()