[R] Permutations (summary)

[Jordi Altirriba Gutiérrez]

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