Integer Partition using an iterator

Question

I tried implementing Integer Partition (enumerating all possible sets of whole numbers whose sum is a given integer).

Looking at @rolfl's answer, I reasoned that with a stack data structure, we shouldn't need to use recursion, since recursion implicitly stores state in the call stack. I also tried to address @JeffVanzella's criticism about separation of concerns by converting the class into an iterator.

My solution ended up being a bit more monstrous than I had anticipated. It looks nothing like the elegant original, and runs more slowly too. Therefore, I suspect that a better iterative solution is possible.

import java.util.Iterator;

public class Partition implements Iterator<String> {
    /**
     * Fixed-capacity stack of ints.  As used in Partition.next(), the
     * invariant is that elements towards the top of the stack are never
     * larger than elements underneath.  (In other words, the array
     * elements are nonincreasing.
     */
    private static class IntStack {
        private int[] data;
        private int size;

        IntStack(int capacity) {
            this.data = new int[capacity];
            this.size = 0;
        }

        public void push(int datum) {
            this.data[this.size++] = datum;
        }

        public int pop() {
            return this.data[--this.size];
        }

        public boolean isEmpty() {
            return this.size == 0;
        }

        /**
         * Returns the elements as a space-delimited string.
         */
        public String toString() {
            // toString() of an empty stack is never used in practice...
            if (this.isEmpty()) return "";

            StringBuilder sb = new StringBuilder(String.valueOf(this.data[0]));
            for (int i = 1; i < this.size; i++) {
                sb.append(' ').append(String.valueOf(this.data[i]));
            }
            return sb.toString();
        }
    }

    //////////////////////////////////////////////////////////////////////

    private IntStack stack;

    public Partition(int n) {
        if (n <= 0) throw new IllegalArgumentException();
        stack = new IntStack(n);
        stack.push(n);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    public String next() {
        String retval = stack.toString();

        int top;
        int ones = 0;

        // Count the ones at the top of the stack. Stop at "top", which is the
        // next element other than a 1.
        while (1 == (top = stack.pop())) {
            if (stack.isEmpty()) {
                // n has been completely partitioned into n ones.  All done!
                return retval;
            }
            ones++;
        }

        // Transfer 1 from top to ones, then write out the remainder in as few
        // numbers as possible, observing the stack invariant that entries
        // must be nonincreasing.
        stack.push(--top);
        for (ones++; ones > 0; ones -= top) {
            stack.push(top < ones ? top : ones);
        }
        return retval;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    public static void main(String[] args)
    {
        int n = Integer.parseInt(args[0]);
        Partition p = new Partition(n);
        while (p.hasNext()) {
            System.out.println(p.next());
        }
    }
}

Answer 1

I am not sure how to 'review' your code in this case.... I have a sense of 'competition' here, and the moment performance enters the equation, there are things I just know are going to be slower, but I cannot always explain why.....

I think often times it simply comes down to primitives vs. Object creation.... whenever that happens things slow down.

I have put together a 'competing' solution, and it uses tricks I have learned over the years... tricks I feel, for the most part, lead to 'fast' code. I have been accused of 'premature optimization' when I do these things, but, it tends to work for me.... ;-)

printing Strings is never going to be a good measure of performance, so I have taken three solutions: the recursive solution I suggested in the earlier post. Your solution using the iterator, and then a 'competing' iterator performance.

So, in my benchmarks, this iterative process is about 5 times faster than yours.... (excluding the System.out.println()):

here are my results (times in milliseconds on my machine):

200_Success=2045.091 rolflIter=446.846=rolflRecur 2046.462011
200_Success=1737.469 rolflIter=573.900=rolflRecur 1521.951070
200_Success=1814.468 rolflIter=385.520=rolflRecur 1499.896568
200_Success=1714.592 rolflIter=333.105=rolflRecur 1372.042103
200_Success=1799.969 rolflIter=383.033=rolflRecur 1520.779467
200_Success=1676.415 rolflIter=336.651=rolflRecur 1474.669545
200_Success=1978.581 rolflIter=407.804=rolflRecur 1417.124248
200_Success=1665.783 rolflIter=343.939=rolflRecur 1375.178203
200_Success=1654.083 rolflIter=331.607=rolflRecur 1369.912767
200_Success=1654.958 rolflIter=339.234=rolflRecur 1369.170302

Edit: New results ... note, 200_success is also running faster here.... Hate performance variances ... probably a Windows/Intel CPU frequency thing.

200_Success=1463.484 rolflIter=624.754 rolflRecur=1777.548864
200_Success=1304.401 rolflIter=302.086 rolflRecur=1492.951479
200_Success=1577.132 rolflIter=367.537 rolflRecur=1485.176134
200_Success=1230.959 rolflIter=266.068 rolflRecur=1389.742206
200_Success=1230.445 rolflIter=269.587 rolflRecur=1382.473980
200_Success=1220.637 rolflIter=269.352 rolflRecur=1376.292369
200_Success=1204.206 rolflIter=266.920 rolflRecur=1369.920239
200_Success=1201.280 rolflIter=264.481 rolflRecur=1365.711999
200_Success=1204.419 rolflIter=262.047 rolflRecur=1368.854637
200_Success=1251.656 rolflIter=264.030 rolflRecur=1416.935596

Main class:

package comp;

import java.util.Iterator;

public class RunParts {

    private static int charsIn(Iterator<String> iter) {
        int chars = 0;
        while (iter.hasNext()) {
            chars += iter.next().length();
        }
        return chars;
    }

    public static void main(String[] args) {
        final int target = Integer.parseInt(args[0]);
        long[] nanos = new long[3];
        int[] charlen = new int[3];
        for (int i = 0; i < 10; i++) {
            System.gc();
            nanos[0] = System.nanoTime();
            charlen[0] = charsIn(new Partition(target));
            nanos[0] = System.nanoTime() - nanos[0];

            System.gc();
            nanos[1] = System.nanoTime();
            charlen[1] = charsIn(new PartitionRLIter(target));
            nanos[1] = System.nanoTime() - nanos[1];

            System.gc();
            nanos[2] = System.nanoTime();
            charlen[2] = PartitionRLRecur.partitionRL(target);
            nanos[2] = System.nanoTime() - nanos[2];

            System.out.printf("200_Success=%.3f rolflIter=%.3f rolflRecur=%3f\n",
                    nanos[0] / 1000000.0, nanos[1] / 1000000.0, nanos[2] / 1000000.0);
        }

    }

}

Your solution is above (I have left it called 'Partition').

Then my iterative solution is...

EDIT: I have edited my solution to add comments. As I was adding the comments I realized that a lot of the logic in the advance() method was related to setup of the system. I have moved the setup to the constructor, and by verifying a couple of things, I am now able to guarantee a couple of behavioral advantages that mean I don't need a few of the loops in the system. I have updated my results now as well.

package comp;

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

public class PartitionRLIter implements Iterator<String> {

    private final int[] stack;
    private final int[] outpos;
    private final StringBuilder outstring;
    private final int limit;
    private boolean hasnext = true;
    private int spos = 0;

    public PartitionRLIter(int n) {
        if (n <= 0) throw new IllegalArgumentException();
        limit = n;
        stack = new int[limit];
        outpos = new int[limit];
        // NOTE THAT THE CONSTRUCTOR NOW MANUALLY INITIALIZES THE SYSTEM
        outstring = new StringBuilder(limit * 2); // worst case is "1 1 1 1 1 ...";
        Arrays.fill(stack, 1);
        for (int i = 0; i < limit; i++) {
            outpos[i] = outstring.length();
            outstring.append("1 ");
        }
        hasnext = true;
        spos = limit - 1;
    }

    @Override
    public boolean hasNext() {
        return hasnext;
    }

    @Override
    public String next() {
        if (!hasnext)
            throw new NoSuchElementException();

        try {
            return outstring.substring(0, outstring.length() - 1);
        } finally {
            hasnext = advance();
        }
    }

    private final boolean advance() {
        // advance() keeps four 'stack-like' variables in sync
        // advance() will only ever be called when the current system has a valid answer
        //
        // **stack** contains the digits that get summed... It is the 'real stack'. The constructor initializes it to all 1's.
        //
        // **spos** is our depth in the stack.
        //
        // the **outstring** is a StringBuilder that is kept in sync with the actual stack...
        //     reusing the StringBuilder makes it much faster... but we need to manage it like a stack.
        //     when you go deeper in the stack, the outstring has values added to it,
        //     when you come back up, the outstring is truncated to remove unneeded characters.
        //     very much like push and pop operations (except at the end of the string, not the front)
        //
        // the **outpos** is the array of integer positions in the outstring StringBuffer that
        //     keeps track of where the outstring should be truncated at each level.
        //     this is what allows working push/pop on the outstring.
        //

        // back up..... the stack, we always know we are already at the limit.
        // pop the value off (keep sum in sync).
        int sum = limit - stack[spos];
        if (--spos < 0) {
            // we ran out of things to do, there's no more possibilities.
            return false;
        }

        // on the previous level, we increment....
        // we can never overflow the previous level because
        // of the way the math works (we would not have a next level if we can't increment this one).
        stack[spos] ++;
        sum++;

        // pop the previous value(s) off the stack representation.
        // outpos[spos] contains the character position in the output representing
        // our current depth.
        outstring.setLength(outpos[spos]);

        // check to see whether adding a new level of depth will work.....
        // the new level will have the same value as the stack's current value...
        while (sum + stack[spos] <= limit) {
            // yes, the new level will work.
            // update our string stack, sum, and record the character position of the outstring.
            outstring.append(stack[spos]).append(" ");
            sum+= stack[spos];
            stack[spos + 1] = stack[spos];
            spos++;
            outpos[spos]=outstring.length();
        }

        // take the new depth and increment it (if needed) to the limit.
        stack[spos] += limit - sum;
        outstring.append(stack[spos]).append(" ");
        return true;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

Finally, my Recursive solution is (note, it has been modified to return the string length, not the string itself):

package comp;


public class PartitionRLRecur {

    public static int partitionRL(final int n)
    {
        return recursivePartition(n, 1, new int[n], 0);
    }

    private static int recursivePartition(final int target, final int from, final int[] stack, final int stacksize)
    {
        if(target == 0) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < stacksize; i++) {
                sb.append(stack[i]).append(" ");
            }
//            System.out.println(sb.toString());
//          );
            return sb.toString().length();
        }
        int sz = 0;
        for(int i = from; i <= target; i++) {
            stack[stacksize] = i;
            sz += recursivePartition(target-i, i, stack, stacksize + 1);
        }
        return sz;
    }

}

Answer 2

Thanks to @rolfl for showing the way. Besides the performance gains, he also improved next() by throwing NoSuchElementException and by moving most of the code into advance().

I've concluded that his solution is faster due to three factors:

1. Caching the StringBuilder.
2. Enumerating the values in ascending rather than descending order. It turns out that putting the smaller numbers at the end results in greater churn of the stack. When the size of the stack keeps changing, the cached StringBuilder is less effective.
3. Raw array access instead of using IntStack.

Of those three factors, (3) has only a minor effect. However, if you delegate all the tedious bookkeeping to IntStack, the algorithm in advance() becomes quite understandable. Here is an implementation that reintroduces a smarter IntStack to PartitionRLIter.

import java.util.Iterator;
import java.util.NoSuchElementException;

public class PartitionRLIter2 implements Iterator<String> {

    private static class IntStack {
        private int[] data;
        private int size;

        private static final String DELIM = " ";

        // sum, str, and strlen store redundant state for performance.

        // Sum of all data
        private int sum;

        // Each element of data followed by DELIM
        private StringBuilder str;

        // For each i, the length of the relevant portion of str when size = i
        private int[] strlen;

        IntStack(int capacity) {
            this.data = new int[capacity];

            // Likely worst case is "1 1 ... 1 "
            this.str = new StringBuilder(capacity * (1 + DELIM.length()));
            this.strlen = new int[capacity];
        }

        public void fill(int datum) {
            for (this.size = 0; this.size < this.data.length; this.size++) {
                this.data[this.size] = datum;
                this.strlen[this.size] = this.str.length();
                this.str.append(String.valueOf(datum)).append(DELIM);
            }
            this.sum = datum * this.size;
        }

        public void push(int datum) {
            this.strlen[this.size] = this.str.length();
            this.data[this.size++] = datum;
            this.sum += datum;
            this.str.append(String.valueOf(datum)).append(DELIM);
        }

        public int pop() {
            int datum = this.data[--this.size];
            this.sum -= datum;
            this.str.setLength(this.strlen[this.size]);
            return datum;
        }

        /**
         * Shortcut for push(i + pop()), peek()
         */
        public int incr(int i) {
            if (i != 0) {
                int datum = this.data[this.size - 1] += i;
                this.sum += i;
                this.str.setLength(this.strlen[this.size - 1]);
                this.str.append(String.valueOf(datum)).append(DELIM);
            }
            return this.data[this.size - 1];
        }

        public boolean isEmpty() {
            return this.size == 0;
        }

        public int sum() {
            return this.sum;
        }

        public String toString() {
            return this.str.substring(0, this.str.length() - DELIM.length());
        }
    }

    //////////////////////////////////////////////////////////////////////

    private final IntStack stack;
    private final int limit;

    public PartitionRLIter2(int n) {
        if (n <= 0) throw new IllegalArgumentException();
        this.limit = n;
        this.stack = new IntStack(limit);
        this.stack.fill(1);
    }

    @Override
    public boolean hasNext() {
        return !this.stack.isEmpty();
    }

    @Override
    public String next() {
        if (this.stack.isEmpty()) {
            throw new NoSuchElementException();
        }
        try {
            return this.stack.toString();
        } finally {
            advance();
        }
    }

    private final void advance() {
        if (this.stack.pop() == this.limit) {
            // All the numbers have been gathered into the original
            // number.  That's all, folks!
            return;
        }

        // Increment the previous level.  We can never overflow because the
        // previous pop decremented the sum by at least one.
        int top = this.stack.incr(1);

        // Duplicate the top of the stack as many times as possible.
        while (this.stack.sum() + top <= this.limit) {
            this.stack.push(top);
        }

        // Increment the top to the limit (if needed).
        this.stack.incr(this.limit - this.stack.sum());

        // Note stack invariant: values are always nondecreasing going from the
        // base to the top.
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

}