[gecode-users] Help:How to compute Autocorrelation of a v-length sequence

[George Rudolph]

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 -------------------
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20071018/c0c34fb9/attachment.htm>