Optimizing unique partitions of integers

Question

I am working on a project involving the unique partitioning of integers. I.e. I am looking to have all of the partitions of n = x₁ + x₂ + x₃ + ... + x_k, where x_i = x_j implies i = j.

For example, if I give my code input of 10, I want to have as output (in an ArrayList<ArrayList<BigInteger>>) the following:

[[1, 2, 3, 4], [2, 3, 5], [1, 4, 5], [1, 3, 6], [4, 6], [1, 2, 7], [3, 7], [2, 8], [1, 9], [10]]

Note that I don't have [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], etc. because these have duplicate entries.

The problem is, once I try to get all of the unique partitions of numbers greater than 70 or so, it starts to take a noticeable amount of time. Further, this shouldn't be a particularly slow algorithm.

The class is below:

import java.math.*;
import java.util.*;


public class UniquePartition {

    private BigInteger n;
    private ArrayList<ArrayList<BigInteger>> allPartitions;

    //Constructs the object with integer. Sets the target and then calculates partitions.
    public UniquePartition(int num) {
        n = new BigInteger(String.valueOf(num));
        allPartitions = new ArrayList<ArrayList<BigInteger>>();
        allPartitions = findPartitions();
    }   

    //Constructs the object. Sets the target and then calculates partitions.
    public UniquePartition(BigInteger num) {
        n = num;
        allPartitions = new ArrayList<ArrayList<BigInteger>>();
        allPartitions = findPartitions();
    }

    //Returns partitions without calculating them.
    public ArrayList<ArrayList<BigInteger>> getPartitions() {
        return allPartitions;
    }

    //Returns the nth partition without calculating them.
    public ArrayList<BigInteger> getPartitionN(int n) {
    //  ArrayList<ArrayList<BigInteger>> partitions = new ArrayList<ArrayList<BigInteger>>();
        return allPartitions.get(n);
    }

    // Returns an ArrayList containing ArrayLists, each of which is a single partition. Should never be called, otherwise
    // will redo calculation.
    public ArrayList<ArrayList<BigInteger>> findPartitions() {
        ArrayList<String> pS = new ArrayList<String>();
        pS = findPartitions(pS,n,n,"");

        for(int i=0;i<pS.size();i++) {
            ArrayList<BigInteger> partition = new ArrayList<BigInteger>();
            String line[] = (pS.get(i)).split(" ");
            for (String entry: line) {
                BigInteger num = new BigInteger(entry);
                partition.add(num);
            }
            allPartitions.add(partition);
        }

        return allPartitions;
    }

    //Stores the partitions in an ArrayList<String>. Never used alone. getAllPartitions() is the driver for this method.
    public ArrayList<String> findPartitions(ArrayList<String> p, BigInteger target, BigInteger maxValue, String suffix) {
        if (target.equals(BigInteger.ZERO)) {
          //            System.out.println(suffix);
            p.add(suffix);
        }
        else {
            if (maxValue.compareTo(BigInteger.ONE) > 0)
                findPartitions(p, target, maxValue.subtract(BigInteger.ONE), suffix);
            if (maxValue.compareTo(target)<=0 && !containsInteger(maxValue,suffix))
                findPartitions(p, target.subtract(maxValue), maxValue, maxValue + " " + suffix);
        }
        return p;
    }

    //Checks if String s contains the BigInteger n. If so, return true, otherwise return false.
    public boolean containsInteger(BigInteger n, String s) {
        boolean b = false;
        String line[] = s.split(" ");
        for(String entry: line) {
            if(entry == "")
                entry = "0";
            BigInteger BI = new BigInteger(entry);
            if(n.equals(BI))
                b = true;
        }
        return b;
    }

    //Returns string with all partitions.
    public String toString() {

        String output = "";     
        for(int i = 0;i<allPartitions.size();i++) {
            for(int j=0; j<(allPartitions.get(i)).size();j++) {
                output = output + (allPartitions.get(i)).get(j).toString()+" ";
            }
            output = output + "\n";
        }
        return output;
    }

    //Returns string with kth partition.
    public String toString(int k) {

        String output = "";     
        for(int j=0; j<(allPartitions.get(k)).size();j++) {
            output = output + (allPartitions.get(k)).get(j).toString()+" ";
        }
        return output;
    }
}

My driver class is below:

import java.math.*;
import java.util.*;

public class test {
    public static void main(String[] args) {
        long nanos =0;
        int target = TARGET;

        System.gc();
        nanos = System.nanoTime();
        UniquePartition part = new UniquePartition(target);
        nanos = System.nanoTime() - nanos;

        System.out.println("Time taken to calculate: "+nanos/1000000.0+"ms");
    }
}

So the question is, is there any way that I can improve the speed of this code? I'm looking to be able to search partitions of very large numbers in a reasonable period of time (as you can tell from the BigInteger constructor!). Is that unreasonable to expect? The algorithm itself doesn't seem to be slow... or is it? Any help would be appreciated!

Answer 1

Yes, it is unreasonable to expect this approach to be "fast".

This answer will focus on... drumroll, please!

Why your current approach is slow

The reason for why it is unreasonable to expect this approach to be fast can be shown simply by adding a private int calls; field to your class and increasing it at the beginning of your findPartitions(ArrayList<String> p, BigInteger target, BigInteger maxValue, String suffix) method. Then log this value for different values in your main method.

Value 5 Calls: 20
Value 10 Calls: 103
Value 15 Calls: 333
Value 20 Calls: 896
Value 25 Calls: 2141
Value 30 Calls: 4735
Value 35 Calls: 9877
Value 40 Calls: 19679
Value 45 Calls: 37729
Value 50 Calls: 70073
Value 55 Calls: 126586
Value 60 Calls: 223195

As you can see, the number of calls to the method increases dramatically, of exponential order.

This is because you are using a recursive approach to the problem that often creates a new "branch".

So, how to speed this up?

Let's take a look at some of the output for the value 20:

2 3 7 8 
1 4 7 8 
5 7 8 
2 3 6 9 
1 4 6 9 
5 6 9 
2 3 5 10 
1 4 5 10 
2 3 4 11 
4 5 11 
2 3 15 
1 4 15 
5 15 

What do all these have in common? They all can make the value 5 in there some where. 11 + 4 (= 15) + 3 + 2 (= 5).

So, what do I want to say with this?

Once you have calculated the possible partitions for the value of 5, reuse them!

To accomplish this you can use a Map<Integer, List<Integer>> structure. In your findPartitions method, check if the map contains a value for target (map.containsKey) and if it does then reuse it. If it does not, then do something similar to what you are doing there already and use map.put at the end to add the found values to the map.

I have to warn you though that even adding this reusing-feature, I still expect it to take quite a long time for larger numbers.

I strongly suggest that you switch back to using int (or Integer for storing them in collections). An int will take you to 2 147 483 647, try partitioning that number first before switching to BigInteger (Hint hint: It will still take a tremendous amount of time to partition 2 147 483 647, if you don't believe me then try doing it by hand).

Answer 2

This answer will focus on general style of your code.

• Use constructor chaining. One of your constructors can call the other one, like this:

  public StackExchange(int num) {
      this(new BigInteger(String.valueOf(num)));
  }
  

  This helps removing a bit of code duplication.

• Declare by interface, not by implementation. To make it easier to change implementations, you can change this line:

     private ArrayList<ArrayList<BigInteger>> allPartitions;
  

  into this:

     private List<List<BigInteger>> allPartitions;
  

• Don't do so much work in the constructor. Only initialize n and the allPartitions list in your constructor, don't call findPartitions from the constructor. Let the main method do that. Constructors are supposed to be initial constructors only, not workers that work for a long while to create the object.

• There's no need to use allPartitions = findPartitions();, findPartitions returns allPartitions. Instead use findPartitions(allPartitions);

• Use JavaDoc to document your methods, like this:

      /**
       * Returns partitions without calculating them.
       */
      public ArrayList<ArrayList<BigInteger>> getPartitions() {
          return allPartitions;
      }
  

• Besides the reasons in my other answer, your containsInteger method takes a tremendous amount of time. Instead of using strings to store the result (which really is a bad idea), use a Set<Integer>. Using a Set let's you use set.contains(value) which has a time complexity of O(1). Your current approach has a time complexity of O(n). If you aren't familiar of time complexities, O(1) is significantly faster than O(n). If you are familiar of time complexities, it's still significantly faster.

• As stated in my other answer, don't expect this algorithm to work well with BigInteger. Stick to using Integer / int instead. Besides the fact that you won't be able to partition Integer.MAX_VALUE (2147483647) that easily, calculations on a regular int is significantly faster than on a BigInteger.

• Don't call System.gc(); in your main method. It is a) totally unnecessary since your program just got started, there's nothing to garbage collect yet. b) Even if it would be something to garbage collect, the method call is just a suggestion to the Java Virtual Machine. In nearly all Java applications, you never need to call this method. The system can take care of this by itself.

Answer 3

@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

  $$ \begin{eqnarray*} n & = & 1 + 2 + 3 + \ldots + x_{max} \\ & = & \frac{x_{max} (x_{max} + 1)}{2} \end{eqnarray*} $$

  By the quadratic equation,

  $$ x_{max} = \frac{-1 \pm \sqrt{1 + 8 n}}{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.