Download
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:
 
  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());
}