Debian Codegraph @

tests/spec/unit/regression/change_partition.mzn

raw
1 /***
2 !Test
3 expected:
4 - !Result
5 solution: !Solution
6 nchange: 2
7 partitions:
8 - !!set {1, 3}
9 - !!set {4}
10 - !!set {2, 6}
11 variables: [6, 6, 2, 1, 3, 3, 1, 6, 2, 2, 2]
12 ***/
13
14 % Regression test for the bug descibed in var_self_assign_bug.mzn.
15 % (This is the model from the original bug report.)
16
17 % Global constraint in MiniZinc.
18 %
19 % From Global Constraint Catalogue
20 % http://www.emn.fr/x-info/sdemasse/gccat/Cchange_parition.html
21 % """
22 % NCHANGE is the number of times that the following constraint holds:
23 % X and Y do not belong to the same partition of the collection PARTITIONS.
24 % X and Y correspond to consecutive variables of the collection VARIABLES.
25 %
26 % Example
27 % (
28 % 2,​<
29 % var-6,
30 % var-6,
31 % var-2,
32 % var-1,
33 % var-3,
34 % var-3,
35 % var-1,
36 % var-6,
37 % var-2,
38 % var-2,
39 % var-2
40 % >,
41 % <
42 % p-<1, 3>,
43 % p-<4>,​
44 % p-<2,6>
45 % >
46 % )
47 %
48 % In the example we have the following two changes:
49 % * One change between values 2 and 1 (since 2 and 1 respectively belong
50 % to the third and the first partition),
51 % * One change between values 1 and 6 (since 1 and 6 respectively belong
52 % to the first and the third partition).
53 %
54 % Consequently the change_partition constraint holds since its first
55 % argument NCHANGE is assigned to 2.
56 % """
57
58 %
59 % Model created by Hakan Kjellerstrand, [email protected]
60 % See also my MiniZinc page: http://www.hakank.org/minizinc
61
62 include "globals.mzn";
63
64 int: n = 11;
65 int: m = 3;
66 set of int: S = {1,2,3,4,6};
67 array[1..n] of var S: variables;
68 array[1..3] of var set of S: partitions;
69 var int: nchange;
70
71 output [
72 "nchange = ", show(nchange), ";\n",
73 "partitions = ", show(partitions), ";\n",
74 "variables = ", show(variables), ";\n"
75 ];
76
77 % a variant of the partition_set from globals.mzn where universe is
78 % a var set of int (instead of par set of int)
79 predicate partition_set2(array[int] of var set of int: S,
80 var set of int: universe) =
81 all_disjoint(S) /\ universe == array_union(i in index_set(S)) ( S[i] )
82 ;
83
84
85 %
86 % change_partition(NCHANGE, VARIABLES, PARTITIONS)
87 %
88 predicate change_partition(var int: nchange, array[int] of var int: variables, array[int] of var set of int: partitions) =
89 let {
90 int: lbv = min(index_set(variables)),
91 int: ubv = max(index_set(variables)),
92 int: lbp = min(index_set(partitions)),
93 int: ubp = max(index_set(partitions))
94 }
95 in
96 % number of patition changes
97 nchange = n - sum(v in lbv+1..ubv, p in lbp..ubp) (
98 bool2int(
99 variables[v-1] in partitions[p] /\ variables[v] in partitions[p]
100 )
101 ) - 1
102 /\
103 partition_set2(partitions, array_union(i in lbp..ubp) (partitions[i]))
104
105 /\ % for generating partitions: exclude empty partitions
106 forall(i in lbp..ubp) (
107 card(partitions[i]) > 0
108 )
109 ;
110
111 predicate cp1d(array[int] of int: x, array[int] of var int: y) =
112 assert(index_set(x) = index_set(y),
113 "cp1d: x and y have different sizes",
114 forall(i in index_set(x)) (
115 x[i] = y[i]
116 )
117 )
118 ;
119
120 predicate cp1d(array[int] of set of int: x, array[int] of var set of int: y) =
121 assert(index_set(x) = index_set(y),
122 "cp1d: x and y have different sizes",
123 forall(i in index_set(x)) (
124 x[i] = y[i]
125 )
126 )
127 ;
128
129
130 solve satisfy;
131
132 constraint
133 cp1d([6,6,2,1,3,3,1,6,2,2,2], variables)
134 /\
135 cp1d([
136 {1,3},
137 {4},
138 {2,6}], partitions)
139 /\
140 change_partition(nchange, variables, partitions)
141 /\
142 nchange = 2
143 ;