this repo has no description
dekker.one
1/***
2!Test
3expected:
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, hakank@bonetmail.com
60% See also my MiniZinc page: http://www.hakank.org/minizinc
61
62include "globals.mzn";
63
64int: n = 11;
65int: m = 3;
66set of int: S = {1,2,3,4,6};
67array[1..n] of var S: variables;
68array[1..3] of var set of S: partitions;
69var int: nchange;
70
71output [
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)
79predicate 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%
88predicate 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
111predicate 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
120predicate 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
130solve satisfy;
131
132constraint
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;