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
