    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 * NOTE: in case an empty collection is provided, the iterator will
    038 * return exactly one empty list as result, as 0! = 1.
    039 *
    040 * @param <E>  the type of the objects being permuted
    041 *
    042 * @since 4.0
    043 */
    044public class PermutationIterator<E> implements Iterator<List<E>> {
    045
    046    /**
    047     * Permutation is done on these keys to handle equal objects.
    048     */
    049    private final int[] keys;
    050
    051    /**
    052     * Mapping between keys and objects.
    053     */
    054    private final Map<Integer, E> objectMap;
    055
    056    /**
    057     * Direction table used in the algorithm:
    058     * <ul>
    059     *   <li>false is left</li>
    060     *   <li>true is right</li>
    061     * </ul>
    062     */
    063    private final boolean[] direction;
    064
    065    /**
    066     * Next permutation to return. When a permutation is requested
    067     * this instance is provided and the next one is computed.
    068     */
    069    private List<E> nextPermutation;
    070
    071    /**
    072     * Standard constructor for this class.
    073     * @param collection  the collection to generate permutations for
    074     * @throws NullPointerException if coll is null
    075     */
    076    public PermutationIterator(final Collection<? extends E> collection) {
    077        Objects.requireNonNull(collection, "collection");
    078        keys = new int[collection.size()];
    079        direction = new boolean[collection.size()];
    080        Arrays.fill(direction, false);
    081        int value = 1;
    082        objectMap = new HashMap<>();
    083        for (final E e : collection) {
    084            objectMap.put(Integer.valueOf(value), e);
    085            keys[value - 1] = value;
    086            value++;
    087        }
    088        nextPermutation = new ArrayList<>(collection);
    089    }
    090
    091    /**
    092     * Indicates if there are more permutation available.
    093     * @return true if there are more permutations, otherwise false
    094     */
    095    @Override
    096    public boolean hasNext() {
    097        return nextPermutation != null;
    098    }
    099
    100    /**
    101     * Returns the next permutation of the input collection.
    102     * @return a list of the permutator's elements representing a permutation
    103     * @throws NoSuchElementException if there are no more permutations
    104     */
    105    @Override
    106    public List<E> next() {
    107        if (!hasNext()) {
    108            throw new NoSuchElementException();
    109        }
    110
    111        // find the largest mobile integer k
    112        int indexOfLargestMobileInteger = -1;
    113        int largestKey = -1;
    114        for (int i = 0; i < keys.length; i++) {
    115            if (direction[i] && i < keys.length - 1 && keys[i] > keys[i + 1] ||
    116                !direction[i] && i > 0 && keys[i] > keys[i - 1]) {
    117                if (keys[i] > largestKey) { // NOPMD
    118                    largestKey = keys[i];
    119                    indexOfLargestMobileInteger = i;
    120                }
    121            }
    122        }
    123        if (largestKey == -1) {
    124            final List<E> toReturn = nextPermutation;
    125            nextPermutation = null;
    126            return toReturn;
    127        }
    128
    129        // swap k and the adjacent integer it is looking at
    130        final int offset = direction[indexOfLargestMobileInteger] ? 1 : -1;
    131        final int tmpKey = keys[indexOfLargestMobileInteger];
    132        keys[indexOfLargestMobileInteger] = keys[indexOfLargestMobileInteger + offset];
    133        keys[indexOfLargestMobileInteger + offset] = tmpKey;
    134        final boolean tmpDirection = direction[indexOfLargestMobileInteger];
    135        direction[indexOfLargestMobileInteger] = direction[indexOfLargestMobileInteger + offset];
    136        direction[indexOfLargestMobileInteger + offset] = tmpDirection;
    137
    138        // reverse the direction of all integers larger than k and build the result
    139        final List<E> nextP = new ArrayList<>();
    140        for (int i = 0; i < keys.length; i++) {
    141            if (keys[i] > largestKey) {
    142                direction[i] = !direction[i];
    143            }
    144            nextP.add(objectMap.get(Integer.valueOf(keys[i])));
    145        }
    146        final List<E> result = nextPermutation;
    147        nextPermutation = nextP;
    148        return result;
    149    }
    150
    151    @Override
    152    public void remove() {
    153        throw new UnsupportedOperationException("remove() is not supported");
    154    }
    155
    156}