Class Combinations.LexicographicIterator

java.lang.Object
org.apache.commons.numbers.combinatorics.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. It is assumed that n > k > 0.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final 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 final int
    k
    Size of subsets returned by the iterator.
    private boolean
    more
    Return value for hasNext().

  • Constructor Summary

    Constructors
    Constructor
    Description
    LexicographicIterator(int n, int k)
    Construct a CombinationIterator to enumerate k-sets from a set of size n.

  • Method Summary

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

    Methods inherited from class Object

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

    Methods inherited from interface 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 a set of size n.

      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

    • 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[]>