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? ;)
----------------------------- Begin Code
--------------------------------------------
declare
% Exactly D elements of Dv have the value I. This is a rewrite of
% the built-in function FD.exactly, which has a bug in version 1.2.3.
% This is used to enforce the constraint that half the differences
% appear once and half appear twice, by counting differences that
% appear twice.
proc {Exactly D Dv TargetValue}
Ds = if {List.is Dv}
then Dv
else {Record.toList Dv} end
Bs = {Map Ds fun {$ E} E =: TargetValue end}
in
{FD.sum Bs '=:' D}
end
%
%
%
proc {Design Count}
%V is the size of set V
V = 13
%I needed a variable to represent V-I to clean up code
%U is probably a bad choice when working with sets though.
U = V-1
%S is the size of the starter set S.
%S is usually calculated by dividing B (the number of blocks in the
design) by V.
S = U div 4
%T is (V-1) div 4, that is, V is congruent to 4*T + 1
T = S
%
N1 = U div 2
N2 = U - N1
Lambda1 = 1
Lambda2 = 2
in
Count = {FD.tuple paired U 1#2}
for I in 1..U do
Count.I =: Count.(V-I)
end
{Exactly N2 Count Lambda2} % lambda2 elements appear twice with 0 in
the design
{Exactly N1 Count Lambda1} % lambda1 elements appear once with 0 in
the design
%% This nested for loop is really computing the shifted dot product of
Count with itself.
%% Because FD variables can only handle positive values, I don't
subtract the number
%% of mismatches from the number of matches, so this doesn't look like a
dot product,
%% But it is.
%%
%% The question is: Is there another, simpler, more efficient way to
calculate the
%% shifted dot product, or really, the number of matches and mismatches
than this?
%% The answer may be "no". Any ideas?
%%
for Y in 1..U do
Intersect0Y = {FD.tuple pairedI U 0#1}
in
for X in 1..U do
if X\=Y then Z = (X-Y+V) mod V in
%% reifies: X appears once with 0 and once with Y
Intersect0Y.X =: (Count.X =: 1) * (Count.Z =:
1)+(Count.X =: 2) * (Count.Z =: 2)
else
Intersect0Y.X = 0
end
end
{FD.sum Intersect0Y '=:' (2*T - 1)}
end
%% end of "balancing pairs" {0,Y} constraints
%% distributed on the variables in Blocks
{FD.distribute ff Count}
end
{Explorer.object option(search search:5 information:25 failed:true)}
{Explorer.object script(Design)}
-------------------------------- End Code
--------------------------------------------------
--------------------
George Rudolph
Assistant Professor
Thompson Hall 225
Math & Computer Science Dept.
The Citadel
171 Moultrie St.
Charleston, SC 29414
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
