Top Description Fields Constructors Methods
org.apache.commons.collections4.iterators

public Class PermutationIterator<E>

extends Object
implements Iterator<List<E>>
Class Inheritance
All Implemented Interfaces
java.util.Iterator
Type Parameters
<E>
the type of the objects being permuted
Imports
java.util.ArrayList, .Arrays, .Collection, .HashMap, .Iterator, .List, .Map, .NoSuchElementException
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 Summary

Modifier and TypeField and Description
private final boolean[]
direction

Direction table used in the algorithm:

  • false is left
  • true is right
private final int[]
keys

Permutation is done on theses keys to handle equal objects.

private List<E>
nextPermutation

Next permutation to return.

private final Map<Integer, E>
objectMap

Mapping between keys and objects.

Constructor Summary

AccessConstructor and Description
public
PermutationIterator(final Collection<? extends E>
the collection to generate permutations for
coll)

Standard constructor for this class.

Method Summary

Modifier and TypeMethod and Description
public boolean

Returns:

true if there are more permutations, otherwise false
hasNext()

Implements java.util.Iterator.hasNext.

Indicates if there are more permutation available.
public List<E>

Returns:

a list of the permutator's elements representing a permutation
next()

Implements java.util.Iterator.next.

Returns the next permutation of the input collection.
public void
remove()

Overrides default java.util.Iterator.remove.

Removes from the underlying collection the last element returned by this iterator (optional operation).
Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

directionback to summary
private final boolean[] direction

Direction table used in the algorithm:

  • false is left
  • true is right
keysback to summary
private final int[] keys

Permutation is done on theses keys to handle equal objects.

nextPermutationback to summary
private List<E> nextPermutation

Next permutation to return. When a permutation is requested this instance is provided and the next one is computed.

objectMapback to summary
private final Map<Integer, E> objectMap

Mapping between keys and objects.

Constructor Detail

PermutationIteratorback to summary
public PermutationIterator(final Collection<? extends E> coll)

Standard constructor for this class.

Parameters
coll:Collection<? extends E>

the collection to generate permutations for

Exceptions
NullPointerException:
if coll is null

Method Detail

hasNextback to summary
public boolean hasNext()

Implements java.util.Iterator.hasNext.

Indicates if there are more permutation available.

Returns:boolean

true if there are more permutations, otherwise false

Annotations
@Override
nextback to summary
public List<E> next()

Implements java.util.Iterator.next.

Returns the next permutation of the input collection.

Returns:List<E>

a list of the permutator's elements representing a permutation

Annotations
@Override
Exceptions
NoSuchElementException:
if there are no more permutations
removeback to summary
public void remove()

Overrides default java.util.Iterator.remove.

Doc from java.util.Iterator.remove.

Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next.

The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method, unless an overriding class has specified a concurrent modification policy.

The behavior of an iterator is unspecified if this method is called after a call to the forEachRemaining method.

Annotations
@Override