Package org.apache.commons.collections4.iterators

Class PermutationIterator<E>

java.lang.Object
org.apache.commons.collections4.iterators.PermutationIterator<E>
Type Parameters:
E - the type of the objects being permuted
All Implemented Interfaces:
Iterator<List<E>>
public class PermutationIterator<E> extends Object implements Iterator<List<E>>
This iterator creates permutations of an input collection, using the Steinhaus-Johnson-Trotter algorithm (also called plain changes).

The iterator will return exactly n! permutations of the input collection. The remove() operation is not supported, and will throw an UnsupportedOperationException.

NOTE: in case an empty collection is provided, the iterator will return exactly one empty list as result, as 0! = 1.

Since:
4.0

  • Field Details

    • keys

      private final int[] keys
      Permutation is done on theses keys to handle equal objects.

    • objectMap

      private final Map<Integer,E> objectMap
      Mapping between keys and objects.

    • direction

      private final boolean[] direction
      Direction table used in the algorithm:
      • false is left
      • true is right

    • nextPermutation

      private List<E> nextPermutation
      Next permutation to return. When a permutation is requested this instance is provided and the next one is computed.

  • Constructor Details

    • PermutationIterator

      public PermutationIterator(Collection<? extends E> coll)
      Standard constructor for this class.
      Parameters:
      coll - the collection to generate permutations for
      Throws:
      NullPointerException - if coll is null

  • Method Details

    • hasNext

      public boolean hasNext()
      Indicates if there are more permutation available.
      Specified by:
      hasNext in interface Iterator<E>
      Returns:
      true if there are more permutations, otherwise false

    • next

      public List<E> next()
      Returns the next permutation of the input collection.
      Specified by:
      next in interface Iterator<E>
      Returns:
      a list of the permutator's elements representing a permutation
      Throws:
      NoSuchElementException - if there are no more permutations

    • remove

      public void remove()
      Specified by:
      remove in interface Iterator<E>