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}