I suppose some of the reasons the code may be confusing are the
following:
1. I was creating only one list of domain variables (Histogram), instead
of using two Lists (Histogram and a shifted copy of Histogram). This
means writing the constraints for the shifted copy in terms of indexes
in the original list.
I thought that doing this would save space, and I wasn't sure that
shifting domain variables in a list, the way you show in the code below,
would work
the way I expect. Apparently it does, which is good.
2. I'm not computing and constraining the shifted dot product just once,
but actually computing/constraining a sequence of shifted dot
products--that is,
the product of Histogram and Histogram shifted once, the product of
Histogram and Histogram shifted twice, and so on, up to
(length-of-Histogram) - 1 shifts.
This version of the code is more like what I want, though it
doesn't seem to work, in that no solutions are found
when I call it with
{Autocorrelate Count (2*T - 1)}
It fails with a red square, as opposed to a light green diamond.
---------- begin code ------------------
proc {Autocorrelate Xs Val}
NumberOfShifts = {List.length Xs} - 1
in
for I in 1..NumberOfShifts do
%rotate the list Xs by: splitting the list at position I
%then slicing the list back together with the parts swapped
CopyOfXsRotatedISlots={Append {List.drop Xs I} {List.take Xs I}}
Matches={List.zip Xs CopyOfXsRotatedISlots fun {$ X Y} X=:Y end}
in
{FD.decl Val}
{FD.sum Matches '=:' Val}
{Browse Matches}
end
end
-------------- end code------------------------------
--------------------
George
> -----Original Message-----
> From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]
On
> Behalf Of Raphael Collet
> Sent: Friday, May 11, 2007 3:07 AM
> To: Mozart users
> Subject: Re: Computing shifted dot product
>
> 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 mozart-
> [EMAIL PROTECTED]
> http://www.mozart-oz.org/mailman/listinfo/mozart-users
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
