1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44 public class PermutationIterator<E> implements Iterator<List<E>> {
45
46
47
48
49 private final int[] keys;
50
51
52
53
54 private final Map<Integer, E> objectMap;
55
56
57
58
59
60
61
62
63 private final boolean[] direction;
64
65
66
67
68
69 private List<E> nextPermutation;
70
71
72
73
74
75
76 public PermutationIterator(final Collection<? extends E> collection) {
77 Objects.requireNonNull(collection, "collection");
78 keys = new int[collection.size()];
79 direction = new boolean[collection.size()];
80 Arrays.fill(direction, false);
81 int value = 1;
82 objectMap = new HashMap<>();
83 for (final E e : collection) {
84 objectMap.put(Integer.valueOf(value), e);
85 keys[value - 1] = value;
86 value++;
87 }
88 nextPermutation = new ArrayList<>(collection);
89 }
90
91
92
93
94
95 @Override
96 public boolean hasNext() {
97 return nextPermutation != null;
98 }
99
100
101
102
103
104
105 @Override
106 public List<E> next() {
107 if (!hasNext()) {
108 throw new NoSuchElementException();
109 }
110
111
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) {
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
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
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 }