Iterating Monotonic Decreasing Sequences

In this post I will show an algorithm to iterate over all monotonic decreasing sequences of non-negative integers of length at most \(m\) and height \(n\).

In a previous post I counted the number of monotonic decreasing sequences of length at most \(m\) and height \(n\). In order to study these objects it is nice If you can generate them all on a computer.

Furthermore, it would be nice to "visit" them one at a time. This cuts down on memory consumption, because then only one sequence has to be in memory at any time. In this blog post I will outline an algorithm to generate all the monotonic decreasing sequences of non-negative integers of length at most \(m\) and height \(n\) in lexicographical order.

In order to generate all sequences, one has to start somewhere. A moments thought shows that the smallest monotonic decreasing sequence of any length is a run of consecutive zeroes i.e.

0,0,0,...,0

So our algorithm initially starts by returning the zero sequence of the specified length. Then the game is on. By only referencing the current sequence one has to determine the next sequence to produce. For instance what would be the sequence following this sequence 4,3,3,1,1,1?

After some reflection is is clear that the tail of 1's can be changed in to 2,0,0. In order to see this, notice that the lexicographical order favours changes at the end of the sequence. And the nature of the monotonic decreasing sequences forces us to increase a constant tail at the beginning. We also already noticed that the zeroes sequence is the smallest sequence of any length.

So the following java code gives a correct iterator of monotonic decreasing sequences of non-negative integers. A nice trick is used to simplified. Pre-pending ∞ to the sequence no further precautions are needed for the logic at the start of the sequence.

package org.effrafax.combinatorial.iterator;

import java.util.Arrays;
import java.util.Iterator;

public class MonotonicDecreasingIterator implements Iterator<int[]> {

  private static final int INFINITY = Integer.MAX_VALUE;
  private final int height;
  private final int[] sequence;

  public MonotonicDecreasingIterator(int length, int height) {

    this.sequence = startSequence(length);
    this.height = height;
  }

  private int[] startSequence(int length) {

    int[] startSequence = new int[length + 1];
    Arrays.fill(startSequence, 0);
    startSequence[0] = INFINITY;
    return startSequence;
  }

  @Override
  public boolean hasNext() {

    return sequence[1] <= height;
  }

  @Override
  public int[] next() {

    int[] copy = Arrays.copyOfRange(sequence, 1, sequence.length);
    produceNext();

    return copy;
  }

  private void produceNext() {

    int index = findLatestStep();
    increaseAt(index);
  }

  private int findLatestStep() {

    int index = sequence.length - 1;
    while (sequence[index] == sequence[index - 1]) {
      index--;
    }
    return index;
  }

  private void increaseAt(int index) {

    sequence[index]++;
    Arrays.fill(sequence, index + 1, sequence.length, 0);
  }

  @Override
  public void remove() {

    throw new UnsupportedOperationException();
  }
}

In this blog I showed an algorithm to iterate over all the monotonic decreasing sequences of non-negative integers of length at most \(m\) and height \(n\).