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
