Thursday, July 12, 2012

Creating Williams designs with even number of products

A Williams design is a special Latin square with the additional property of first order carry over (each product is followed equally often by each other product). In R the package crossdes can be used to create them.

> williams(4)
     [,1] [,2] [,3] [,4]
[1,]    1    2    4    3
[2,]    2    3    1    4
[3,]    3    4    2    1
[4,]    4    1    3    2
As a consequence of the carry over restriction, the design has the property that a row in this design is also reversed present in the design. Example, row 3 is row 1 reversed. For small designs this property can be used to generate the designs by brute force. Example; a four by four design has without loss of generality the first row and column designated 1 to 4 (using . as unknown).
1 2 3 4
2 . . .
3 . . .
4 . . .
Adding the reversal of the first row gives:
1 2 3 4
2 . . .
3 . . .
4 3 2 1
In practice, for an even number of products the last column can be created as reversed first column.
1 2 3 4
2 . . 3
3 . . 2
4 3 2 1
It is rather obvious that only one solution remains for the 2,2 location and the rest is simple filling in the blanks. The resulting design is the same as the solution of williams(4) with '3' and '4' permuted.
1 2 3 4
2 4 . 3
3 . . 2
4 3 2 1
It is possible to use the same approach for small designs with an even number of products. For an odd number of products the number of rows has to be doubled so this will follow in a later post. To create the design with 6 products a program it is more convenient than manual work. It appears, unknown to many, that using this approach there are two solutions for 6 products. These two solutions are not permutations of each other!
[[1]]
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    1    2    3    4    5    6
[2,]    2    4    1    6    3    5
[3,]    3    1    5    2    6    4
[4,]    4    6    2    5    1    3
[5,]    5    3    6    1    4    2
[6,]    6    5    4    3    2    1

[[2]]
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    1    2    3    4    5    6
[2,]    2    4    6    1    3    5
[3,]    3    6    2    5    1    4
[4,]    4    1    5    2    6    3
[5,]    5    3    1    6    4    2
[6,]    6    5    4    3    2    1

There are 8 solutions for 8 products and 192 solutions for 10 products. Above that, calculation time is prohibitive. Even to get to 10, the program had to be streamlined considerably.

R code

gendesign <- function(n=6) {
nr <- as.integer(n)
nc <- nr
desmat <- matrix(NA,nrow=nr,ncol=nc)
desmat[1,] <- 1L:nc
desmat[,1] <- 1L:nr
desmat[nr,] <- nc:1L
desmat[,nc] <- nr:1L
carover <- matrix(0L,nrow=nr,ncol=nc)
for (i in 1L:(nc-1L)) carover[i+1,i] <- carover[i,i+1] <- 1L
desobject <- list(desmat=desmat,carover = carover)
desresult <- list()
addpoint(desobject,desresult)
}

nextpos <- function(desmat) which(is.na(desmat),arr.ind=TRUE)

checkdes <- function(desobject,row,col) {
# test for only once carry over 
all(desobject$carover<=1) & 
# each product only once in each row and each column
!any(desobject$desmat[row,-col]== desobject$desmat[row,col],na.rm=TRUE )  &
!any(desobject$desmat[-row,col]== desobject$desmat[row,col],na.rm=TRUE )  
}

addpoint <- function(desobject,desresult) {
todo <- nextpos(desobject$desmat)
if (length(todo)==0) {
l <- length(desresult)
desresult[[l+1]] <- desobject$desmat
return(desresult)
row <- todo[1L,1L]
col <- todo[1L,2L]
nc <- ncol(desobject$desmat)
dob <- desobject
for (i in 1L:nc) {
desobject$desmat[row,col] <- i
desobject$desmat[nc-row+1,nc-col+1] <- i
desobject$carover[desobject$desmat[row,col-1L],i] <- desobject$carover[desobject$desmat[row,col-1],i] + 1L
desobject$carover[i,desobject$desmat[row,col-1L]] <- desobject$carover[i,desobject$desmat[row,col-1L]] + 1L
other <- desobject$desmat[row,col+1L]
if (!is.na(other)) {
desobject$carover[other,i] <- desobject$carover[other,i] + 1
desobject$carover[i,other] <- desobject$carover[i,other] + 1
}
if (checkdes(desobject,row,col)) desresult <- addpoint(desobject,desresult)
desobject <- dob
}
desresult
}
gendesign(6)

8 comments:

  1. It was interesting to read your blog as I have seen these two 6x6 squares before. Have you noticed that they are symmetric about both the main diagonal and the back diagonal and can be completely defined by the top left 3x3 sub-square? Simply reflect this top left quarter about the back diagonal to get the bottom right 3x3 sub-square. Then reflect these two 3x3 sub-squares about one of the mid lines and finally subtract the entries in the top-right and bottom left sub-squares from 7. Of course, the symmetries mean that the 'carry-over' property in the rows, is also present in the columns.

    One or other of these 'reduced' form squares is equivalent to the cyclic Williams square, this could be demonstrated by taking the Williams square, applying a permutation to the symbols so that the first row becomes (1 2 3 4 5 6) and the sorting the rows on the first column.

    It is not a surprise that the algorithm has problems with larger order squares, take a look at the Wikipedia page on Latin Squares and the table of the number of squares, 'combinatorial explosion' hardly does justice to how fast the numbers rise! Nevertheless, is there a way perhaps to search for only the top left sub-square, this might bring a small increase in speed?

    I also looked at the related page on odd order squares, there are single squares with carry-over balance, the smallest being 9x9, and not all orders higher than that are possible. As far as I know 11x11 is an open problem if you wanted to apply a computer search.

    ReplyDelete
    Replies
    1. I ran a little check. If you look at this design (probably messy without fixed font) it does not have that diagonal symmetry. So, using the symmetry may help, but won't give all solutions.

      [1,] 1 2 3 4 5 6 7 8
      [2,] 2 4 8 3 6 1 5 7
      [3,] 3 1 4 7 2 5 8 6
      [4,] 4 6 2 8 1 7 3 5
      [5,] 5 3 7 1 8 2 6 4
      [6,] 6 8 5 2 7 4 1 3
      [7,] 7 5 1 6 3 8 4 2
      [8,] 8 7 6 5 4 3 2 1

      Obviously I am aware of the 'combinatorial explosion', part of the trick is checking asap that some answers are not possible, hence avoiding loads of combinations further down. I may have a look at the odd designs again, thanks for the tip. I for one did not know about that 9 treatment version

      Delete
    2. I realise that the diagonal symmetry is not necessary in general for the carry-over balance, but I believe the Williams square is always equivalent to such a square. But if, as I think you are saying, that you want to find _all_ the balanced squares, then you should question the assumption that the squares must contain the reverse orders, the 9x9 square I mention above certainly does not. Also if you read the last section of:

      P.J. Owens (1976) J. of Combinatorial Theory(A) v21, 299-308.

      then he finds 12 carry-over balanced order 8 squares, where you have only found 8. Quite some feat with the computing power of the mid 1970s, I would actually love to know how he did it.

      Delete
    3. If you just want the Williams, there is an efficient method for that. On the other hand, the 12 carry-over designs of size 8, that will be smart programming. I would love to see his algorithm to. Probably Fortran 4 or assembler, quite the opposite in efficiency from R. Still, 1976, I'm very impressed

      Delete
    4. The point that I was trying to make, is that there is a whole class of 'Williams like' squares here, and for order six you have shown that there are exactly two of these, the classic square (the first square above) and then another different square, having the same symmetry that makes it equivalent to a cyclic square. This class of square will be subject to a similar, but hopefully smaller explosion, so a more tractable problem than the one you have tackled, may be to look for an efficient method of enumerating all the members of this class of squares. There are certainly more tricks that can be employed in the algorithm.

      Fisher & Yates held to the notion that you should pick one square at random from all that exist. But isn't that no longer found to be necessary? So all this is really academic interest - nothing wrong with that of course.

      Delete
    5. Hi. Not sure if you saw this comment but thought you were interested:
      "Note that there are 492, not 192, unique solutions of order 10. This Web page lists them all: http://users.monash.edu.au/~iwanless/data/RCLS/ "

      Delete
  2. Note that there are 492, not 192, unique solutions of order 10. This Web page lists them all: http://users.monash.edu.au/~iwanless/data/RCLS/

    It also lists the number of complete squares, i.e., squares where the same carry-over property holds for the columns. (Somewhat confusingly, the number of complete squares of a certain order is greater than the number of row-complete squares of the same order. But it makes sense when you think about it.)

    ReplyDelete
    Replies
    1. I am not surprised there are more than 192. After all, with 8 there were more than the algorithm in this post revealed. I am surprised somebody made this nice collection. I did not know latin squares was still an active subject of research. Thanks for the link.

      Delete