org.apache.commons.math3.util

Class Combinations.LexicographicIterator

java.lang.Object

org.apache.commons.math3.util.Combinations.LexicographicIterator

All Implemented Interfaces:

java.util.Iterator<int[]>

Enclosing class:

Combinations

private static class Combinations.LexicographicIterator
extends java.lang.Object
implements java.util.Iterator<int[]>

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. If constructor arguments satisfy k == 0 or k >= n, no exception is generated, but the iterator is empty.

Field Summary

Fields

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 Summary

Constructors

Constructor and Description
Combinations.LexicographicIterator(int n, int k) Construct a CombinationIterator to enumerate k-sets from n.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	hasNext()
int[]	next()
void	remove() Not supported.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

k

private final int k

Size of subsets returned by the iterator

c

private final int[] c

c[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 more

Return value for hasNext()

j

private int j

Marker: smallest index such that c[j + 1] > j

Constructor Detail

Combinations.LexicographicIterator

public Combinations.LexicographicIterator(int n,
                                  int k)

Construct a CombinationIterator to enumerate k-sets from n.

NOTE: If k === 0 or k >= n, the Iterator will be empty (that is, hasNext() will return false immediately.

Parameters:

n - size of the set from which subsets are enumerated

k - size of the subsets to enumerate

Method Detail

hasNext

public boolean hasNext()

Specified by:

hasNext in interface java.util.Iterator<int[]>

next

public int[] next()

Specified by:

next in interface java.util.Iterator<int[]>

remove

public void remove()

Not supported.

Specified by:

remove in interface java.util.Iterator<int[]>