[gecode-users] Help:How to compute Autocorrelation of a v-lengthsequence
Christian Schulte
cschulte at kth.se
Fri Oct 19 13:11:46 CEST 2007
Hi,
what is the Gecode-specific question here?
Christian
--
Christian Schulte, http://www.imit.kth.se/~schulte/
-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of George Rudolph
Sent: Thursday, October 18, 2007 7:42 PM
To: users at gecode.org
Subject: [gecode-users] Help:How to compute Autocorrelation of a
v-lengthsequence
As stated in the comments below, I need help figuring out
how to express constraints on the autocorrelation of a v-length sequence.
I am sure there is an easier way to rotate a list,
compare two lists for positional matches, count the member of matches,
and constrain the number of matches to be a particular value,
and I need help finding it.
------------- begin code --------------
package citadel;
import static org.gecode.Gecode.*;
import static org.gecode.GecodeEnumConstants.*;
import org.gecode.*;
/**
* Script for computing 2-class association schemes, modified from the
Queens
* example. The goal of this script is to generate (v-1)-length sequences
with
* the following properties:
* 1. v is prime and v=4t+1, t >=0.
* 2. each sequence has n1 occurrences of lambda1 and n2 occurrences of
lambda2.
* 3. the sequence is a palindrome: element 0 and element v-2 have the sane
value, element 1 and
* element v-3 have the same value, element 2 and element 4-4 have the same
* value, etc.
* 4. The autocorrelation sequence generated by this sequence is flat. That
is,
* if you prepend a 0 to the sequence, and then take the cross-correlation C
of
* the extended sequence with rotated copies of itself for all shift values
y=1...(v-1),
* then c[i] = 2t-1.
* Since 0 matched with non-zero value is a mismatch, it should be possible
* take the cross-correlation without prepending the 0.
*
* @author George Rudolph
* @version 1.0 Sep 20, 2007
*/
public class AssociationScheme extends Space {
/**
* v is the size or length of the sequence,
* must be prime.
*/
public int v;
/**
* v = 4t + 1, so t = (v-1)/4, t > 0
*/
public int t;
/**
* the number of 1st associates of any element x.
*/
public int n1;
/**
* The number of 2nd associates of any element x.
*/
public int n2;
/**
*
*/
public int lambda1;
public int lambda2;
public VarArray<IntVar> schemeCount;
/**
* @param opt
* Convenience object containing options
* @see citadel.Options#toString()
*/
public AssociationScheme(Options opt) {
super();
v = opt.size;
t = (v - 1) / 4;
n1 = (v - 1) / 2;
n2 = (v - 1) / 2;
lambda1 = 1;
lambda2 = 2;
schemeCount = new VarArray<IntVar>(this, v - 1,
IntVar.class, 1, 2);
// in the difference vector, constrain it so that
// the value of position i is the same as the value at
position v-i
// for a (v-1)-length array starting at (conceptual) index 1
// TODO: simplify the indexing in this constraint
for (int i = 1; i <= v - 1; i++) {
rel(this, schemeCount.get(i - 1), IRT_EQ,
schemeCount
.get(v - 1 - i), opt.icl);
}
// "exactly n1 elements have the value lambda1 in
schemeCount"
// "exactly n2 elements have the value lambda2 in
schemeCount"
count(this, schemeCount, lambda1, IRT_EQ, n1, opt.icl);
count(this, schemeCount, lambda2, IRT_EQ, n2, opt.icl);
/********************** begin autocorrelation code
***************************/
/** what am I doing wrong below?
**/
/* each element of the autocorrelation sequence for
schemeCount
// must equal 2t-1 = ((v-1)/2) - 1
// autocorrelation is the cross-correlation of a sequence
with a rotated copy
// of itself.
// An autocorrelation sequence is the sequence generated by
taking the
// cross-correlation for each rotation--the ith position in
the autocorrelation
// sequence is obtained by taking the cross-correlation of
schemeCount with a
// copy of schemeCount rotated right i places (mod v).
// But I don't need a second copy of the sequence, I can
just manipulate
// the indices. This is what I am trying to do below, but I
am not getting
* the results I expect. Invalid solutions are being
accepted.
*
* The algorithm is to match schemeCount against a shifted
copy of itself using
* the offset y, count the matches as 1, and the mismatches
as 0,
* stored in the sequence Intersect0Y, then sum up all
* the 1's in Intersect0Y, and finally, constrain that the
sum must be 2t-1
* for *each* shift 1...v-1.
* It works for v=5, but is broken for v=13.
* I suspect it only works for v-5 because of the small
space.
*
* If there is an easier way to write this constraint,
* I'm open to suggestions.
*
* 212211112212 is a valid solution for v=13.
*
* Note, really the sequence is 0212211112212,
* so rotated 5 places it looks like 1221202122111,
* but since 0 matched with anything is 10, in this case,
* I'm trying to avoid prepending the 0 to schemeCount,
* which doesn't include it above.
*
*/
for (int y = 1; y < v; y++) {
VarArray<BoolVar> intersectY0 = new
VarArray<BoolVar>(this, v - 1,
BoolVar.class);
for (int x = 1; x < v; x++) {
if (x == y) {
continue;
}
int z = ((x - y + v) % v)-1;
eq(this, schemeCount.get(y-1),
schemeCount.get(z), intersectY0
.get(x-1), opt.icl);
} // end for x
VarArray<IntVar> pijk = new
VarArray<IntVar>(intersectY0);
// exactly 2t-1 elements have the value 1 in pijk
count(this, pijk, 1, IRT_EQ, 2 * t - 1, opt.icl);
} // end for y
/*********************** end autocorrelation code
**************************/
branch(this, schemeCount, BVAR_SIZE_MIN, BVAL_MIN);
}
/**
* Copy constructor.
*
* @param share
* @param scheme
*/
public AssociationScheme(Boolean share, AssociationScheme scheme) {
super(share, scheme);
v = scheme.v;
t= (v-1)/4;
n1 = (v - 1) / 2;
n2 = (v - 1) / 2;
lambda1 = 1;
lambda2 = 2;
schemeCount = new VarArray<IntVar>(this, share,
scheme.schemeCount);
}
/**
*
* @see org.gecode.Space#toString()
*/
public String toString() {
return schemeCount.toString();
}
/**
* Application startup
*
* @param args
*/
public static void main(String[] args) {
Options opt = new Options();
opt.size = 5;
opt.gui = true;
opt.parse(args);
opt.name = "" + opt.size + "-Schemes";
AssociationScheme schemes = new AssociationScheme(opt);
opt.doSearch(schemes);
}
}
--------------------- end code -------------------
More information about the gecode-users
mailing list