Class 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. It is assumed that n > k > 0.

    • Field Summary

      Fields 
      Modifier and Type Field 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 Description
      LexicographicIterator​(int n, int k)
      Construct a CombinationIterator to enumerate k-sets from a set of size n.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method 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
      • Methods inherited from interface java.util.Iterator

        forEachRemaining
    • 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

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