1 /* Copyright 2011 Axel Kramer
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.Iterator;
20 import java.util.NoSuchElementException;
21
22 import org.hipparchus.exception.LocalizedCoreFormats;
23 import org.hipparchus.exception.MathIllegalArgumentException;
24
25 /**
26 * An iterator that generates all partitions of <code>n</code> elements, into <code>k</code> parts
27 * containing the number of elements in each part, based on Rosen's algorithm.
28 * <p>
29 * This is a copy of the class (with slight edits) with the same name from the
30 * <a href="https://github.com/axkr/symja_android_library">Symja Library</a>.
31 * The original file was published under the terms of the GPLV3 license,
32 * but the Hipparchus project was <a
33 * href="https://github.com/Hipparchus-Math/hipparchus/issues/197#issuecomment-1193259547">explicitly allowed</a>
34 * to include it relicensed to Apache V2.
35 * </p>
36 * <p>
37 * See Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill,
38 * 1991), pp. 284-286
39 * </p>
40 */
41 public class RosenNumberPartitionIterator implements Iterator<int[]> {
42
43 /** Number of elements. */
44 private final int n;
45
46 /** Subset/sample size. */
47 private final int k;
48
49 /** Work array. */
50 private int[] a;
51
52 /** Count of unique combinations. */
53 private long count;
54
55 /** Simple constructor.
56 * @param n the number of elements
57 * @param k divided into k parts
58 */
59 public RosenNumberPartitionIterator(final int n, final int k) {
60
61 this.n = n - 1;
62 this.k = k - 1;
63 if (k > n || k < 1) {
64 throw new MathIllegalArgumentException(LocalizedCoreFormats.OUT_OF_RANGE_SIMPLE, k, 1, n);
65 }
66
67 reset();
68
69 }
70
71 /**
72 * {@inheritDoc}
73 *
74 * @see java.util.Iterator#hasNext()
75 */
76 @Override
77 public final boolean hasNext() {
78 return count > 0;
79 }
80
81 /**
82 * {@inheritDoc}
83 *
84 * @see java.util.Iterator#next()
85 */
86 @Override
87 public final int[] next() {
88
89 if (count == 0) {
90 throw new NoSuchElementException();
91 }
92
93 // rosenNext start
94 if (a == null) {
95 this.a = new int[k];
96 for (int i = 0; i < k; ++i) {
97 this.a[i] = i;
98 }
99 } else {
100 int i = k - 1;
101 while (a[i] == n - k + i) {
102 i--;
103 }
104 final int t = ++a[i] - i++;
105 int j = i;
106 while (j < k) {
107 a[j] = t + j++;
108 }
109 }
110 --count;
111 // rosenNext end
112
113 final int kPlus1 = k + 1;
114 final int[] temp = new int[kPlus1];
115
116 for (int i = 0; i < kPlus1; i++) {
117 if (i == 0) {
118 temp[i] = a[i] + 1;
119 } else {
120 if (i == k) {
121 temp[i] = n - a[i - 1];
122 } else {
123 temp[i] = a[i] - a[i - 1];
124 }
125 }
126 }
127 return temp;
128 }
129
130 /** Reset this iterator to the start condition.
131 */
132 public void reset() {
133 count = 1;
134 for (int i = 0; i < k; ++i) {
135 count = count * (n - i) / (i + 1);
136 }
137 a = null;
138 }
139
140 }