RE: [R] Permutations (summary)

From: Jordi Altirriba Gutiérrez <altirriba_at_hotmail.com>
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