    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 *      http://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     * @param collection  the collection to generate permutations for
    075     * @throws NullPointerException if coll is null
    076     */
    077    public PermutationIterator(final Collection<? extends E> collection) {
    078        Objects.requireNonNull(collection, "collection");
    079        keys = new int[collection.size()];
    080        direction = new boolean[collection.size()];
    081        Arrays.fill(direction, false);
    082        int value = 1;
    083        objectMap = new HashMap<>();
    084        for (final E e : collection) {
    085            objectMap.put(Integer.valueOf(value), e);
    086            keys[value - 1] = value;
    087            value++;
    088        }
    089        nextPermutation = new ArrayList<>(collection);
    090    }
    091
    092    /**
    093     * Indicates if there are more permutation available.
    094     * @return true if there are more permutations, otherwise false
    095     */
    096    @Override
    097    public boolean hasNext() {
    098        return nextPermutation != null;
    099    }
    100
    101    /**
    102     * Returns the next permutation of the input collection.
    103     * @return a list of the permutator's elements representing a permutation
    104     * @throws NoSuchElementException if there are no more permutations
    105     */
    106    @Override
    107    public List<E> next() {
    108        if (!hasNext()) {
    109            throw new NoSuchElementException();
    110        }
    111
    112        // find the largest mobile integer k
    113        int indexOfLargestMobileInteger = -1;
    114        int largestKey = -1;
    115        for (int i = 0; i < keys.length; i++) {
    116            if (direction[i] && i < keys.length - 1 && keys[i] > keys[i + 1] ||
    117                !direction[i] && i > 0 && keys[i] > keys[i - 1]) {
    118                if (keys[i] > largestKey) { // NOPMD
    119                    largestKey = keys[i];
    120                    indexOfLargestMobileInteger = i;
    121                }
    122            }
    123        }
    124        if (largestKey == -1) {
    125            final List<E> toReturn = nextPermutation;
    126            nextPermutation = null;
    127            return toReturn;
    128        }
    129
    130        // swap k and the adjacent integer it is looking at
    131        final int offset = direction[indexOfLargestMobileInteger] ? 1 : -1;
    132        final int tmpKey = keys[indexOfLargestMobileInteger];
    133        keys[indexOfLargestMobileInteger] = keys[indexOfLargestMobileInteger + offset];
    134        keys[indexOfLargestMobileInteger + offset] = tmpKey;
    135        final boolean tmpDirection = direction[indexOfLargestMobileInteger];
    136        direction[indexOfLargestMobileInteger] = direction[indexOfLargestMobileInteger + offset];
    137        direction[indexOfLargestMobileInteger + offset] = tmpDirection;
    138
    139        // reverse the direction of all integers larger than k and build the result
    140        final List<E> nextP = new ArrayList<>();
    141        for (int i = 0; i < keys.length; i++) {
    142            if (keys[i] > largestKey) {
    143                direction[i] = !direction[i];
    144            }
    145            nextP.add(objectMap.get(Integer.valueOf(keys[i])));
    146        }
    147        final List<E> result = nextPermutation;
    148        nextPermutation = nextP;
    149        return result;
    150    }
    151
    152    @Override
    153    public void remove() {
    154        throw new UnsupportedOperationException("remove() is not supported");
    155    }
    156
    157}