1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | /* Set partition problem in Comet. Problem formulation from """ This is a partition problem. Given the set S = {1, 2, ..., n}, it consists in finding two sets A and B such that: A U B = S, |A| = |B|, sum(A) = sum(B), sum_squares(A) = sum_squares(B) """ This model uses a binary matrix to represent the sets. Also, compare with other models which uses var sets: * MiniZinc: http://www.hakank.org/minizinc/set_partition.mzn * Gecode/R: http://www.hakank.org/gecode_r/set_partition.rb This Comet model was created by Hakan Kjellerstrand (hakank@gmail.com) Also, see my Comet page: http://www.hakank.org/comet */ // Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/ import cotfd; int t0 = System.getCPUTime(); int n = 16; int num_sets = 2; assert (n % num_sets == 0); // sanity: is the partition possible? Solver<CP> m(); var <CP>{ bool } a[1..num_sets, 1..n](m); // the set Integer num_solutions(0); exploreall <m> { forall (i in 1..num_sets, j in i+1..num_sets) { // same cardinality m.post( sum (k in 1..n) a[i,k] == sum (k in 1..n) a[j,k]); // same sum m.post( sum (k in 1..n) k*a[i,k] == sum (k in 1..n) k*a[j,k]); // same sum squared m.post(( sum (k in 1..n) (k*a[i,k])^2) == ( sum (k in 1..n) (k*a[j,k])^2)); } partition_sets(a); // symmetry breaking (for num_sets == 2) if (num_sets == 2) m.post(a[1,1] == true ); } using { labelFF(m); num_solutions := num_solutions + 1; cout << "sums: " << sum (j in 1..n) j*a[1,j] << endl; cout << "sums squared: " << ( sum (j in 1..n) (j*a[1,j])^2) << endl; // show the partitions forall (i in 1..num_sets) { if ( sum (j in 1..n) a[i,j] > 0) { cout << i << ": " ; forall (j in 1..n) { if (a[i,j]) cout << j << " " ; } cout << endl; } } cout << endl; } cout << "\nnum_solutions: " << num_solutions << endl; int t1 = System.getCPUTime(); cout << "time: " << (t1-t0) << endl; cout << "#choices = " << m.getNChoice() << endl; cout << "#fail = " << m.getNFail() << endl; cout << "#propag = " << m.getNPropag() << endl; // // Partition the sets (binary matrix representation). // function void partition_sets( var <CP>{ bool } [,] x) { Solver<CP> m = x[1,1].getSolver(); range R1 = x.getRange(0); range R2 = x.getRange(1); forall (i in R1, j in R1 : i != j) m.post( sum (k in R2) (x[i,k] && x[j,k]) == 0); // ensure that all integers is in (exactly) one partition m.post(( sum (i in R1, j in R2) x[i,j]) == R2.getSize()); } |