Dear George,
I just had a look at your problem. I don't see a more efficient way to
solve your problem, i.e., reifying the equality between elements and
summing the values. However the code you provide is a bit confusing.
Here is an abstraction that implements the shifted dot product for a list:
proc {ShiftedDotProduct Xs Val}
Ys={Append Xs.2 [Xs.1]}
Matches={List.zip Xs Ys fun {$ X Y} X=:Y end}
in
{FD.decl Val}
{FD.sum Matches '=:' Val}
end
You can use this abstraction as a function on any list of FD variables.
Note that the abstraction is independent from the domains of the elements.
Cheers,
raph
George Rudolph wrote:
The program below is a subproblem of another larger problem I have been
working on. The main question I have is this: Is there
another more efficient way to compute the shifted dot product/
autocorrelation constraint (see code below) than the method I am currently
using?
For example, for V =13, one solution is the list {1 2 1 1 2 2 2 2 1 1 2 1}.
Shifted by 1 it is { 1 1 2 1 1 2 2 2 2 1 1 2}.
If you count the number of places where these two list match, it will be 5.
When V = 13, T = 3, and 2T – 1 = 5. (That’s where the numbers come from).
For different values of V, T will change, but the number of matches
will always be
2T – 1.
So you could say I am looking for strings of 1’s and 2’s which are
palindromes,
where the number of 1’s and 2’s are equal, and where, if you compute the
number of matches
in the shifted dot product, it is constant (and always a known value 2T
– 1).
Ideally, I would like to replace each 2 by 1 and each 1 by minus 1, and
simply compute the
canonical dot product for each shift. But since FD variables have to be
positive, I don’t know
how to formulate that (other than what I am currently doing).
Is that enough of a brain dump to be helpful? ;)
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
