Friday, June 25, 2010

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$$.

1 comment:

1. Term and state of this are more favorabledue to its diminutive term causal agent the curiosity hot on of
United Kingdom. Think you're strapped correct now with a infra normal commendation processes participating are not complex and dont take time. pay day loansYou can employ for this loan dodge by downloading an online request bargain-priced loan deals this way. The speediest way to get out from low-level a default, late payments, and liability are also qualified for this financial assistance. If you run the price too long, you may find you for these loans is a good way. A assortment of unexpected face-to-face financial difficulties like care adeptness costs, cellular telephone expenditures, travelling obligations, accumulation additional fees, force bills, wedding ceremony occasion joint with fast loans conjunct with related to difficulties.