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
%
% Set partition problem in Minizinc.
%
% 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:
%  <ul>
%  <li>A U B = S,</li>
%  <li>|A| = |B|,</li>
%  <li>sum(A) = sum(B),</li>
%  <li>sum_squares(A) = sum_squares(B).</li>
%  </ul>
% """
%
% Model created by Hakan Kjellerstrand, hakank@gmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc
%
 
% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
 
%
include "globals.mzn";
 
int: n = 16;
set of 1..n: S = 1..n;
int: num_sets = 2;
array[1..num_sets] of var set of S: a;
array[1..num_sets] of var 0..n*n: sums;
array[1..num_sets] of var 0..n*n*n*n: sum_squared;
 
 
%
% set_sum
% sums the elements in the set s
%
predicate set_sum(var set of int: s, var int: the_sum) =
   the_sum = sum(i in ub(s)) (bool2int(i in s)*i)
;
 
predicate set_sum_squared(var set of int: s, var int: the_sum) =
   the_sum = sum(i in ub(s)) (bool2int(i in s)*i*i)
;
 
 
solve :: set_search(a, first_fail, indomain_min, complete) satisfy;
% solve maximize sums[1];
 
constraint
  assert(n mod 4 == 0, "n must be a multiple of 4")
;
 
% (
%  20080419:
%  eclipse gives the following error
%  instantiation fault in dvar_remove_smaller(_18602{0 .. 20}, 1)
% )
constraint
   % use all the elements in S and it should be disjoint sets
   partition_set(a, S)
   /\
   forall(i in 1..num_sets) (  
     a[i] `set_sum` sums[i]
     /\ a[i] `set_sum_squared` sum_squared[i]
   )
   /\
   forall(i in 2..num_sets) (
     card(a[i]) > 0 /\ % this is needed by eclipse
     card(a[i]) = card(a[i-1]) /\
     sums[i] = sums[i-1]
     /\ sum_squared[i] = sum_squared[i-1]
   )
 
  % symmetry breaking
  /\ 1 in a[1]
 
;
 
output [
   "a: " ++ show(a) ++ "\n" ++
   "sums: " ++ show(sums) ++ "\n" ++
   "sum_squared: " ++ show(sum_squared) ++ "\n"
];
 
% For model seeker
% output [
%    show(set2array(fix(a[i]))) ++ ","
%   | i in 1..num_sets
% ];