Integer Partition using an iterator 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&lt;String&gt; {
    /**
     * 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 &lt; this.size; i++) {
                sb.append(' ').append(String.valueOf(this.data[i]));
            }
            return sb.toString();
        }
    }

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

    private IntStack stack;

    public Partition(int n) {
        if (n &lt;= 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 &gt; 0; ones -= top) {
            stack.push(top &lt; 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());
        }
    }
}
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&lt;String&gt; 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 &lt; 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&lt;String&gt; {

    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 &lt;= 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 &lt; 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 &lt; 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] &lt;= 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 &lt; stacksize; i++) {
                sb.append(stack[i]).append(" ");
            }
//            System.out.println(sb.toString());
//          );
            return sb.toString().length();
        }
        int sz = 0;
        for(int i = from; i &lt;= target; i++) {
            stack[stacksize] = i;
            sz += recursivePartition(target-i, i, stack, stacksize + 1);
        }
        return sz;
    }

}