Courses/CS 460/Fall 2006/Partition
From CSWiki
Partition a set of integers into two subsets so that the sums of the integers in the two subsets are equal.
Strategy: Define a set of selectors whose domain is {-1, 1}. The n-the selector applies to the n-the element in the integer set. Select the selector values so that the sum of the products of the selectors and the set is 0. Use the scalar() method to take the sum of the product.
[edit] Code
//Partition using constraints
package examples;
import java.util.ArrayList;
import java.util.Random;
import choco.Problem;
import choco.integer.IntDomainVar;
public class Partition {
public static int setSize;
public static int numTrials;
public static int numSolved;
public static int range;
public static Random generator;
public static int[] set;
public static IntDomainVar[] selectors;
public static Problem problem;
public static ArrayList<IntDomainVar> fdvList;
public static long totalSuccessTime = 0;
public static long totalFailureTime = 0;
public static void main(String[] args) {
// Run parameters
setSize = 20;
numTrials = 10;
range = 10;
// Init random generator
generator = new Random(System.currentTimeMillis());
// Run the trials.
for (int i = 0; i < numTrials; i++) runTrial(i);
System.out.println("\nOverall statistics: " + setSize + " elements.");
System.out.println("-------------------");
System.out.println("Percent solved: " + (100*numSolved)/numTrials + "%.");
System.out.println("Average success time: " +
Math.round(totalSuccessTime/(double)numSolved) + " ms.");
System.out.println("Average failure time: " +
Math.round(totalFailureTime/(double)(numTrials-numSolved)) + " ms.");
System.out.println("Average time: " +
Math.round((totalSuccessTime+totalFailureTime)/(double)numTrials) + " ms.");
}
public static void generateConstraints() {
// Create an FDV selector for each element in the set.
// It's value may be either -1 or 1.
for (int i = 0; i < setSize; i++) {
selectors[i] = problem.makeEnumIntVar("selectors[" + i + "]", -1, 1 );
problem.post(problem.neq(0, selectors[i]));
}
// Distribute -1 and 1 among the selectors so that the weighted sum is 0.
problem.post(problem.eq(0, problem.scalar(set, selectors)));
}
public static void buildSet() {
set = new int[setSize];
for (int i = 0; i < setSize; i++) {
set[i] = 1 + new Integer( generator.nextInt( range ));
}
}
public static void outputSet() {
System.out.print("Set: ");
for (int i = 0; i < setSize; i++) {
System.out.print(set[i] + (i < setSize - 1 ? " " : "\n"));
}
}
public static void outputSolution() {
for (int k: new int[] {1, -1}) {
System.out.print("Set " + (k == -1 ? 1 : 2) + ": ");
for (int i = 0; i < setSize; i++) {
if (selectors[i].getVal() == k) System.out.print(set[i] + " ");
}
System.out.println();
}
}
private static void runTrial(int i) {
fdvList = new ArrayList<IntDomainVar>();
selectors = new IntDomainVar[setSize];
problem = new Problem();
buildSet();
generateConstraints();
long t1 = System.currentTimeMillis();
// Run branch and bound minimization search.
// Minimize difference (absolute value).
boolean solved = problem.solve(); //difference, false); //(problem, fdvList, difference, new IndomainMin(), new Delete());
long time = System.currentTimeMillis() - t1;
if (solved) {
numSolved++;
totalSuccessTime += time;
} else totalFailureTime += time;
System.out.println("\n" + setSize + " elements. Trial " + i + ". " + time + " ms.");
System.out.println((solved ? "Solved. " : "Failed. "));
System.out.println("======================================================================");
outputSet();
if (solved) outputSolution();
System.out.println("======================================================================");
}
}
[edit] Output
20 elements. Trial 0. 93 ms. Solved. ====================================================================== Set: 1 4 10 6 7 2 5 3 7 2 10 2 9 10 7 4 7 8 9 9 Set 2: 2 9 10 7 7 8 9 9 Set 1: 1 4 10 6 7 2 5 3 7 2 10 4 ====================================================================== 20 elements. Trial 1. 0 ms. Solved. ====================================================================== Set: 6 10 7 9 6 9 2 3 5 7 6 7 9 3 7 4 7 1 10 10 Set 2: 6 7 9 3 7 4 7 1 10 10 Set 1: 6 10 7 9 6 9 2 3 5 7 ====================================================================== 20 elements. Trial 2. 4390 ms. Failed. ====================================================================== Set: 5 7 2 8 6 5 8 8 3 6 2 10 5 3 9 7 3 9 1 4 ====================================================================== 20 elements. Trial 3. 5312 ms. Failed. ====================================================================== Set: 1 9 4 8 4 10 4 3 2 1 7 10 9 2 1 8 1 6 6 1 ====================================================================== 20 elements. Trial 4. 0 ms. Solved. ====================================================================== Set: 4 7 6 10 5 3 5 4 5 9 1 10 6 3 1 10 4 4 9 4 Set 2: 9 10 6 3 10 4 9 4 Set 1: 4 7 6 10 5 3 5 4 5 1 1 4 ====================================================================== 20 elements. Trial 5. 0 ms. Solved. ====================================================================== Set: 2 9 3 5 9 2 6 8 10 9 2 10 7 1 6 7 1 10 7 8 Set 2: 9 2 10 1 6 7 1 10 7 8 Set 1: 2 9 3 5 9 2 6 8 10 7 ====================================================================== 20 elements. Trial 6. 10547 ms. Failed. ====================================================================== Set: 7 9 8 9 3 3 1 7 10 7 5 7 3 9 1 10 9 4 5 4 ====================================================================== 20 elements. Trial 7. 0 ms. Solved. ====================================================================== Set: 5 2 5 7 9 10 8 4 1 1 6 8 9 4 10 10 1 7 9 10 Set 2: 8 9 10 10 7 9 10 Set 1: 5 2 5 7 9 10 8 4 1 1 6 4 1 ====================================================================== 20 elements. Trial 8. 10344 ms. Failed. ====================================================================== Set: 5 3 9 8 8 10 2 4 8 2 2 5 4 9 2 10 9 9 6 4 ====================================================================== 20 elements. Trial 9. 3563 ms. Failed. ====================================================================== Set: 1 9 10 3 3 10 9 3 4 9 2 6 2 7 6 10 8 4 2 1 ====================================================================== Overall statistics: 20 elements. ------------------- Percent solved: 50%. Average success time: 19 ms. Average failure time: 6831 ms. Average time: 3425 ms.
This was run on a computer that was simultaneously doing the partition stress test. The timings should presumably be halved.
