1 /*
2 * Licensed to the Hipparchus project 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 Hipparchus project 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 * https://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.hipparchus.util;
18
19 import java.util.ArrayList;
20 import java.util.Iterator;
21 import java.util.List;
22 import java.util.NoSuchElementException;
23
24 /** Iterator for generating permutations.
25 * <p>
26 * This class implements the Steinhaus–Johnson–Trotter algorithm
27 * with Even's speedup
28 * <a href="https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm">Steinhaus–Johnson–Trotter algorithm</a>
29 * </p>
30 * @param <T> type of the elements
31 * @since 2.2
32 */
33 class PermutationsIterator<T> implements Iterator<List<T>> {
34
35 /** Current permuted list. */
36 private final List<T> permuted;
37
38 /** Value markers. */
39 private final int[] value;
40
41 /** Directions markers. */
42 private final int[] direction;
43
44 /** Indicator for exhausted partitions. */
45 private boolean exhausted;
46
47 /** Simple constructor.
48 * @param list list to permute (will not be touched)
49 */
50 PermutationsIterator(final List<T> list) {
51
52 this.permuted = new ArrayList<>(list);
53
54 this.value = new int[list.size()];
55 this.direction = new int[list.size()];
56 for (int i = 0; i < value.length; ++i) {
57 value[i] = i;
58 direction[i] = i == 0 ? 0 : -1;
59 }
60
61 exhausted = false;
62
63 }
64
65 /** {@inheritDoc} */
66 @Override
67 public boolean hasNext() {
68 return !exhausted;
69 }
70
71 /** {@inheritDoc} */
72 @Override
73 public List<T> next() {
74
75 if (exhausted) {
76 throw new NoSuchElementException();
77 }
78
79 // the value that will be returned at the end
80 final List<T> current = new ArrayList<>(permuted);
81
82 // select element to swap for next permutation
83 int selectedIndex = -1;
84 int selectedValue = -1;
85 int selectedDirection = -1;
86 for (int i = 0; i < value.length; ++i) {
87 if (direction[i] != 0 && value[i] > selectedValue) {
88 selectedIndex = i;
89 selectedValue = value[i];
90 selectedDirection = direction[i];
91 }
92 }
93 if (selectedIndex < 0) {
94 exhausted = true;
95 } else {
96
97 // prepare next permutation
98
99 // swap selected and peer elements
100 final int selectedPeer = selectedIndex + selectedDirection;
101 final T tmp = permuted.get(selectedIndex);
102 permuted.set(selectedIndex, permuted.get(selectedPeer));
103 permuted.set(selectedPeer, tmp);
104 value[selectedIndex] = value[selectedPeer];
105 value[selectedPeer] = selectedValue;
106 direction[selectedIndex] = direction[selectedPeer];
107 if (selectedPeer == 0 || selectedPeer == permuted.size() - 1 ||
108 value[selectedPeer + selectedDirection] > selectedValue) {
109 // we cannot move anymore
110 direction[selectedPeer] = 0;
111 } else {
112 // we will continue moving in the same direction
113 direction[selectedPeer] = selectedDirection;
114 }
115
116 // enable motion again for greater elements, towards selected one
117 for (int i = 0; i < selectedIndex; ++i) {
118 if (value[i] > selectedValue) {
119 direction[i] = +1;
120 }
121 }
122 for (int i = selectedIndex + 1; i < value.length; ++i) {
123 if (value[i] > selectedValue) {
124 direction[i] = -1;
125 }
126 }
127
128 }
129
130 return current;
131
132 }
133
134 }