Harmon Nine wrote:
Could someone direct me to a more detailed explanation of the redundant
constraints shown in the Chapter 7 exercises of the Constraint
Programming Tutorial (i.e. "Finite Domain Constraint Programming in Oz.
A Tutorial.", section 7.4).
The problem has to do with "Magic Sequences," and the redundant
constraints are:
x0 + x1 + ... + x(n-1) = n
-1*x0 + 0*x1 + 2*x2 + ... + (n-2)*x(n-1) = 0
The explanations in the tutorial are a bit vague.
Let me restate the problem, and introduce useful notations: the problem
is to find a sequence x0, x1, ..., x(n-1) such that for each i:
0 =< xi < n and #{j | xj=i} = xi.
The set {j | xj=i} is the set of indices j corresponding to the
occurrences of the integer i in the sequence, and '#' is the cardinality
operator.
Now consider the sum s = x0 + x1 + ... + x(n-1), and replace each xi by
its definition, which gives
s = #{j | xj=0} + #{j | xj=1} + ... + #{j | xj=n-1}.
As all the sets in the sum are disjoint, you can compute the cardinality
of their union, which is equal to n:
s = #{j | 0 =< xj =< n-1} = #{0,1,...,n-1} = n
That gives the first redundant constraint. The second one is obtained
in a similar way. In the sum
s = x0 + x1 + ... + x(n-1),
each integer i in {0,1,...,n-1} is summed xi times, hence
s = 0*x0 + 1*x1 + 2*x2 + ... + (n-1)*x(n-1).
The difference between the two latter equations gives
(-1)*x0 + 0*x1 + 1*x2 + 2*x3 + ... + (n-2)*x(n-1).
Quod erat demonstrandum :-)
Cheers,
raph
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
