From: Jordi Altirriba Gutiérrez <altirriba_at_hotmail.com>

Date: Sat 17 Jul 2004 - 00:08:16 EST

R-help@stat.math.ethz.ch mailing list

https://www.stat.math.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html Received on Sat Jul 17 00:25:30 2004

Date: Sat 17 Jul 2004 - 00:08:16 EST

Dear R users,

This is a second summary of the permutation problem I previously posted. This summary restates the problem as well as the solution.

First of all thanks to everyone including Erich, Robin, Gabor, Christian,
Ingmar and others for your suggestions.

With the help of an off-list discussion with Gabor I’m going to summarize.

**THE PROBLEM
**
We have 12 elements in blocks of 3 :

1 2 3 | 4 5 6 | 7 8 9 | 10 11 12

and we want to generate random permutations of these 12 elements such that no permutation so generated can be obtained solely through intra-block permutations of some previously generated permutation.

In the last sentence intra-block permutations are those permutations which shuffle the first three numbers among themselves, the second three numbers among themselves, the third three numbers among themselves and the fourth three numbers among themselves. Numbers in one block cannot be permuted into another block through an intra-block permutation. (That would be an inter-block permutation.)

For example, if we consider the following potential candidates as successive permutations the first is ok, the second is not since its an intra-block permutation of the first (thus the 2nd would be rejected) and the third is ok since it is not an intra-block permutation of the first.

1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 ---> perm 1
1 3 2 | 4 5 6 | 7 8 9 | 10 11 12 ---> perm 2. NO, swapping 2 & 3 is
intra-block

1 2 4 | 3 5 6 | 7 8 9 | 10 11 12 ---> perm 3. YES, swapping 3 & 4 is
inter-block

Here is another example where perm 2 is ok but perm 3 would be rejected as perm 3 is an intra-block permutation of perm 2.

1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 ---> perm 1
5 8 10 | 7 9 4 | 12 1 3 | 11 6 2 ---> perm 2. YES. not an intra-block perm
of 1

5 10 8 | 7 9 4 | 12 1 3 | 11 6 2 ---> perm 3. NO. is intra-block perm of
perm 2

**SOLUTION
**
Erich Neuwirth defined ordered permutations to be permutations that are
increasing within each block. The ordered permutation corresponding to an
arbitrary permutation of 12 elements is formed by sorting all elements
within each of the 4 blocks to make them increasing.

With this in mind we can redefine the problem as requiring the generation of random permutations such no two permutations on our list can correspond to the same ordered permutation.

Gabor Grothendieck provided the following code which uses this idea. samp()
generates a permutation of 12 that is stored in z[i,] and returns the
ordered permutation that corresponds to it. Each iteration of the for loop
generates one random permutation using rejection. That is, each such
iteration uses a while loop to repeatedly call samp converting the resulting
ordered permutation to a string and looking it up in z, the vector of all
previously accepted ordered

permutations. If its found then the while loop tries again and if it is NOT
found then the permutation that samp just stored in z[i,] is accepted.

The code is followed by a test generating 10,000 random permutations.

ordered.perm2 <- function(N) {

samp <- function() c(apply(matrix(z[i,] <<- sample(12,12),3),2,sort))
s <- vector(length = N, mode = "character")
z <- matrix(nr = N, nc = 12)

for(i in 1:N)

while( (s[i]<-paste(samp(),collapse=" ")) %in% s[seq(len=i-1)] ) {}
z

}

set.seed(1)

ordered.perm2(10000)

**KIRKMAN SCHOOL GIRL PROBLEM
**
Christian pointed out the Kirkman School Girl Problem.
It is intrigingly similar to the current problem. At the same time it is
not exactly the same because the present problem can permute only one
element and Kirkman's School Girl Problem can not.

For example, the following is an acceptable permutation in our problem but not for the Kirkman problem:

1 2 3 | 4 5 6 | 7 8 9 | 10 11 12

1 2 4 | 3 5 6 | 7 8 9 | 10 11 12

For Kirkman’s problem, the four blocks should be different in the two permutations.

Thanks to all, and sorry for the initial confusion with intra-block permutations,

Jordi Altirriba

PhD student

Hospital Clinic - Barcelona - Spain

R-help@stat.math.ethz.ch mailing list

https://www.stat.math.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html Received on Sat Jul 17 00:25:30 2004

*
This archive was generated by hypermail 2.1.8
: Wed 03 Nov 2004 - 22:55:03 EST
*