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}