this repo has no description
dekker.one
1%-----------------------------------------------------------------------------%
2% Requires that the array 'x' is lexicographically less than or equal to
3% array 'y'. Compares them from first to last element, regardless of indices
4%-----------------------------------------------------------------------------%
5
6predicate fzn_lex_lesseq_bool(array[int] of var bool: x,
7 array[int] of var bool: y) =
8% if (min(card(index_set(x)), card(index_set(y))) <= 25) then
9% let { int: size = min(card(index_set(x)), card(index_set(y)));
10% } in
11% sum(i in 0..size-1)(pow(2, (size-1-i)) * bool2int(x[i+min(index_set(x))]))
12% <= sum(i in 0..size-1)(pow(2, (size-1-i)) * bool2int(y[i+min(index_set(y))]))
13% else
14% my_trace ("lex_lesseq_bool(\(x), \(y))") /\
15 let { int: lx = min(index_set(x)),
16 int: ux = max(index_set(x)),
17 int: ly = min(index_set(y)),
18 int: uy = max(index_set(y)),
19 int: size = min(ux - lx, uy - ly),
20 array[0..size+1] of var bool: b }
21 % b[i] is true if the lexicographical order holds from position i on.
22 in
23 b[0]
24 /\
25 forall(i in 0..size) (
26 b[i] -> ( ( ( x[lx + i] <= y[ly + i] ) ) /\
27 % bool2int(b[i]) + bool2int(x[lx + i]) + (1-bool2int(y[ly + i])) <= 2 /\
28
29% ( b[i] ->
30( x[lx + i] < y[ly + i] \/ b[i+1] ) )
31% /\ ( bool2int(b[i]) <= bool2int(x[lx + i] < y[ly + i]) + bool2int(b[i+1]) ) /\
32 % bool2int(b[i]) + (1-bool2int(x[lx + i])) + (1-bool2int(y[ly + i])) + (1-bool2int(b[i+1])) <= 3
33 % /\ bool2int(b[i]) + bool2int(x[lx + i]) + bool2int(y[ly + i]) + (1-bool2int(b[i+1])) <= 3
34 %% This guy is dominated by the 1st one above but helps:
35 % /\ bool2int(b[i]) + bool2int(x[lx + i]) + (1-bool2int(y[ly + i])) + (1-bool2int(b[i+1])) <= 3
36 )
37 /\ b[size+1] = (ux-lx <= uy-ly)
38% endif
39;
40
41% forall(i in 0..size) (
42% ( b[i] == ( x[lx + i] <= y[ly + i] ) )
43% /\
44% if i < size then
45% ( b[i] == ( x[lx + i] < y[ly + i] \/ b[i+1]
46% ) ) else true endif
47% );
48
49%-----------------------------------------------------------------------------%