In my previous post on partition of integers, I discussed partition using a recursive technique. The recursive technique I discussed was relatively easy to understand, but at the same time was inefficient in terms of memory usage and time taken. In this post I would be discussing a way of solving the partition problem using an iterative approach. In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. If order matters, the sum becomes a composition.

For partitioning an integer using iterative technique we would take an integer array ‘a’ to store the partitions. The size of the array would be equal to the integer we are trying to partition, that is n because the longest partition would be consisting of all 1’s (n times). Initially we would initialize the first element of the array ‘a’ (index 0) to n. We would take an integer variable last to store the index of last effective element of the array. By effective I mean the part of the array which is being used at any given point of time for storing the partition. The basic idea is to generate a partition, display it; then adjust/modify the array to store the next partition and again display it. The process would repeat until all the elements of the array ‘a’ are only 1’s.

Another point which must be kept in mind while adjusting/modifying the array for next partition, is that at all times, the array elements would be in non-increasing order.

The Java implementation for partitioning an integer using the above logic is as follows:

class Partition{
    public static void main( String args[] ){
        partition(5);
    }
    public static void displayArray( int a[], int limit ){
        String answer="";
        for( int i=0; i< limit; i++ ){
             answer += a[ i ];
             if( i != limit-1 ) answer+="+";
         }
         System.out.println( answer );
     }
     public static void partition( int n ){
         int a[] = new int[ n ];
         int last = 0;
         a[last] = n;
         int remaining;
         while (true){
            displayArray(a, last+1);
            remaining = 0;
            while (last >= 0 && a[last] == 1){
               remaining += a[last--];
            }
            if (last < 0)  break;
            a[last]--;
            remaining++;
            while (remaining > a[last]){
               a[last+1] = a[last];
                remaining -= a[last++];
            }
            a[last+1] = remaining;
            last++;
        }
    }
}

As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.