    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      https://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4.iterators;
    018
    019import java.util.ArrayList;
    020import java.util.Arrays;
    021import java.util.Collection;
    022import java.util.HashMap;
    023import java.util.Iterator;
    024import java.util.List;
    025import java.util.Map;
    026import java.util.NoSuchElementException;
    027import java.util.Objects;
    028
    029/**
    030 * This iterator creates permutations of an input collection, using the
    031 * Steinhaus-Johnson-Trotter algorithm (also called plain changes).
    032 * <p>
    033 * The iterator will return exactly n! permutations of the input collection.
    034 * The {@code remove()} operation is not supported, and will throw an
    035 * {@code UnsupportedOperationException}.
    036 * </p>
    037 * <p>
    038 * NOTE: in case an empty collection is provided, the iterator will
    039 * return exactly one empty list as result, as 0! = 1.
    040 * </p>
    041 *
    042 * @param <E>  the type of the objects being permuted
    043 * @since 4.0
    044 */
    045public class PermutationIterator<E> implements Iterator<List<E>> {
    046
    047    /**
    048     * Permutation is done on these keys to handle equal objects.
    049     */
    050    private final int[] keys;
    051
    052    /**
    053     * Mapping between keys and objects.
    054     */
    055    private final Map<Integer, E> objectMap;
    056
    057    /**
    058     * Direction table used in the algorithm:
    059     * <ul>
    060     *   <li>false is left</li>
    061     *   <li>true is right</li>
    062     * </ul>
    063     */
    064    private final boolean[] direction;
    065
    066    /**
    067     * Next permutation to return. When a permutation is requested
    068     * this instance is provided and the next one is computed.
    069     */
    070    private List<E> nextPermutation;
    071
    072    /**
    073     * Standard constructor for this class.
    074     *
    075     * @param collection  The collection to generate permutations for
    076     * @throws NullPointerException if coll is null
    077     */
    078    public PermutationIterator(final Collection<? extends E> collection) {
    079        Objects.requireNonNull(collection, "collection");
    080        keys = new int[collection.size()];
    081        direction = new boolean[collection.size()];
    082        Arrays.fill(direction, false);
    083        int value = 1;
    084        objectMap = new HashMap<>();
    085        for (final E e : collection) {
    086            objectMap.put(Integer.valueOf(value), e);
    087            keys[value - 1] = value;
    088            value++;
    089        }
    090        nextPermutation = new ArrayList<>(collection);
    091    }
    092
    093    /**
    094     * Indicates if there are more permutation available.
    095     *
    096     * @return true if there are more permutations, otherwise false
    097     */
    098    @Override
    099    public boolean hasNext() {
    100        return nextPermutation != null;
    101    }
    102
    103    /**
    104     * Returns the next permutation of the input collection.
    105     *
    106     * @return A list of the permutator's elements representing a permutation
    107     * @throws NoSuchElementException if there are no more permutations
    108     */
    109    @Override
    110    public List<E> next() {
    111        if (!hasNext()) {
    112            throw new NoSuchElementException();
    113        }
    114
    115        // find the largest mobile integer k
    116        int indexOfLargestMobileInteger = -1;
    117        int largestKey = -1;
    118        for (int i = 0; i < keys.length; i++) {
    119            if (direction[i] && i < keys.length - 1 && keys[i] > keys[i + 1] ||
    120                !direction[i] && i > 0 && keys[i] > keys[i - 1]) {
    121                if (keys[i] > largestKey) { // NOPMD
    122                    largestKey = keys[i];
    123                    indexOfLargestMobileInteger = i;
    124                }
    125            }
    126        }
    127        if (largestKey == -1) {
    128            final List<E> toReturn = nextPermutation;
    129            nextPermutation = null;
    130            return toReturn;
    131        }
    132
    133        // swap k and the adjacent integer it is looking at
    134        final int offset = direction[indexOfLargestMobileInteger] ? 1 : -1;
    135        final int tmpKey = keys[indexOfLargestMobileInteger];
    136        keys[indexOfLargestMobileInteger] = keys[indexOfLargestMobileInteger + offset];
    137        keys[indexOfLargestMobileInteger + offset] = tmpKey;
    138        final boolean tmpDirection = direction[indexOfLargestMobileInteger];
    139        direction[indexOfLargestMobileInteger] = direction[indexOfLargestMobileInteger + offset];
    140        direction[indexOfLargestMobileInteger + offset] = tmpDirection;
    141
    142        // reverse the direction of all integers larger than k and build the result
    143        final List<E> nextP = new ArrayList<>();
    144        for (int i = 0; i < keys.length; i++) {
    145            if (keys[i] > largestKey) {
    146                direction[i] = !direction[i];
    147            }
    148            nextP.add(objectMap.get(Integer.valueOf(keys[i])));
    149        }
    150        final List<E> result = nextPermutation;
    151        nextPermutation = nextP;
    152        return result;
    153    }
    154
    155    /**
    156     * Always throws {@link UnsupportedOperationException}.
    157     *
    158     * @throws UnsupportedOperationException Always thrown.
    159     */
    160    @Override
    161    public void remove() {
    162        throw new UnsupportedOperationException("remove() is not supported");
    163    }
    164
    165}