/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.collections4.iterators;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.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.

Type parameters:
  • <E> – the type of the objects being permuted
Since:4.0
/** * This iterator creates permutations of an input collection, using the * Steinhaus-Johnson-Trotter algorithm (also called plain changes). * <p> * The iterator will return exactly n! permutations of the input collection. * The {@code remove()} operation is not supported, and will throw an * {@code UnsupportedOperationException}. * <p> * NOTE: in case an empty collection is provided, the iterator will * return exactly one empty list as result, as 0! = 1. * * @param <E> the type of the objects being permuted * * @since 4.0 */
public class PermutationIterator<E> implements Iterator<List<E>> {
Permutation is done on theses keys to handle equal objects.
/** * Permutation is done on theses keys to handle equal objects. */
private final int[] keys;
Mapping between keys and objects.
/** * Mapping between keys and objects. */
private final Map<Integer, E> objectMap;
Direction table used in the algorithm:
  • false is left
  • true is right
/** * Direction table used in the algorithm: * <ul> * <li>false is left</li> * <li>true is right</li> * </ul> */
private final boolean[] direction;
Next permutation to return. When a permutation is requested this instance is provided and the next one is computed.
/** * Next permutation to return. When a permutation is requested * this instance is provided and the next one is computed. */
private List<E> nextPermutation;
Standard constructor for this class.
Params:
  • coll – the collection to generate permutations for
Throws:
/** * Standard constructor for this class. * @param coll the collection to generate permutations for * @throws NullPointerException if coll is null */
public PermutationIterator(final Collection<? extends E> coll) { if (coll == null) { throw new NullPointerException("The collection must not be null"); } keys = new int[coll.size()]; direction = new boolean[coll.size()]; Arrays.fill(direction, false); int value = 1; objectMap = new HashMap<>(); for (final E e : coll) { objectMap.put(Integer.valueOf(value), e); keys[value - 1] = value; value++; } nextPermutation = new ArrayList<>(coll); }
Indicates if there are more permutation available.
Returns:true if there are more permutations, otherwise false
/** * Indicates if there are more permutation available. * @return true if there are more permutations, otherwise false */
@Override public boolean hasNext() { return nextPermutation != null; }
Returns the next permutation of the input collection.
Throws:
Returns:a list of the permutator's elements representing a permutation
/** * Returns the next permutation of the input collection. * @return a list of the permutator's elements representing a permutation * @throws NoSuchElementException if there are no more permutations */
@Override public List<E> next() { if (!hasNext()) { throw new NoSuchElementException(); } // find the largest mobile integer k int indexOfLargestMobileInteger = -1; int largestKey = -1; for (int i = 0; i < keys.length; i++) { if ((direction[i] && i < keys.length - 1 && keys[i] > keys[i + 1]) || (!direction[i] && i > 0 && keys[i] > keys[i - 1])) { if (keys[i] > largestKey) { // NOPMD largestKey = keys[i]; indexOfLargestMobileInteger = i; } } } if (largestKey == -1) { final List<E> toReturn = nextPermutation; nextPermutation = null; return toReturn; } // swap k and the adjacent integer it is looking at final int offset = direction[indexOfLargestMobileInteger] ? 1 : -1; final int tmpKey = keys[indexOfLargestMobileInteger]; keys[indexOfLargestMobileInteger] = keys[indexOfLargestMobileInteger + offset]; keys[indexOfLargestMobileInteger + offset] = tmpKey; final boolean tmpDirection = direction[indexOfLargestMobileInteger]; direction[indexOfLargestMobileInteger] = direction[indexOfLargestMobileInteger + offset]; direction[indexOfLargestMobileInteger + offset] = tmpDirection; // reverse the direction of all integers larger than k and build the result final List<E> nextP = new ArrayList<>(); for (int i = 0; i < keys.length; i++) { if (keys[i] > largestKey) { direction[i] = !direction[i]; } nextP.add(objectMap.get(Integer.valueOf(keys[i]))); } final List<E> result = nextPermutation; nextPermutation = nextP; return result; } @Override public void remove() { throw new UnsupportedOperationException("remove() is not supported"); } }