Class Combinations.LexicographicIterator
java.lang.Object
org.apache.commons.numbers.combinatorics.Combinations.LexicographicIterator
- All Implemented Interfaces:
Iterator<int[]>
- Enclosing class:
Combinations
Lexicographic combinations iterator.
Implementation follows Algorithm T in The Art of Computer Programming Internet Draft (PRE-FASCICLE 3A), "A Draft of Section 7.2.1.3 Generating All Combinations, D. Knuth, 2004.
The degenerate cases k == 0
and k == n
are NOT handled by this
implementation. It is assumed that n > k > 0
.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final int[]
c[1], ..., c[k] stores the next combination; c[k + 1], c[k + 2] are sentinels.private int
Marker: smallest index such thatc[j + 1] > j
.private final int
Size of subsets returned by the iterator.private boolean
Return value forhasNext()
. -
Constructor Summary
ConstructorsConstructorDescriptionLexicographicIterator
(int n, int k) Construct a CombinationIterator to enumeratek
-sets from a set of sizen
. -
Method Summary
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface java.util.Iterator
forEachRemaining
-
Field Details
-
k
private final int kSize of subsets returned by the iterator. -
c
private final int[] cc[1], ..., c[k] stores the next combination; c[k + 1], c[k + 2] are sentinels.Note that c[0] is "wasted" but this makes it a little easier to follow the code.
-
more
private boolean moreReturn value forhasNext()
. -
j
private int jMarker: smallest index such thatc[j + 1] > j
.
-
-
Constructor Details
-
LexicographicIterator
LexicographicIterator(int n, int k) Construct a CombinationIterator to enumeratek
-sets from a set of sizen
.NOTE: It is assumed that
n > k > 0
.- Parameters:
n
- Size of the set from which subsets are enumerated.k
- Size of the subsets to enumerate.
-
-
Method Details