The gecode-specific question is this: What have I done wrong? How do I specify periodic autocorrelation on a binary sequence using Gecode/J? The code I have written does not match the constraints I think I am writing--when I run the program for v=13, for example, I am expecting exactly two solutions, but I get more than two. And the additional solutions don't match the constraints I am trying to specify. Yet, It is not obvious to me what I have done wrong.
-------------------- George Rudolph Assistant Professor Thompson Hall 225 Math & Computer Science Dept. The Citadel 171 Moultrie St. Charleston, SC 29409 > -----Original Message----- > From: Christian Schulte [mailto:[EMAIL PROTECTED] > Sent: Friday, October 19, 2007 7:12 AM > To: George Rudolph; [EMAIL PROTECTED] > Subject: RE: [gecode-users] Help:How to compute Autocorrelation of a v- > lengthsequence > > Hi, > > what is the Gecode-specific question here? > > Christian > > -- > Christian Schulte, http://www.imit.kth.se/~schulte/ > -----Original Message----- > From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf > Of George Rudolph > Sent: Thursday, October 18, 2007 7:42 PM > To: [EMAIL PROTECTED] > 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 ------------------- _______________________________________________ Gecode users mailing list [EMAIL PROTECTED] https://www.gecode.org/mailman/listinfo/gecode-users
