| /* |
| * 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; |
| import java.util.Objects; |
| |
| /** |
| * 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. |
| */ |
| private final int[] keys; |
| |
| /** |
| * Mapping between keys and objects. |
| */ |
| private final Map<Integer, E> objectMap; |
| |
| /** |
| * 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. |
| */ |
| private List<E> nextPermutation; |
| |
| /** |
| * Standard constructor for this class. |
| * @param collection the collection to generate permutations for |
| * @throws NullPointerException if coll is null |
| */ |
| public PermutationIterator(final Collection<? extends E> collection) { |
| Objects.requireNonNull(collection, "collection"); |
| keys = new int[collection.size()]; |
| direction = new boolean[collection.size()]; |
| Arrays.fill(direction, false); |
| int value = 1; |
| objectMap = new HashMap<>(); |
| for (final E e : collection) { |
| objectMap.put(Integer.valueOf(value), e); |
| keys[value - 1] = value; |
| value++; |
| } |
| nextPermutation = new ArrayList<>(collection); |
| } |
| |
| /** |
| * 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. |
| * @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"); |
| } |
| |
| } |