Return to Answer

• 1

• 145.5k
• 22
• 190
• 478

• 145.5k
• 22
• 190
• 478

@Simon has shown you why the code is slow, that you may have underestimated the enormity of the output. I agree with his points completely, and won't reiterate them.

Instead, I'll suggest an alternative solution, based largely on a previous integer partition question on Code Review. That question called for an exhaustive integer partition (x_i listed in monotonically nondecreasing order), whereas this question calls for a "unique" integer partition (x_i listed in monotonically increasing order). The changes required to the code are minimal, once you figure out the new algorithm.

Running the code below for n = 150, it produces 19406016 partitions in about a minute (not outputting to the console).

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MonotonicallyIncreasingPartition implements Iterator<int[]> {
 private static class IntStack {
 private int[] data;
 private int size;
 
 // sum stores redundant state for performance.
 // Sum of all data
 private int sum;
 IntStack(int capacity) {
 this.data = new int[capacity];
 }
 public void fill(int limit) {
 this.sum = 0;
 this.size = this.data.length;
 int datum = 1;
 for (int i = 0; i < this.size; i++) {
 if (i == this.size - 1) datum = limit - this.sum;
 this.data[i] = datum;
 this.sum += datum++;
 }
 }
 public void push(int datum) {
 this.data[this.size++] = datum;
 this.sum += datum;
 }
 public int peek() {
 return this.data[this.size - 1];
 }
 public int pop() {
 int datum = this.data[--this.size];
 this.sum -= datum;
 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;
 }
 return this.data[this.size - 1];
 }
 public boolean isEmpty() {
 return this.size == 0;
 }
 public int sum() {
 return this.sum;
 }
 public int[] toArray() {
 return Arrays.copyOf(this.data, this.size);
 }
 }
 //////////////////////////////////////////////////////////////////////
 private final IntStack stack;
 private final int limit;
 public MonotonicallyIncreasingPartition(int n) {
 if (n <= 0) throw new IllegalArgumentException();
 this.limit = n;
 int stackSize = (int)Math.floor((-1 + Math.sqrt(1 + 8 * this.limit)) / 2);
 this.stack = new IntStack(stackSize);
 this.stack.fill(this.limit);
 }
 @Override
 public boolean hasNext() {
 return !this.stack.isEmpty();
 }
 @Override
 public int[] next() {
 if (this.stack.isEmpty()) {
 throw new NoSuchElementException();
 }
 try {
 return this.stack.toArray();
 } 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;
 }
 // Push the smallest possible monotonically increasing numbers
 this.stack.incr(1);
 while (this.stack.peek() + 1 <= this.limit - this.stack.sum()) {
 this.stack.push(this.stack.peek() + 1);
 }
 // Increase the last number such that the sum is the limit
 this.stack.incr(this.limit - this.stack.sum());
 // Note stack invariant: values are always increasing going from the
 // base to the top.
 }
 @Override
 public void remove() {
 throw new UnsupportedOperationException();
 }
 public static void main(String[] args) {
 int limit = Integer.parseInt(args[0]);
 Iterator<int[]> part = new MonotonicallyIncreasingPartition(limit);
 while (part.hasNext()) {
 System.out.println(Arrays.toString(part.next()));
 }
 }
}

Note the following speed-enhancing features:

• It makes no attempt to store all of the results in one data structure. Instead, it produces an iterator that you can use to fetch one partition at a time.

• There is a simple iterative algorithm to produce the next partition based on the current one.

• The data structure being used internally is just a simple int[] array, which I've packaged in an inner class called IntStack. You can tell exactly how large an array you need to allocate based on n. The most you can break it up is as

  n = 1 + 2 + 3 + ... + x_max

  = x_max (x_max + 1) / 2

  By the quadratic equation,

   _________
   -1 ± √ 1 + 8 n
   x = —————————————————
   max 2
  

• No stringification or complicated lookups involved in the partitioning algorithm itself. It merely makes decisions based on the top two numbers on the stack.