1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections4.iterators;
18
19 import java.util.ArrayList;
20 import java.util.Arrays;
21 import java.util.Collection;
22 import java.util.HashMap;
23 import java.util.Iterator;
24 import java.util.List;
25 import java.util.Map;
26 import java.util.NoSuchElementException;
27 import java.util.Objects;
28
29 /**
30 * This iterator creates permutations of an input collection, using the
31 * Steinhaus-Johnson-Trotter algorithm (also called plain changes).
32 * <p>
33 * The iterator will return exactly n! permutations of the input collection.
34 * The {@code remove()} operation is not supported, and will throw an
35 * {@code UnsupportedOperationException}.
36 * </p>
37 * <p>
38 * NOTE: in case an empty collection is provided, the iterator will
39 * return exactly one empty list as result, as 0! = 1.
40 * </p>
41 *
42 * @param <E> the type of the objects being permuted
43 * @since 4.0
44 */
45 public class PermutationIterator<E> implements Iterator<List<E>> {
46
47 /**
48 * Permutation is done on these keys to handle equal objects.
49 */
50 private final int[] keys;
51
52 /**
53 * Mapping between keys and objects.
54 */
55 private final Map<Integer, E> objectMap;
56
57 /**
58 * Direction table used in the algorithm:
59 * <ul>
60 * <li>false is left</li>
61 * <li>true is right</li>
62 * </ul>
63 */
64 private final boolean[] direction;
65
66 /**
67 * Next permutation to return. When a permutation is requested
68 * this instance is provided and the next one is computed.
69 */
70 private List<E> nextPermutation;
71
72 /**
73 * Standard constructor for this class.
74 * @param collection the collection to generate permutations for
75 * @throws NullPointerException if coll is null
76 */
77 public PermutationIterator(final Collection<? extends E> collection) {
78 Objects.requireNonNull(collection, "collection");
79 keys = new int[collection.size()];
80 direction = new boolean[collection.size()];
81 Arrays.fill(direction, false);
82 int value = 1;
83 objectMap = new HashMap<>();
84 for (final E e : collection) {
85 objectMap.put(Integer.valueOf(value), e);
86 keys[value - 1] = value;
87 value++;
88 }
89 nextPermutation = new ArrayList<>(collection);
90 }
91
92 /**
93 * Indicates if there are more permutation available.
94 * @return true if there are more permutations, otherwise false
95 */
96 @Override
97 public boolean hasNext() {
98 return nextPermutation != null;
99 }
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 }