Class Combinations.LexicographicIterator

java.lang.Object
org.apache.commons.math3.util.Combinations.LexicographicIterator
All Implemented Interfaces:
Iterator<int[]>
Enclosing class:
Combinations

private static class Combinations.LexicographicIterator extends Object implements 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
    Description
    private final int[]
    c[1], ..., c[k] stores the next combination; c[k + 1], c[k + 2] are sentinels.
    private int
    Marker: smallest index such that c[j + 1] > j
    private final int
    Size of subsets returned by the iterator
    private boolean
    Return value for hasNext()
  • Constructor Summary

    Constructors
    Constructor
    Description
    LexicographicIterator(int n, int k)
    Construct a CombinationIterator to enumerate k-sets from n.
  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    int[]
    void
    Not supported.

    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 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 Details

    • LexicographicIterator

      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 Details

    • hasNext

      public boolean hasNext()
      Specified by:
      hasNext in interface Iterator<int[]>
    • next

      public int[] next()
      Specified by:
      next in interface Iterator<int[]>
    • remove

      public void remove()
      Not supported.
      Specified by:
      remove in interface Iterator<int[]>