Java implementation of a Dynamic Programming approach to the Linear Partition Algorithm

LinearPartitionTestApplication.java

/**
 *  Created by abrie on 2015-11-01.
 *
 *  Java implementation of a Dynamic Programming approach to the Linear Partition Algorithm
 *   AKA 'The Easiest Hard Problem': https://en.wikipedia.org/wiki/Partition_problem
 *
 *  Adapted from the python implementation described here: http://stackoverflow.com/a/7942946
 *   and on Skiena's description in 'The Algorithm Design Manual':
 *   https://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK2/NODE45.HTM
 *
 *  An interesting feature of this algorithm is the preservation of sequence order!
**/
     
import java.util.ArrayList;
import java.util.Arrays;

public class LinearPartitionTestApplication 
{
    static class LinearPartition {
        static public ArrayList<ArrayList<Integer>> run(ArrayList<Integer> seq, int k) {
            ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    
            if (k <= 0) {
                ArrayList<Integer> partition = new ArrayList<>();
                partition.addAll(seq);
                result.add(partition);
                return result;
            }
    
            int n = seq.size()-1;
            
            if (k > n) {
                for (Integer value : seq) {
                    ArrayList<Integer> partition = new ArrayList<>();
                    partition.add(value);
                    result.add(partition);
                }
                return result;
            }
    
            int[][] table = build_partition_table(seq, k);
            k = k-2;
            
            while (k >= 0) {
                ArrayList<Integer> partition = new ArrayList<>();
                
                for (int i = table[n-1][k]+1; i < n+1; i++) {
                    partition.add(seq.get(i));
                }
                
                result.add(0, partition);
                n = table[n-1][k];
                k = k-1;
            }
    
            ArrayList<Integer> partition = new ArrayList<>();
            
            for (int i = 0; i < n+1; i++) {
                partition.add(seq.get(i));
            }
    
            result.add(0, partition);
    
            return result;
        }
    
        static public int[][] build_partition_table(ArrayList<Integer> seq, int k) {
            int n = seq.size();
            float[][] table = new float[n][k];
            int[][] solution = new int[n-1][k-1];
            
            for (int i = 0; i < n; i++) {
                table[i][0] = seq.get(i) + ((i > 0) ? (table[i-1][0]) : 0);
            }
    
            for (int j = 0; j < k; j++) {
                table[0][j] = seq.get(0);
            }
    
            for (int i = 1; i < n; i++) {
                for (int j = 1; j < k; j++) {
                    table[i][j] = Integer.MAX_VALUE;
                    for (int x = 0; x < i; x++) {
                        float cost = Math.max(table[x][j-1], table[i][0]-table[x][0]);
                        if (table[i][j] > cost) {
                            table[i][j] = cost;
                            solution[i-1][j-1] = x;
                        }
                    }
                }
            }
    
            return solution;
        }
    
        static public void test_AllSame() {
            ArrayList<Integer> input = new ArrayList<>(
                Arrays.asList(100, 100, 100, 100, 100, 100, 100, 100, 100));
    
            ArrayList<ArrayList<Integer>> expect = new ArrayList<>(
                Arrays.asList(
                    new ArrayList<Integer>(Arrays.asList(100, 100, 100)),
                    new ArrayList<Integer>(Arrays.asList(100, 100, 100)),
                    new ArrayList<Integer>(Arrays.asList(100, 100, 100))));
    
            ArrayList<ArrayList<Integer>> actual = run(input, 3);
            System.out.println("Expect: " + expect.toString());
            System.out.println("Actual: " + actual.toString());
            System.out.println("Passes: " + expect.toString().equals(actual.toString()));
        }
    
        static public void test_AllDifferent() {
            ArrayList<Integer> input = new ArrayList<>(
                Arrays.asList(100, 200, 300, 400, 500, 600, 700, 800, 900));
            
            ArrayList<ArrayList<Integer>> expect = new ArrayList<>(
                Arrays.asList(
                    new ArrayList<Integer>(Arrays.asList(100, 200, 300, 400, 500)),
                    new ArrayList<Integer>(Arrays.asList(600, 700)),
                    new ArrayList<Integer>(Arrays.asList(800, 900))));
    
            ArrayList<ArrayList<Integer>> actual = run(input, 3);
            System.out.println("Expect: " + expect.toString());
            System.out.println("Actual: " + actual.toString());
            System.out.println("Passes: " + expect.toString().equals(actual.toString()));
        }
    }
    
    public static void main(String[] args)
    {
        LinearPartition.test_AllSame();
        LinearPartition.test_AllDifferent();
    }
}