private static class Combinations.LexicographicIterator
extends java.lang.Object
implements java.util.Iterator<int[]>
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. If constructor arguments satisfy k == 0
or k >= n
, no exception is generated, but the iterator is empty.
Modifier and Type | Field and Description |
---|---|
private int[] |
c
c[1], ..., c[k] stores the next combination; c[k + 1], c[k + 2] are
sentinels.
|
private int |
j
Marker: smallest index such that c[j + 1] > j
|
private int |
k
Size of subsets returned by the iterator
|
private boolean |
more
Return value for
hasNext() |
Constructor and Description |
---|
LexicographicIterator(int n,
int k)
Construct a CombinationIterator to enumerate k-sets from n.
|
Modifier and Type | Method and Description |
---|---|
boolean |
hasNext() |
int[] |
next() |
void |
remove()
Not supported.
|
private final int k
private final int[] c
Note that c[0] is "wasted" but this makes it a little easier to follow the code.
private boolean more
hasNext()
private int j
public LexicographicIterator(int n, int k)
NOTE: If k === 0
or k >= n
, the Iterator will be empty
(that is, hasNext()
will return false
immediately.
n
- size of the set from which subsets are enumeratedk
- size of the subsets to enumerateCopyright (c) 2003-2016 Apache Software Foundation