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.lang.reflect.Array;
20 import java.util.ArrayDeque;
21 import java.util.ArrayList;
22 import java.util.Iterator;
23 import java.util.List;
24 import java.util.NoSuchElementException;
25 import java.util.Queue;
26
27 /** Iterator for generating partitions.
28 * <p>
29 * This class implements the iterative algorithm described in
30 * <a href="https://academic.oup.com/comjnl/article/32/3/281/331557">Short Note:
31 * A Fast Iterative Algorithm for Generating Set Partitions</a>
32 * by B. Djokić, M. Miyakawa, S. Sekiguchi, I. Semba, and I. Stojmenović
33 * (The Computer Journal, Volume 32, Issue 3, 1989, Pages 281–282,
34 * <a href="https://doi.org/10.1093/comjnl/32.3.281">https://doi.org/10.1093/comjnl/32.3.281</a>
35 * </p>
36 * @param <T> type of the elements
37 * @since 2.2
38 */
39 class PartitionsIterator<T> implements Iterator<List<T>[]> {
40
41 /** List to partition. */
42 private final List<T> list;
43
44 /** Number of elements to partition. */
45 private final int n;
46
47 /** Mapping from elements indices to parts indices. */
48 private final int[] partIndex;
49
50 /** Backtracking array. */
51 private final int[] backTrack;
52
53 /** Current part index. */
54 private int r;
55
56 /** Current backtrack index. */
57 private int j;
58
59 /** Pending parts already generated. */
60 private final Queue<List<T>[]> pending;
61
62 /** Indicator for exhausted partitions. */
63 private boolean exhausted;
64
65 /** Simple constructor.
66 * @param list list to partition
67 */
68 PartitionsIterator(final List<T> list) {
69
70 this.list = list;
71 this.n = list.size();
72 this.partIndex = new int[list.size()];
73 this.backTrack = new int[list.size() - 1];
74 this.r = 0;
75 this.j = 0;
76 this.pending = new ArrayDeque<>(n);
77
78 // generate a first set of partitions
79 generate();
80
81 }
82
83 /** Generate one set of partitions.
84 */
85 private void generate() {
86
87 // put elements in the first part
88 while (r < n - 2) {
89 partIndex[++r] = 0;
90 backTrack[++j] = r;
91 }
92
93 // generate partitions
94 for (int i = 0; i < n - j; ++i) {
95
96 // fill-up final element
97 partIndex[n - 1] = i;
98
99 // count the number of parts in this partition
100 int max = 0;
101 for (final int index : partIndex) {
102 max = FastMath.max(max, index);
103 }
104
105 // prepare storage
106 @SuppressWarnings("unchecked")
107 final List<T>[] partition = (List<T>[]) Array.newInstance(List.class, max + 1);
108 for (int k = 0; k < partition.length; ++k) {
109 partition[k] = new ArrayList<>(n);
110 }
111
112 // distribute elements in the parts
113 for (int k = 0; k < partIndex.length; ++k) {
114 partition[partIndex[k]].add(list.get(k));
115 }
116
117 // add the generated partition to the pending queue
118 pending.add(partition);
119
120 }
121
122 // backtrack to generate next partition
123 r = backTrack[j];
124 partIndex[r]++;
125 if (partIndex[r] > r - j) {
126 --j;
127 }
128
129 // keep track of end of generation
130 exhausted = r == 0;
131
132 }
133
134 /** {@inheritDoc} */
135 @Override
136 public boolean hasNext() {
137 return !(exhausted && pending.isEmpty());
138 }
139
140 /** {@inheritDoc} */
141 @Override
142 public List<T>[] next() {
143
144 if (pending.isEmpty()) {
145 // we need to generate more partitions
146 if (exhausted) {
147 throw new NoSuchElementException();
148 }
149 generate();
150 }
151
152 return pending.remove();
153
154 }
155
156 }