[gecode-users] Help:How to compute Autocorrelation of a v-length sequence
George Rudolph
george.rudolph at citadel.edu
Fri Oct 19 16:48:31 CEST 2007
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:cschulte at kth.se]
> Sent: Friday, October 19, 2007 7:12 AM
> To: George Rudolph; users at gecode.org
> 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: 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