Dear R users,
I?m a beginner user of R and I?ve a problem with permutations that I don?t
know how to solve. I?ve 12 elements in blocks of 3 elements and I want only
to make permutations inter-blocks (no intra-blocks) (sorry if the
terminology is not accurate), something similar to:
1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 ----------1st permutation
1 3 2 | 4 5 6 | 7 8 9 | 10 11 12 NO
- -
3 2 1 | 4 5 6 | 7 8 9 | 10 11 12 NO
- - -
1 2 4 | 3 5 6 | 7 8 9 | 10 11 12 YES-----2nd permutation
- -
4 5 6 | 1 2 3 | 7 8 9 | 10 11 12 YES-----3rd permutation
- - - - - -
4 5 6 | 2 1 3 | 7 8 9 | 10 11 12 NO
- -
....
Thanks for your time,
Jordi Altirriba
Ph D student
Hospital Clinic - Barcelona - Spain
MSN Motor. http://motor.msn.es/researchcentre/
On Tue, 2004-07-13 at 14:07, Jordi Altirriba Guti伱仼rrez wrote:> Dear R users, > Im a beginner user of R and Ive a problem with permutations that I dont > know how to solve. Ive 12 elements in blocks of 3 elements and I want only > to make permutations inter-blocks (no intra-blocks) (sorry if the > terminology is not accurate), something similar to: > > 1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 ----------1st permutation > > 1 3 2 | 4 5 6 | 7 8 9 | 10 11 12 NO > - - > 3 2 1 | 4 5 6 | 7 8 9 | 10 11 12 NO > - - - > 1 2 4 | 3 5 6 | 7 8 9 | 10 11 12 YES-----2nd permutation > - - > 4 5 6 | 1 2 3 | 7 8 9 | 10 11 12 YES-----3rd permutation > - - - - - - > 4 5 6 | 2 1 3 | 7 8 9 | 10 11 12 NO > - - > ....You can use the permutations() function in the 'gregmisc' package on CRAN: # Assuming you installed 'gregmisc' and used library(gregmisc) # First create 'groups' consisting of the four blocks groups <- c("1 2 3", "4 5 6", "7 8 9", "10 11 12") # Now create a 4 column matrix containing the permutations # The call to permutations() here indicates the number of blocks in # groups (4), the required length of the output (4) and the vector of # elements to permute perms <- matrix(permutations(4, 4, groups), ncol = 4)> perms[,1] [,2] [,3] [,4] [1,] "1 2 3" "10 11 12" "4 5 6" "7 8 9" [2,] "1 2 3" "10 11 12" "7 8 9" "4 5 6" [3,] "1 2 3" "4 5 6" "10 11 12" "7 8 9" [4,] "1 2 3" "4 5 6" "7 8 9" "10 11 12" [5,] "1 2 3" "7 8 9" "10 11 12" "4 5 6" [6,] "1 2 3" "7 8 9" "4 5 6" "10 11 12" [7,] "10 11 12" "1 2 3" "4 5 6" "7 8 9" [8,] "10 11 12" "1 2 3" "7 8 9" "4 5 6" [9,] "10 11 12" "4 5 6" "1 2 3" "7 8 9" [10,] "10 11 12" "4 5 6" "7 8 9" "1 2 3" [11,] "10 11 12" "7 8 9" "1 2 3" "4 5 6" [12,] "10 11 12" "7 8 9" "4 5 6" "1 2 3" [13,] "4 5 6" "1 2 3" "10 11 12" "7 8 9" [14,] "4 5 6" "1 2 3" "7 8 9" "10 11 12" [15,] "4 5 6" "10 11 12" "1 2 3" "7 8 9" [16,] "4 5 6" "10 11 12" "7 8 9" "1 2 3" [17,] "4 5 6" "7 8 9" "1 2 3" "10 11 12" [18,] "4 5 6" "7 8 9" "10 11 12" "1 2 3" [19,] "7 8 9" "1 2 3" "10 11 12" "4 5 6" [20,] "7 8 9" "1 2 3" "4 5 6" "10 11 12" [21,] "7 8 9" "10 11 12" "1 2 3" "4 5 6" [22,] "7 8 9" "10 11 12" "4 5 6" "1 2 3" [23,] "7 8 9" "4 5 6" "1 2 3" "10 11 12" [24,] "7 8 9" "4 5 6" "10 11 12" "1 2 3" HTH, Marc Schwartz
Marc Schwartz wrote (in response to a question from Jordi Altirriba):> You can use the permutations() function in the 'gregmisc' package on > CRAN: > > # Assuming you installed 'gregmisc' and used library(gregmisc) > # First create 'groups' consisting of the four blocks > groups <- c("1 2 3", "4 5 6", "7 8 9", "10 11 12") > > # Now create a 4 column matrix containing the permutations > # The call to permutations() here indicates the number of blocks in > # groups (4), the required length of the output (4) and the vector of > # elements to permute > perms <- matrix(permutations(4, 4, groups), ncol = 4) > > > perms > [,1] [,2] [,3] [,4] > [1,] "1 2 3" "10 11 12" "4 5 6" "7 8 9" > [2,] "1 2 3" "10 11 12" "7 8 9" "4 5 6" > [3,] "1 2 3" "4 5 6" "10 11 12" "7 8 9" > [4,] "1 2 3" "4 5 6" "7 8 9" "10 11 12" > [5,] "1 2 3" "7 8 9" "10 11 12" "4 5 6" > [6,] "1 2 3" "7 8 9" "4 5 6" "10 11 12" > [7,] "10 11 12" "1 2 3" "4 5 6" "7 8 9" > [8,] "10 11 12" "1 2 3" "7 8 9" "4 5 6" > [9,] "10 11 12" "4 5 6" "1 2 3" "7 8 9" > [10,] "10 11 12" "4 5 6" "7 8 9" "1 2 3" > [11,] "10 11 12" "7 8 9" "1 2 3" "4 5 6" > [12,] "10 11 12" "7 8 9" "4 5 6" "1 2 3" > [13,] "4 5 6" "1 2 3" "10 11 12" "7 8 9" > [14,] "4 5 6" "1 2 3" "7 8 9" "10 11 12" > [15,] "4 5 6" "10 11 12" "1 2 3" "7 8 9" > [16,] "4 5 6" "10 11 12" "7 8 9" "1 2 3" > [17,] "4 5 6" "7 8 9" "1 2 3" "10 11 12" > [18,] "4 5 6" "7 8 9" "10 11 12" "1 2 3" > [19,] "7 8 9" "1 2 3" "10 11 12" "4 5 6" > [20,] "7 8 9" "1 2 3" "4 5 6" "10 11 12" > [21,] "7 8 9" "10 11 12" "1 2 3" "4 5 6" > [22,] "7 8 9" "10 11 12" "4 5 6" "1 2 3" > [23,] "7 8 9" "4 5 6" "1 2 3" "10 11 12" > [24,] "7 8 9" "4 5 6" "10 11 12" "1 2 3"This does not solve the problem that was posed. It only permutes the blocks, and does not allow for swapping between blocks. For instance it does produce the ``acceptable'' permutation 1 2 4 | 3 5 6 | 7 8 9 | 10 11 12 YES-----2nd permutation I would guess that a correct solution is likely to be pretty difficult. I mean, one ***could*** just generate all 12! permutations of 1 to 12 and filter out the unacceptable ones. But this is getting unwieldy (12! is close to half a billion) and is inelegant. And the method does not ``generalize'' worth a damn. cheers, Rolf Turner rolf at math.unb.ca
I may be confused, but I think what you described will produce greater than
472 million permutations. I think your second permutation <1 2 4 | 3 5 6 |
7 8 9 | 10 11 12 YES-----2nd permutation> shows that you want more than
just a permutation of entire blocks.
There are a total of 12! (12 factorial) permutations of 1:12 ignoring your
blocking restriction.
There are 3! * 9! Permutations in which the first block has an intrablock
permutation and the rest of the 9 symbols can do anything. Since there are
4 blocks then there are fewer than 4 * 3! * 9! permutations with intra-block
transfers (this 4*3!*9! double counts some intrablock permutations - you
need to take out of the 9! the count of intra-block only permutations among
the remaining 9 symbols: 3!*3!*3!).
This gives more than
12! - 4*3!*9! + 1 = 9!*[12*11*10 - 4*3*2*1] + 1 = 12*9![110 - 2] + 1 ~ 472
million permutations.
How could you possibly deal with all of these permutations? If you can deal
with this much junk then maybe you can generate all 12! Permutations and
take out the ones you don't want.
Sorry if I got it totally wrong
bob
-----Original Message-----
From: Jordi Altirriba Guti??rrez [mailto:altirriba at hotmail.com]
Sent: Tuesday, July 13, 2004 3:07 PM
To: r-help at stat.math.ethz.ch
Subject: [R] Permutations
Dear R users,
I'm a beginner user of R and I've a problem with permutations that I
don't
know how to solve. I've 12 elements in blocks of 3 elements and I want only
to make permutations inter-blocks (no intra-blocks) (sorry if the
terminology is not accurate), something similar to:
1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 ----------1st permutation
1 3 2 | 4 5 6 | 7 8 9 | 10 11 12 NO
- -
3 2 1 | 4 5 6 | 7 8 9 | 10 11 12 NO
- - -
1 2 4 | 3 5 6 | 7 8 9 | 10 11 12 YES-----2nd permutation
- -
4 5 6 | 1 2 3 | 7 8 9 | 10 11 12 YES-----3rd permutation
- - - - - -
4 5 6 | 2 1 3 | 7 8 9 | 10 11 12 NO
- -
....
Thanks for your time,
Jordi Altirriba
Ph D student
Hospital Clinic - Barcelona - Spain
MSN Motor. http://motor.msn.es/researchcentre/
______________________________________________
R-help at 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
As has been pointed out by Robert Baskin, your ``restricted''
permutations comprise the bulk of all permutations; i.e. the
restriction isn't as restrictive as one might have expected.
So constructing ***all*** restricted permutations is probably not
very useful.
However if you simply wish to ***generate*** restricted permutations
at random, then your problem is (I think) solvable as follows:
===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+==restr.perm
<- function ()
{
S <- 4:12
G <- NULL
A <- list(1:3,4:6,7:9,10:12)
for(k in 1:4) {
for(i in A[[k]]) {
tmp <- union(i,S)
tmp <- setdiff(tmp,G)
x <- if(length(tmp)==1) tmp else sample(tmp,1)
G <- c(G,x)
S <- setdiff(S,G)
}
S <- union(S,A[[k]])
R <- if(k < 4) A[[k+1]] else NULL
R <- union(R,G)
S <- setdiff(S,R)
}
G
}
===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+==
Sample output:
> set.seed(42)
> restr.perm()
[1] 12 11 5 2 10 9 4 8 3 7 1 6
> restr.perm()
[1] 10 12 5 9 3 2 7 1 4 8 11 6
which look O.K. according to my understanding of your criterion
for ``acceptable'' permutations.
cheers,
Rolf Turner
rolf at math.unb.ca
Jordi Altirriba wrote:
> Dear R users,
> I'm a beginner user of R and I've a problem with permutations that
I
> don't know how to solve. I've 12 elements in blocks of 3 elements
and
> I want only to make permutations inter-blocks (no intra-blocks)
> (sorry if the terminology is not accurate), something similar to:
>
> 1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 ----------1st permutation
>
> 1 3 2 | 4 5 6 | 7 8 9 | 10 11 12 NO
> - -
> 3 2 1 | 4 5 6 | 7 8 9 | 10 11 12 NO
> - - -
> 1 2 4 | 3 5 6 | 7 8 9 | 10 11 12 YES-----2nd permutation
> - -
> 4 5 6 | 1 2 3 | 7 8 9 | 10 11 12 YES-----3rd permutation
> - - - - - -
> 4 5 6 | 2 1 3 | 7 8 9 | 10 11 12 NO
> - -
> ....
>
> Thanks for your time,
>
> Jordi Altirriba
> Ph D student
>
> Hospital Clinic - Barcelona - Spain
>
>
> MSN Motor. http://motor.msn.es/researchcentre/
>
> ______________________________________________
> R-help at 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
>
> From r-help-bounces at stat.math.ethz.ch Tue Jul 13 17:19:55 2004
> From: "Baskin, Robert" <RBaskin at ahrq.gov>
> To: =?iso-8859-1?Q?=27Jordi_Altirriba_Guti=E9rrez=27?= <altirriba at
hotmail.com>,
> r-help at stat.math.ethz.ch
> Subject: RE: [R] Permutations
> Date: Tue, 13 Jul 2004 16:12:46 -0400
> MIME-Version: 1.0
> X-OriginalArrivalTime: 13 Jul 2004 20:14:08.0328 (UTC)
> FILETIME=[F4123480:01C46915]
> Received-SPF: none (hypatia: domain of r-help-bounces at stat.math.ethz.ch
does not designate permitted sender hosts)
> Received-SPF: none (hypatia: domain of rbaskin at ahrq.gov does not
designate
> permitted sender hosts)
> X-Virus-Scanned: by amavisd-new at stat.math.ethz.ch
> Content-Transfer-Encoding: 8bit
> X-MIME-Autoconverted: from quoted-printable to 8bit by hypatia.math.ethz.ch
id
> i6DKABdp031609
> Cc:
> X-BeenThere: r-help at stat.math.ethz.ch
> X-Mailman-Version: 2.1.5
> List-Id: "Main R Mailing List: Primary help"
<r-help.stat.math.ethz.ch>
> List-Unsubscribe:
<https://www.stat.math.ethz.ch/mailman/listinfo/r-help>,
> <mailto:r-help-request at stat.math.ethz.ch?subject=unsubscribe>
> List-Archive: <https://www.stat.math.ethz.ch/pipermail/r-help>
> List-Post: <mailto:r-help at stat.math.ethz.ch>
> List-Help: <mailto:r-help-request at stat.math.ethz.ch?subject=help>
> List-Subscribe:
<https://www.stat.math.ethz.ch/mailman/listinfo/r-help>,
> <mailto:r-help-request at stat.math.ethz.ch?subject=subscribe>
> X-Spam-Math-Flag: NO
> X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on erdos.math.unb.ca
> X-Spam-Math-Status: No, hits=-4.9 required=5.0 tests=BAYES_00 autolearn=ham
> version=2.63
>
> I may be confused, but I think what you described will produce greater than
> 472 million permutations. I think your second permutation <1 2 4 | 3 5
6 |
> 7 8 9 | 10 11 12 YES-----2nd permutation> shows that you want more
than
> just a permutation of entire blocks.
>
> There are a total of 12! (12 factorial) permutations of 1:12 ignoring your
> blocking restriction.
>
> There are 3! * 9! Permutations in which the first block has an intrablock
> permutation and the rest of the 9 symbols can do anything. Since there are
> 4 blocks then there are fewer than 4 * 3! * 9! permutations with
intra-block
> transfers (this 4*3!*9! double counts some intrablock permutations - you
> need to take out of the 9! the count of intra-block only permutations among
> the remaining 9 symbols: 3!*3!*3!).
>
> This gives more than
> 12! - 4*3!*9! + 1 = 9!*[12*11*10 - 4*3*2*1] + 1 = 12*9![110 - 2] + 1 ~ 472
> million permutations.
>
> How could you possibly deal with all of these permutations? If you can
deal
> with this much junk then maybe you can generate all 12! Permutations and
> take out the ones you don't want.
>
> Sorry if I got it totally wrong
> bob
>
>
>
> -----Original Message-----
> From: Jordi Altirriba Guti??rrez [mailto:altirriba at hotmail.com]
> Sent: Tuesday, July 13, 2004 3:07 PM
> To: r-help at stat.math.ethz.ch
> Subject: [R] Permutations
>
>
> Dear R users,
> I'm a beginner user of R and I've a problem with permutations that
I don't
> know how to solve. I've 12 elements in blocks of 3 elements and I want
only
> to make permutations inter-blocks (no intra-blocks) (sorry if the
> terminology is not accurate), something similar to:
>
> 1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 ----------1st permutation
>
> 1 3 2 | 4 5 6 | 7 8 9 | 10 11 12 NO
> - -
> 3 2 1 | 4 5 6 | 7 8 9 | 10 11 12 NO
> - - -
> 1 2 4 | 3 5 6 | 7 8 9 | 10 11 12 YES-----2nd permutation
> - -
> 4 5 6 | 1 2 3 | 7 8 9 | 10 11 12 YES-----3rd permutation
> - - - - - -
> 4 5 6 | 2 1 3 | 7 8 9 | 10 11 12 NO
> - -
> ....
>
> Thanks for your time,
>
> Jordi Altirriba
> Ph D student
>
> Hospital Clinic - Barcelona - Spain
>
>
> MSN Motor. http://motor.msn.es/researchcentre/
Dang!!! Forget it. My random restricted permutation generator doesn't ``quite'' work. Further testing --- which I should've done before posting (sigh) --- reveals that it can get into a situation in which there's nothing left to sample from, and it still needs to fill out the permutation. I.e. it has painted itself into a corner. Perhaps one could put in a test for this situation and just start again if it happens, but this makes me uneasy. What happens to the ``equal probability'' of all the generated permutations? Mebbe somebody else can come up with something cleverer. Sorry if I got your hopes up. cheers, Rolf Turner rolf at math.unb.ca
Jordi:
If I understand you well, the function below may do what you asked for.
It is not clear to me from your posting wether e.g.
1 2 4 3 5 6 7 8 9 10 11 12
and
1 4 2 3 5 6 7 8 9 10 11 12
should count as differente permutations, i.e., wether once one pair of
elements interchange their
blocks, permutations within any block are allowable. I have assumed that
only one pair of
elements are interchanged (but the function could be modified to account
for other possibilities).
> permutations
function(elements,blocks) {
n <- length(elements)
el.per.block <- n / blocks
for (i in 1:n) { # For each element in turn,
b <- floor(i/(el.per.block+.1))+1 # find which block it belongs to.
if (b==blocks) # If in the last block, we are done.
break
allow.pos <- b*el.per.block + 1 # Find first position it could
migrate to...
for (j in (allow.pos:n)) { # and create permutations with
all allowable
perm <- elements # interchanges.
perm[i] <- elements[j]
perm[j] <- elements[i]
print(perm)
}
}
}
> permutations(1:4,2)
[1] 3 2 1 4
[1] 4 2 3 1
[1] 1 3 2 4
[1] 1 4 3 2
> permutations(1:6,2)
[1] 4 2 3 1 5 6
[1] 5 2 3 4 1 6
[1] 6 2 3 4 5 1
[1] 1 4 3 2 5 6
[1] 1 5 3 4 2 6
[1] 1 6 3 4 5 2
[1] 1 2 4 3 5 6
[1] 1 2 5 4 3 6
[1] 1 2 6 4 5 3
> permutations(1:9,3)
[1] 4 2 3 1 5 6 7 8 9
[1] 5 2 3 4 1 6 7 8 9
[1] 6 2 3 4 5 1 7 8 9
[1] 7 2 3 4 5 6 1 8 9
[1] 8 2 3 4 5 6 7 1 9
[1] 9 2 3 4 5 6 7 8 1
[1] 1 4 3 2 5 6 7 8 9
[1] 1 5 3 4 2 6 7 8 9
[1] 1 6 3 4 5 2 7 8 9
[1] 1 7 3 4 5 6 2 8 9
[1] 1 8 3 4 5 6 7 2 9
[1] 1 9 3 4 5 6 7 8 2
[1] 1 2 4 3 5 6 7 8 9
[1] 1 2 5 4 3 6 7 8 9
[1] 1 2 6 4 5 3 7 8 9
[1] 1 2 7 4 5 6 3 8 9
[1] 1 2 8 4 5 6 7 3 9
[1] 1 2 9 4 5 6 7 8 3
[1] 1 2 3 7 5 6 4 8 9
[1] 1 2 3 8 5 6 7 4 9
[1] 1 2 3 9 5 6 7 8 4
[1] 1 2 3 4 7 6 5 8 9
[1] 1 2 3 4 8 6 7 5 9
[1] 1 2 3 4 9 6 7 8 5
[1] 1 2 3 4 5 7 6 8 9
[1] 1 2 3 4 5 8 7 6 9
[1] 1 2 3 4 5 9 7 8 6
Notice that no error checking of any kind is done: one should check,
e.g. that el.per.block is
integer.
Best,
ft.
--
Fernando TUSELL e-mail:
Departamento de Econometr??a y Estad??stica etptupaf at bs.ehu.es
Facultad de CC.EE. y Empresariales Tel: (+34)94.601.3733
Avenida Lendakari Aguirre, 83 Fax: (+34)94.601.3754
E-48015 BILBAO (Spain) Secr: (+34)94.601.3740
Perhaps what you want might better be described as ordered partitions? Is what you want the following: We study sequences of length 12 and divide them in 4 segments position 1 2 3, position 4 5 6, position 7 8 9, position 10 11 12, Find all permutation sequences of the numbers 1 to 12 with the property that all segment sequences are monotonically increasing. I think that produces what you need. Since the segments are ordered, you avoid intra-block permutations. If that is what you want, writing a recursive function should not be too hard. Jordi Altirriba Guti侀rrez wrote:> Dear R users, > I抦 a beginner user of R and I抳e a problem with permutations that I > don抰 know how to solve. I抳e 12 elements in blocks of 3 elements and I > want only to make permutations inter-blocks (no intra-blocks) (sorry if > the terminology is not accurate), something similar to: > > 1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 ----------1st permutation > > 1 3 2 | 4 5 6 | 7 8 9 | 10 11 12 NO > - - > 3 2 1 | 4 5 6 | 7 8 9 | 10 11 12 NO > - - - > 1 2 4 | 3 5 6 | 7 8 9 | 10 11 12 YES-----2nd permutation > - - > 4 5 6 | 1 2 3 | 7 8 9 | 10 11 12 YES-----3rd permutation > - - - - - - > 4 5 6 | 2 1 3 | 7 8 9 | 10 11 12 NO > - - > .... > > Thanks for your time, > > Jordi Altirriba > Ph D student > > Hospital Clinic - Barcelona - Spain > > > MSN Motor. http://motor.msn.es/researchcentre/ > > ______________________________________________ > R-help at 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 >-- Erich Neuwirth, Computer Supported Didactics Working Group Visit our SunSITE at http://sunsite.univie.ac.at Phone: +43-1-4277-38624 Fax: +43-1-4277-9386
In respect of generating random ``restricted'' permutations, it
occurred to me as I was driving home last night .... If one is going
to invoke some kind of ``try again if it doesn't work procedure''
then one might as well keep it simple: Essentially use the rejection
method. Just generate a random permutation, and then check whether
it meets the restriction criterion. If yes, return that
permutation, if not, throw it away and try again.
This will definitely (???) genererate a genuinely random restricted
permutation. I figured that since a very large fraction of permutations
are acutally restricted permutions one wouldn't reject much of the
time, and so the rejection method should be pretty efficient.
I wrote the following code to do the work:
restr.perm2 <- function () {
#
okay <- function (x) {
m1 <- cbind(1:12,rep(1:4,rep(3,4)))
m2 <- m1[x,]
all((m2[,1] == m1[,1]) | (m2[,2] != m1[,2]))
}
#
repeat{
x <- sample(12,12)
if(okay(x)) return(x)
}
}
I'm bothered again, but: I did a little test to see how many tries
it would take on average. On 1000 attempts I got a mean of 8.44
tries, with a standard deviation of 7.7610 (standard error of the
mean = 0.2454). The value of 7.76 is roughly consistent with
sqrt(1-p.hat)/p.hat = 7.92 that one gets from the geometric
distribution.
This would indicate that the fraction of ``restricted'' permutations
is something like p.hat = 1/8.44 = 0.1184834. Which is a lot less
than the rough estimate of (4.7 x 10^6)/12! approx. = 0.9853 from
Robert Baskin's back-of-the-envelope calculations.
What's going on/wrong?
cheers,
Rolf Turner
rolf at math.unb.ca
Dear R users, First of all, thanks to Rolf, Brad, Robin, Erich, Fernando and Adaikalavan for your time and suggestions. I?ve been testing some algorithms (sorry for the delay, I?m very slow, and I?m a completely beginner in R?s world). First, the Robin algorithm. I think that there is a problem because I?ve done 200 permutations and I?ve found that these permutations are the same: 52 and 91, 99 and 110, 121 and 122, 51 and 141, 130 and 134. Thanks again, Jordi Altirriba Hospital Clinic - Barcelona - Spain>x <- c(1,2,3,4,5,6,7,8,9,10,11,12) >dim(x) <- c(3,4) a<-matrix(1,200,12) >for (i in 1:200)+ { + jj <- t(apply(x,1,sample)) + a[i,]<-as.vector(jj) + }>a[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [1,] 7 2 3 1 11 6 4 8 9 10 5 12 [2,] 1 2 9 7 11 6 4 8 12 10 5 3 [3,] 7 2 9 1 11 3 4 5 6 10 8 12 [4,] 10 8 6 4 5 12 7 2 9 1 11 3 [5,] 10 2 12 1 11 9 7 8 6 4 5 3 [6,] 7 8 6 1 5 9 4 11 12 10 2 3 [7,] 1 5 12 7 2 6 4 8 9 10 11 3 [8,] 1 5 9 10 8 6 4 2 3 7 11 12 [9,] 1 11 6 7 2 12 4 5 9 10 8 3 [10,] 4 5 12 10 11 9 1 8 6 7 2 3 [11,] 1 11 9 7 5 6 4 8 12 10 2 3 [12,] 1 8 3 4 2 12 10 5 9 7 11 6 [13,] 1 2 3 7 11 6 10 5 12 4 8 9 [14,] 4 8 3 10 5 12 7 2 9 1 11 6 [15,] 10 2 3 4 8 6 7 11 9 1 5 12 [16,] 4 8 9 10 2 12 7 5 6 1 11 3 [17,] 1 2 6 10 5 3 7 8 12 4 11 9 [18,] 10 2 9 4 11 12 1 5 6 7 8 3 [19,] 4 8 6 7 11 12 1 2 9 10 5 3 [20,] 1 8 12 7 2 3 10 11 6 4 5 9 [21,] 10 2 12 1 5 9 7 11 6 4 8 3 [22,] 4 11 12 1 2 3 10 8 6 7 5 9 [23,] 1 11 3 7 2 6 10 5 9 4 8 12 [24,] 7 2 9 10 5 12 1 11 3 4 8 6 [25,] 7 8 9 1 2 6 4 5 3 10 11 12 [26,] 4 5 12 10 2 3 7 11 6 1 8 9 [27,] 4 5 9 1 11 3 7 8 12 10 2 6 [28,] 1 5 6 4 11 3 7 8 9 10 2 12 [29,] 4 5 6 1 11 9 10 2 12 7 8 3 [30,] 4 11 3 7 8 12 10 5 6 1 2 9 [31,] 10 2 3 1 11 6 7 8 9 4 5 12 [32,] 10 2 3 7 8 9 1 11 6 4 5 12 [33,] 7 11 6 1 8 9 4 5 12 10 2 3 [34,] 7 5 12 1 8 6 4 11 3 10 2 9 [35,] 1 2 3 4 8 6 7 5 9 10 11 12 [36,] 7 8 3 1 11 9 10 2 12 4 5 6 [37,] 10 2 6 1 11 12 7 5 3 4 8 9 [38,] 1 5 9 4 11 12 7 8 3 10 2 6 [39,] 1 2 12 7 5 9 10 8 3 4 11 6 [40,] 1 8 3 10 2 12 7 11 6 4 5 9 [41,] 1 2 9 4 8 3 10 11 12 7 5 6 [42,] 4 5 6 1 2 9 10 8 3 7 11 12 [43,] 1 2 6 7 11 12 10 5 9 4 8 3 [44,] 1 2 9 10 11 12 4 8 6 7 5 3 [45,] 10 5 9 7 11 6 4 2 3 1 8 12 [46,] 1 2 3 4 11 6 7 5 9 10 8 12 [47,] 4 2 6 1 8 3 10 5 12 7 11 9 [48,] 4 8 9 7 2 3 1 5 12 10 11 6 [49,] 10 8 12 1 2 9 4 11 3 7 5 6 [50,] 10 8 6 1 2 3 7 5 12 4 11 9 [51,] 7 2 12 10 11 6 4 8 3 1 5 9 [52,] 4 5 6 1 2 12 10 11 9 7 8 3 [53,] 1 2 3 7 5 6 4 8 9 10 11 12 [54,] 10 5 3 7 11 9 1 8 6 4 2 12 [55,] 7 11 12 4 2 3 10 8 6 1 5 9 [56,] 1 5 9 4 11 12 10 8 3 7 2 6 [57,] 4 5 9 7 11 3 10 2 6 1 8 12 [58,] 10 11 3 4 5 6 1 8 12 7 2 9 [59,] 4 8 9 10 5 6 7 2 3 1 11 12 [60,] 4 2 12 1 8 6 10 5 9 7 11 3 [61,] 4 8 6 7 11 9 10 5 12 1 2 3 [62,] 7 8 3 10 5 6 1 11 12 4 2 9 [63,] 10 5 3 7 8 6 1 2 9 4 11 12 [64,] 10 2 9 4 11 12 1 5 3 7 8 6 [65,] 1 11 6 4 8 12 7 2 3 10 5 9 [66,] 1 5 3 7 11 9 4 2 12 10 8 6 [67,] 4 2 6 7 5 12 10 8 9 1 11 3 [68,] 4 11 12 10 2 3 7 8 6 1 5 9 [69,] 4 5 6 10 2 3 7 8 9 1 11 12 [70,] 1 11 12 10 2 6 4 5 3 7 8 9 [71,] 10 5 6 7 8 12 4 2 9 1 11 3 [72,] 10 8 12 1 11 9 7 5 3 4 2 6 [73,] 10 8 3 7 11 9 4 5 12 1 2 6 [74,] 7 2 12 1 5 6 4 8 9 10 11 3 [75,] 7 2 12 10 8 9 1 11 6 4 5 3 [76,] 7 2 3 1 5 9 4 8 12 10 11 6 [77,] 1 11 3 10 5 6 7 2 9 4 8 12 [78,] 7 2 6 10 11 12 4 8 9 1 5 3 [79,] 10 8 6 7 5 3 1 2 9 4 11 12 [80,] 10 11 3 7 2 12 4 8 6 1 5 9 [81,] 10 5 6 1 8 3 4 11 9 7 2 12 [82,] 1 11 3 7 5 12 10 2 6 4 8 9 [83,] 4 11 9 10 5 12 7 2 6 1 8 3 [84,] 1 11 12 7 8 3 4 2 6 10 5 9 [85,] 10 2 9 7 5 6 1 11 12 4 8 3 [86,] 7 11 9 4 5 6 10 2 12 1 8 3 [87,] 4 5 12 7 2 3 10 11 6 1 8 9 [88,] 1 2 12 7 5 3 10 8 6 4 11 9 [89,] 1 8 12 7 11 9 10 2 6 4 5 3 [90,] 4 5 3 10 11 9 7 2 6 1 8 12 [91,] 4 5 6 1 2 12 10 11 9 7 8 3 [92,] 10 11 9 7 5 12 1 2 6 4 8 3 [93,] 4 2 3 7 8 6 1 11 12 10 5 9 [94,] 4 5 3 10 2 12 7 8 9 1 11 6 [95,] 4 8 3 10 11 9 1 2 6 7 5 12 [96,] 7 5 12 10 11 3 1 8 9 4 2 6 [97,] 4 2 3 1 8 6 7 11 9 10 5 12 [98,] 4 11 9 7 5 12 10 8 6 1 2 3 [99,] 1 11 12 4 5 6 7 8 3 10 2 9 [100,] 1 8 3 7 5 6 10 2 12 4 11 9 [101,] 7 11 6 4 8 3 1 2 12 10 5 9 [102,] 7 11 12 1 2 3 10 8 6 4 5 9 [103,] 4 5 12 1 2 9 7 8 3 10 11 6 [104,] 10 11 12 4 8 3 7 5 9 1 2 6 [105,] 10 5 9 1 2 3 4 8 6 7 11 12 [106,] 10 11 9 1 2 12 7 8 3 4 5 6 [107,] 10 11 3 4 8 9 7 5 12 1 2 6 [108,] 7 2 6 1 11 9 4 5 12 10 8 3 [109,] 1 8 6 7 2 12 10 5 3 4 11 9 [110,] 1 11 12 4 5 6 7 8 3 10 2 9 [111,] 7 8 6 1 5 3 10 2 12 4 11 9 [112,] 4 8 3 7 5 6 1 2 9 10 11 12 [113,] 1 2 9 4 11 6 7 5 3 10 8 12 [114,] 4 11 9 1 8 6 7 2 3 10 5 12 [115,] 10 8 3 4 11 12 7 2 9 1 5 6 [116,] 7 11 12 1 2 3 4 8 9 10 5 6 [117,] 1 5 3 10 11 12 7 8 9 4 2 6 [118,] 1 11 6 4 2 9 10 5 12 7 8 3 [119,] 10 2 3 1 5 9 4 8 12 7 11 6 [120,] 1 2 3 4 11 12 7 8 9 10 5 6 [121,] 7 8 3 4 5 12 10 2 6 1 11 9 [122,] 7 8 3 4 5 12 10 2 6 1 11 9 [123,] 4 5 3 10 11 9 7 8 6 1 2 12 [124,] 4 5 6 7 11 9 1 8 12 10 2 3 [125,] 10 8 6 1 11 9 4 2 12 7 5 3 [126,] 10 8 12 4 11 9 7 2 6 1 5 3 [127,] 7 8 12 1 11 6 10 5 9 4 2 3 [128,] 1 8 12 10 11 3 7 5 9 4 2 6 [129,] 7 8 3 10 2 6 1 11 9 4 5 12 [130,] 7 11 9 1 2 6 10 8 3 4 5 12 [131,] 10 2 3 4 11 9 1 5 6 7 8 12 [132,] 4 11 3 1 5 9 10 2 6 7 8 12 [133,] 10 2 12 7 8 3 4 5 6 1 11 9 [134,] 7 11 9 1 2 6 10 8 3 4 5 12 [135,] 7 8 3 4 11 6 10 2 9 1 5 12 [136,] 10 8 9 7 11 12 1 2 6 4 5 3 [137,] 10 8 12 4 5 3 1 2 9 7 11 6 [138,] 1 2 6 10 8 12 7 11 9 4 5 3 [139,] 4 5 3 7 11 9 1 2 12 10 8 6 [140,] 4 5 12 7 8 6 10 11 3 1 2 9 [141,] 7 2 12 10 11 6 4 8 3 1 5 9 [142,] 10 11 12 7 2 6 1 5 3 4 8 9 [143,] 7 2 3 10 11 6 1 8 9 4 5 12 [144,] 1 2 9 10 5 12 4 8 3 7 11 6 [145,] 1 11 6 4 8 9 7 5 12 10 2 3 [146,] 4 5 3 10 2 6 1 11 9 7 8 12 [147,] 7 11 9 1 2 3 10 8 12 4 5 6 [148,] 4 2 3 1 5 12 7 8 6 10 11 9 [149,] 10 11 12 4 8 3 1 2 9 7 5 6 [150,] 4 8 3 10 5 6 1 11 9 7 2 12 [151,] 1 8 6 10 5 9 4 11 3 7 2 12 [152,] 4 8 6 7 11 12 10 5 3 1 2 9 [153,] 7 2 3 10 5 6 4 11 9 1 8 12 [154,] 10 5 12 1 8 9 7 2 3 4 11 6 [155,] 1 8 6 4 2 9 10 5 3 7 11 12 [156,] 10 2 3 7 5 9 4 11 12 1 8 6 [157,] 10 5 3 1 2 6 7 8 9 4 11 12 [158,] 7 11 12 4 5 9 10 8 3 1 2 6 [159,] 7 5 3 1 8 12 10 2 6 4 11 9 [160,] 7 2 6 4 11 3 1 5 12 10 8 9 [161,] 7 5 3 1 2 12 4 8 9 10 11 6 [162,] 7 8 12 1 5 6 10 11 9 4 2 3 [163,] 10 11 9 4 8 6 1 2 3 7 5 12 [164,] 7 11 6 1 5 9 4 2 12 10 8 3 [165,] 4 11 9 10 8 3 7 2 12 1 5 6 [166,] 4 2 6 10 8 9 7 11 12 1 5 3 [167,] 7 5 3 10 2 12 4 8 6 1 11 9 [168,] 1 8 12 7 2 3 4 5 9 10 11 6 [169,] 7 8 12 1 5 6 4 2 3 10 11 9 [170,] 4 5 3 7 8 9 1 2 12 10 11 6 [171,] 7 11 9 1 8 6 4 2 12 10 5 3 [172,] 10 8 3 1 2 9 4 11 12 7 5 6 [173,] 10 5 12 7 8 9 4 11 3 1 2 6 [174,] 10 11 6 7 5 3 4 8 12 1 2 9 [175,] 7 11 12 1 2 3 10 8 9 4 5 6 [176,] 1 11 12 7 2 3 4 8 9 10 5 6 [177,] 10 11 12 4 5 3 7 8 6 1 2 9 [178,] 10 5 3 7 2 6 4 8 12 1 11 9 [179,] 1 5 6 7 2 9 10 11 3 4 8 12 [180,] 1 11 12 10 5 6 4 2 3 7 8 9 [181,] 7 2 12 4 11 9 1 5 6 10 8 3 [182,] 10 11 12 1 5 3 7 8 9 4 2 6 [183,] 4 8 3 1 11 9 7 2 6 10 5 12 [184,] 4 8 9 7 2 3 10 5 6 1 11 12 [185,] 10 11 9 1 5 6 7 2 12 4 8 3 [186,] 10 5 12 4 8 9 7 2 6 1 11 3 [187,] 4 2 3 1 8 6 7 5 12 10 11 9 [188,] 10 2 9 4 11 12 1 8 3 7 5 6 [189,] 10 2 12 7 11 3 4 5 9 1 8 6 [190,] 4 5 6 7 8 3 10 11 9 1 2 12 [191,] 10 5 9 1 2 3 7 11 12 4 8 6 [192,] 4 11 9 7 2 6 10 5 3 1 8 12 [193,] 10 11 12 1 2 6 4 5 9 7 8 3 [194,] 10 2 3 4 11 12 7 5 6 1 8 9 [195,] 4 2 6 7 8 9 1 11 3 10 5 12 [196,] 10 2 12 4 8 6 7 5 3 1 11 9 [197,] 7 5 12 4 11 9 1 2 3 10 8 6 [198,] 10 5 6 1 11 3 7 2 9 4 8 12 [199,] 1 2 9 7 11 3 4 8 6 10 5 12 [200,] 4 8 3 7 11 12 1 2 6 10 5 9>From: Robin Hankin <rksh at soc.soton.ac.uk> >To: Jordi Altirriba Guti??rrez <altirriba at hotmail.com> >CC: r-help at stat.math.ethz.ch >Subject: Re: [R] (no subject) (was: Permutations) >Date: Wed, 14 Jul 2004 09:11:48 +0100 > >Jordi > >try this > > >R> x <- c(1,2,3, 10,11,12, 41,42,43, 81,82,83) >R> dim(x) <- c(3,4) >R> x > [,1] [,2] [,3] [,4] >[1,] 1 10 41 81 >[2,] 2 11 42 82 >[3,] 3 12 43 83 >R> jj <- t(apply(x,1,sample)) >R> jj > [,1] [,2] [,3] [,4] >[1,] 1 41 10 81 >[2,] 2 11 82 42 >[3,] 12 3 43 83 >R> as.vector(jj) >R> > [1] 1 2 12 41 11 3 10 82 43 81 42 83 > > > > >and I think that does what you want... > >We take the vector, rearrange it into a matrix with three rows, then sample >*within* the rows, >then rearrange into a vector again. > >There will be one forbidden permutation, namely the identity (which may or >may not be >desirable). > >This method doesn't allow "intra block" permutations. > >best > >rksh > > > >> Dear R users, >> First of all, thanks for the incredibly fast answers and help of Rolf, >>Marc and Robert. >> Yes, I noticed that it was a lot of permutacions, but my intention was >>to make this process automatic and take only 5.000 - 10.000 permutations. >>Therefore, I wanted only to take that "interesting permutations" with >>"some information" [inter-block permutations]. >> The reason why I'm interested in these permutations is because I'm using >>some packages of Bioconductor to analyse my data from some microarrays and >>I thought that perhaps could be interesting to see what happens when I >>permute my data and I compare it against the not permuted data. >> Thanks again for your time and suggestions. >> >>Jordi Altirriba >>Ph. D. Student >> >>Hospital Clinic-Barcelona-Spain >> >>______________________________________________ >>R-help at 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 > > >-- >Robin Hankin >Uncertainty Analyst >Southampton Oceanography Centre >SO14 3ZH >tel +44(0)23-8059-7743 >initialDOTsurname at soc.soton.ac.uk (edit in obvious way; spam precaution)
Dear Adaikalavan,
Now I've send a similar e-mail to Robin and Rolf, therefore I can deduce
that my first e-mail was not enough clear (sorry).
Therefore, I'm going to try it again with an explanation of why I
don't
want those permutations:
I?ve 12 elements in blocks of 3 elements and I want only to make
permutations inter-blocks (no intra-blocks) (sorry if the terminology is not
accurate), something similar to:
1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 YES-------1st permutation
1 3 2 | 4 5 6 | 7 8 9 | 10 11 12 NO ----because it's an
"intra-block"
permutation of permutation 1
- -
3 2 1 | 4 5 6 | 7 8 9 | 10 11 12 NO ----because it's an
"intra-block"
permutation of permutation 1
- - -
1 2 4 | 3 5 6 | 7 8 9 | 10 11 12 YES-----2nd permutation
4 5 6 | 1 2 3 | 7 8 9 | 10 11 12 YES-----3rd permutation
4 5 6 | 2 1 3 | 7 8 9 | 10 11 12 NO ----because it's an
"intra-block"
permutation of permutation 3
- -
10 1 7 | 4 8 7 | 5 6 12 | 3 2 9 YES---Xth permutation
1 10 7 | 4 8 7 | 5 6 12 | 3 2 9 NO ----because it's an
"intra-block"permutation of permutation X
- -
So, what is a "not correct" permutation is an "intra-block"
permutation of a
permutation created before.
Again, thanks for your time and suggestions,
Jordi Altirriba
PhD student
Hospital Clinic - Barcelona - Spain
P.S. Probably (it's the way of how I'm testing the algorithms now with
Excel) [sorry if it's stupid], could be interesting something similar to:
1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 ---> 1*2*3=6 | 4*5*6=120 | 7*8*9=504 |
10*11*12=1320
1 3 2 | 4 5 6 | 7 8 9 | 10 11 12 ---> 1*3*2=6 | 4*5*6=120 | 7*8*9=504 |
10*11*12=1320
4 5 6 | 1 2 3 | 7 8 9 | 10 11 12 ---> 4*5*6=120 | 1*2*3=6 | 7*8*9=504 |
10*11*12=1320
Results:
permutation1: 6 | 120 | 504 | 1320
permutation2: 6 | 120 | 504 | 1320
permutation3: 120 | 6 | 504 | 1320
Order the permutations according first to the first parameter, second to the
second...and to the fourth.
In this case it's the same:
permutation1: 6 | 120 | 504 | 1320
permutation2: 6 | 120 | 504 | 1320
permutation3: 120 | 6 | 504 | 1320
Therefore, if the first, second, third and fourth parameter of a
permutations have the same value that the next permutation it's because
there is an "intra-block" permutation. So, permutation 2 is an
"intra-block"
permutation of permutation 1.
P.S. Sorry for having forgotten the title of the last e-mail
>From: Adaikalavan Ramasamy <ramasamy at cancer.org.uk>
>To: Jordi Altirriba Guti??rrez <altirriba at hotmail.com>
>CC: rksh at soc.soton.ac.uk, R-help <r-help at stat.math.ethz.ch>
>Subject: Re: [R] Permutations
>Date: Wed, 14 Jul 2004 18:00:49 +0100
>
>I think the issue here is in the two keywords - permutations or sample.
>
>AFAIK, permutations should return all admissible (by some rule)
>combinations. If this is a large number, as some have pointed out, then
>one essentially takes a _sample_ of all admissible combinations. Since
>you earlier mentioned that you only want 5-10 outputs, perhaps the
>correct term is sampling with restrictions.
>
>There main problem with Robin's method in that all elements within a row
>are mutually exclusive to the other. e.g. only one of either 1, 4, 7, 10
>can appear in block 1. Furthermore they can only appear in the first
>slot of the first block (so no intra-block randomness). This limits the
>number of possible outputs.
>
>Can you clearly define the rules (with examples) for an admissible
>combination ? They seem to have a different meaning every time I read
>the mail. Maybe I am just confused.
>
>
>On Wed, 2004-07-14 at 17:16, Jordi Altirriba Guti????rrez wrote:
> > Dear R users,
> > First of all, thanks to Rolf, Brad, Robin, Erich, Fernando and
>Adaikalavan
> > for your time and suggestions.
> > Ive been testing some algorithms (sorry for the delay, Im very slow,
>and
> > Im a completely beginner in Rs world).
> > First, the Robin algorithm.
> > I think that there is a problem because Ive done 200 permutations
and
> > Ive found that these permutations are the same:
> > 52 and 91, 99 and 110, 121 and 122, 51 and 141, 130 and 134.
> > Thanks again,
> >
> > Jordi Altirriba
> > Hospital Clinic Barcelona - Spain
> >
> > >x <- c(1,2,3,4,5,6,7,8,9,10,11,12)
> > >dim(x) <- c(3,4) a<-matrix(1,200,12)
> > >for (i in 1:200)
> > + {
> > + jj <- t(apply(x,1,sample))
> > + a[i,]<-as.vector(jj)
> > + }
> > >a
> > [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
> > [1,] 7 2 3 1 11 6 4 8 9 10 5 12
> > [2,] 1 2 9 7 11 6 4 8 12 10 5 3
> > [3,] 7 2 9 1 11 3 4 5 6 10 8 12
> > [4,] 10 8 6 4 5 12 7 2 9 1 11 3
> > [5,] 10 2 12 1 11 9 7 8 6 4 5 3
> > [6,] 7 8 6 1 5 9 4 11 12 10 2 3
> > [7,] 1 5 12 7 2 6 4 8 9 10 11 3
> > [8,] 1 5 9 10 8 6 4 2 3 7 11 12
> > [9,] 1 11 6 7 2 12 4 5 9 10 8 3
> > [10,] 4 5 12 10 11 9 1 8 6 7 2 3
> > [11,] 1 11 9 7 5 6 4 8 12 10 2 3
> > [12,] 1 8 3 4 2 12 10 5 9 7 11 6
> > [13,] 1 2 3 7 11 6 10 5 12 4 8 9
> > [14,] 4 8 3 10 5 12 7 2 9 1 11 6
> > [15,] 10 2 3 4 8 6 7 11 9 1 5 12
> > [16,] 4 8 9 10 2 12 7 5 6 1 11 3
> > [17,] 1 2 6 10 5 3 7 8 12 4 11 9
> > [18,] 10 2 9 4 11 12 1 5 6 7 8 3
> > [19,] 4 8 6 7 11 12 1 2 9 10 5 3
> > [20,] 1 8 12 7 2 3 10 11 6 4 5 9
> > [21,] 10 2 12 1 5 9 7 11 6 4 8 3
> > [22,] 4 11 12 1 2 3 10 8 6 7 5 9
> > [23,] 1 11 3 7 2 6 10 5 9 4 8 12
> > [24,] 7 2 9 10 5 12 1 11 3 4 8 6
> > [25,] 7 8 9 1 2 6 4 5 3 10 11 12
> > [26,] 4 5 12 10 2 3 7 11 6 1 8 9
> > [27,] 4 5 9 1 11 3 7 8 12 10 2 6
> > [28,] 1 5 6 4 11 3 7 8 9 10 2 12
> > [29,] 4 5 6 1 11 9 10 2 12 7 8 3
> > [30,] 4 11 3 7 8 12 10 5 6 1 2 9
> > [31,] 10 2 3 1 11 6 7 8 9 4 5 12
> > [32,] 10 2 3 7 8 9 1 11 6 4 5 12
> > [33,] 7 11 6 1 8 9 4 5 12 10 2 3
> > [34,] 7 5 12 1 8 6 4 11 3 10 2 9
> > [35,] 1 2 3 4 8 6 7 5 9 10 11 12
> > [36,] 7 8 3 1 11 9 10 2 12 4 5 6
> > [37,] 10 2 6 1 11 12 7 5 3 4 8 9
> > [38,] 1 5 9 4 11 12 7 8 3 10 2 6
> > [39,] 1 2 12 7 5 9 10 8 3 4 11 6
> > [40,] 1 8 3 10 2 12 7 11 6 4 5 9
> > [41,] 1 2 9 4 8 3 10 11 12 7 5 6
> > [42,] 4 5 6 1 2 9 10 8 3 7 11 12
> > [43,] 1 2 6 7 11 12 10 5 9 4 8 3
> > [44,] 1 2 9 10 11 12 4 8 6 7 5 3
> > [45,] 10 5 9 7 11 6 4 2 3 1 8 12
> > [46,] 1 2 3 4 11 6 7 5 9 10 8 12
> > [47,] 4 2 6 1 8 3 10 5 12 7 11 9
> > [48,] 4 8 9 7 2 3 1 5 12 10 11 6
> > [49,] 10 8 12 1 2 9 4 11 3 7 5 6
> > [50,] 10 8 6 1 2 3 7 5 12 4 11 9
> > [51,] 7 2 12 10 11 6 4 8 3 1 5 9
> > [52,] 4 5 6 1 2 12 10 11 9 7 8 3
> > [53,] 1 2 3 7 5 6 4 8 9 10 11 12
> > [54,] 10 5 3 7 11 9 1 8 6 4 2 12
> > [55,] 7 11 12 4 2 3 10 8 6 1 5 9
> > [56,] 1 5 9 4 11 12 10 8 3 7 2 6
> > [57,] 4 5 9 7 11 3 10 2 6 1 8 12
> > [58,] 10 11 3 4 5 6 1 8 12 7 2 9
> > [59,] 4 8 9 10 5 6 7 2 3 1 11 12
> > [60,] 4 2 12 1 8 6 10 5 9 7 11 3
> > [61,] 4 8 6 7 11 9 10 5 12 1 2 3
> > [62,] 7 8 3 10 5 6 1 11 12 4 2 9
> > [63,] 10 5 3 7 8 6 1 2 9 4 11 12
> > [64,] 10 2 9 4 11 12 1 5 3 7 8 6
> > [65,] 1 11 6 4 8 12 7 2 3 10 5 9
> > [66,] 1 5 3 7 11 9 4 2 12 10 8 6
> > [67,] 4 2 6 7 5 12 10 8 9 1 11 3
> > [68,] 4 11 12 10 2 3 7 8 6 1 5 9
> > [69,] 4 5 6 10 2 3 7 8 9 1 11 12
> > [70,] 1 11 12 10 2 6 4 5 3 7 8 9
> > [71,] 10 5 6 7 8 12 4 2 9 1 11 3
> > [72,] 10 8 12 1 11 9 7 5 3 4 2 6
> > [73,] 10 8 3 7 11 9 4 5 12 1 2 6
> > [74,] 7 2 12 1 5 6 4 8 9 10 11 3
> > [75,] 7 2 12 10 8 9 1 11 6 4 5 3
> > [76,] 7 2 3 1 5 9 4 8 12 10 11 6
> > [77,] 1 11 3 10 5 6 7 2 9 4 8 12
> > [78,] 7 2 6 10 11 12 4 8 9 1 5 3
> > [79,] 10 8 6 7 5 3 1 2 9 4 11 12
> > [80,] 10 11 3 7 2 12 4 8 6 1 5 9
> > [81,] 10 5 6 1 8 3 4 11 9 7 2 12
> > [82,] 1 11 3 7 5 12 10 2 6 4 8 9
> > [83,] 4 11 9 10 5 12 7 2 6 1 8 3
> > [84,] 1 11 12 7 8 3 4 2 6 10 5 9
> > [85,] 10 2 9 7 5 6 1 11 12 4 8 3
> > [86,] 7 11 9 4 5 6 10 2 12 1 8 3
> > [87,] 4 5 12 7 2 3 10 11 6 1 8 9
> > [88,] 1 2 12 7 5 3 10 8 6 4 11 9
> > [89,] 1 8 12 7 11 9 10 2 6 4 5 3
> > [90,] 4 5 3 10 11 9 7 2 6 1 8 12
> > [91,] 4 5 6 1 2 12 10 11 9 7 8 3
> > [92,] 10 11 9 7 5 12 1 2 6 4 8 3
> > [93,] 4 2 3 7 8 6 1 11 12 10 5 9
> > [94,] 4 5 3 10 2 12 7 8 9 1 11 6
> > [95,] 4 8 3 10 11 9 1 2 6 7 5 12
> > [96,] 7 5 12 10 11 3 1 8 9 4 2 6
> > [97,] 4 2 3 1 8 6 7 11 9 10 5 12
> > [98,] 4 11 9 7 5 12 10 8 6 1 2 3
> > [99,] 1 11 12 4 5 6 7 8 3 10 2 9
> > [100,] 1 8 3 7 5 6 10 2 12 4 11 9
> > [101,] 7 11 6 4 8 3 1 2 12 10 5 9
> > [102,] 7 11 12 1 2 3 10 8 6 4 5 9
> > [103,] 4 5 12 1 2 9 7 8 3 10 11 6
> > [104,] 10 11 12 4 8 3 7 5 9 1 2 6
> > [105,] 10 5 9 1 2 3 4 8 6 7 11 12
> > [106,] 10 11 9 1 2 12 7 8 3 4 5 6
> > [107,] 10 11 3 4 8 9 7 5 12 1 2 6
> > [108,] 7 2 6 1 11 9 4 5 12 10 8 3
> > [109,] 1 8 6 7 2 12 10 5 3 4 11 9
> > [110,] 1 11 12 4 5 6 7 8 3 10 2 9
> > [111,] 7 8 6 1 5 3 10 2 12 4 11 9
> > [112,] 4 8 3 7 5 6 1 2 9 10 11 12
> > [113,] 1 2 9 4 11 6 7 5 3 10 8 12
> > [114,] 4 11 9 1 8 6 7 2 3 10 5 12
> > [115,] 10 8 3 4 11 12 7 2 9 1 5 6
> > [116,] 7 11 12 1 2 3 4 8 9 10 5 6
> > [117,] 1 5 3 10 11 12 7 8 9 4 2 6
> > [118,] 1 11 6 4 2 9 10 5 12 7 8 3
> > [119,] 10 2 3 1 5 9 4 8 12 7 11 6
> > [120,] 1 2 3 4 11 12 7 8 9 10 5 6
> > [121,] 7 8 3 4 5 12 10 2 6 1 11 9
> > [122,] 7 8 3 4 5 12 10 2 6 1 11 9
> > [123,] 4 5 3 10 11 9 7 8 6 1 2 12
> > [124,] 4 5 6 7 11 9 1 8 12 10 2 3
> > [125,] 10 8 6 1 11 9 4 2 12 7 5 3
> > [126,] 10 8 12 4 11 9 7 2 6 1 5 3
> > [127,] 7 8 12 1 11 6 10 5 9 4 2 3
> > [128,] 1 8 12 10 11 3 7 5 9 4 2 6
> > [129,] 7 8 3 10 2 6 1 11 9 4 5 12
> > [130,] 7 11 9 1 2 6 10 8 3 4 5 12
> > [131,] 10 2 3 4 11 9 1 5 6 7 8 12
> > [132,] 4 11 3 1 5 9 10 2 6 7 8 12
> > [133,] 10 2 12 7 8 3 4 5 6 1 11 9
> > [134,] 7 11 9 1 2 6 10 8 3 4 5 12
> > [135,] 7 8 3 4 11 6 10 2 9 1 5 12
> > [136,] 10 8 9 7 11 12 1 2 6 4 5 3
> > [137,] 10 8 12 4 5 3 1 2 9 7 11 6
> > [138,] 1 2 6 10 8 12 7 11 9 4 5 3
> > [139,] 4 5 3 7 11 9 1 2 12 10 8 6
> > [140,] 4 5 12 7 8 6 10 11 3 1 2 9
> > [141,] 7 2 12 10 11 6 4 8 3 1 5 9
> > [142,] 10 11 12 7 2 6 1 5 3 4 8 9
> > [143,] 7 2 3 10 11 6 1 8 9 4 5 12
> > [144,] 1 2 9 10 5 12 4 8 3 7 11 6
> > [145,] 1 11 6 4 8 9 7 5 12 10 2 3
> > [146,] 4 5 3 10 2 6 1 11 9 7 8 12
> > [147,] 7 11 9 1 2 3 10 8 12 4 5 6
> > [148,] 4 2 3 1 5 12 7 8 6 10 11 9
> > [149,] 10 11 12 4 8 3 1 2 9 7 5 6
> > [150,] 4 8 3 10 5 6 1 11 9 7 2 12
> > [151,] 1 8 6 10 5 9 4 11 3 7 2 12
> > [152,] 4 8 6 7 11 12 10 5 3 1 2 9
> > [153,] 7 2 3 10 5 6 4 11 9 1 8 12
> > [154,] 10 5 12 1 8 9 7 2 3 4 11 6
> > [155,] 1 8 6 4 2 9 10 5 3 7 11 12
> > [156,] 10 2 3 7 5 9 4 11 12 1 8 6
> > [157,] 10 5 3 1 2 6 7 8 9 4 11 12
> > [158,] 7 11 12 4 5 9 10 8 3 1 2 6
> > [159,] 7 5 3 1 8 12 10 2 6 4 11 9
> > [160,] 7 2 6 4 11 3 1 5 12 10 8 9
> > [161,] 7 5 3 1 2 12 4 8 9 10 11 6
> > [162,] 7 8 12 1 5 6 10 11 9 4 2 3
> > [163,] 10 11 9 4 8 6 1 2 3 7 5 12
> > [164,] 7 11 6 1 5 9 4 2 12 10 8 3
> > [165,] 4 11 9 10 8 3 7 2 12 1 5 6
> > [166,] 4 2 6 10 8 9 7 11 12 1 5 3
> > [167,] 7 5 3 10 2 12 4 8 6 1 11 9
> > [168,] 1 8 12 7 2 3 4 5 9 10 11 6
> > [169,] 7 8 12 1 5 6 4 2 3 10 11 9
> > [170,] 4 5 3 7 8 9 1 2 12 10 11 6
> > [171,] 7 11 9 1 8 6 4 2 12 10 5 3
> > [172,] 10 8 3 1 2 9 4 11 12 7 5 6
> > [173,] 10 5 12 7 8 9 4 11 3 1 2 6
> > [174,] 10 11 6 7 5 3 4 8 12 1 2 9
> > [175,] 7 11 12 1 2 3 10 8 9 4 5 6
> > [176,] 1 11 12 7 2 3 4 8 9 10 5 6
> > [177,] 10 11 12 4 5 3 7 8 6 1 2 9
> > [178,] 10 5 3 7 2 6 4 8 12 1 11 9
> > [179,] 1 5 6 7 2 9 10 11 3 4 8 12
> > [180,] 1 11 12 10 5 6 4 2 3 7 8 9
> > [181,] 7 2 12 4 11 9 1 5 6 10 8 3
> > [182,] 10 11 12 1 5 3 7 8 9 4 2 6
> > [183,] 4 8 3 1 11 9 7 2 6 10 5 12
> > [184,] 4 8 9 7 2 3 10 5 6 1 11 12
> > [185,] 10 11 9 1 5 6 7 2 12 4 8 3
> > [186,] 10 5 12 4 8 9 7 2 6 1 11 3
> > [187,] 4 2 3 1 8 6 7 5 12 10 11 9
> > [188,] 10 2 9 4 11 12 1 8 3 7 5 6
> > [189,] 10 2 12 7 11 3 4 5 9 1 8 6
> > [190,] 4 5 6 7 8 3 10 11 9 1 2 12
> > [191,] 10 5 9 1 2 3 7 11 12 4 8 6
> > [192,] 4 11 9 7 2 6 10 5 3 1 8 12
> > [193,] 10 11 12 1 2 6 4 5 9 7 8 3
> > [194,] 10 2 3 4 11 12 7 5 6 1 8 9
> > [195,] 4 2 6 7 8 9 1 11 3 10 5 12
> > [196,] 10 2 12 4 8 6 7 5 3 1 11 9
> > [197,] 7 5 12 4 11 9 1 2 3 10 8 6
> > [198,] 10 5 6 1 11 3 7 2 9 4 8 12
> > [199,] 1 2 9 7 11 3 4 8 6 10 5 12
> > [200,] 4 8 3 7 11 12 1 2 6 10 5 9
> >
> >
> >
> > >From: Robin Hankin <rksh at soc.soton.ac.uk>
> > >To: Jordi Altirriba Guti????rrez <altirriba at
hotmail.com>
> > >CC: r-help at stat.math.ethz.ch
> > >Subject: Re: [R] (no subject) (was: Permutations)
> > >Date: Wed, 14 Jul 2004 09:11:48 +0100
> > >
> > >Jordi
> > >
> > >try this
> > >
> > >
> > >R> x <- c(1,2,3, 10,11,12, 41,42,43, 81,82,83)
> > >R> dim(x) <- c(3,4)
> > >R> x
> > > [,1] [,2] [,3] [,4]
> > >[1,] 1 10 41 81
> > >[2,] 2 11 42 82
> > >[3,] 3 12 43 83
> > >R> jj <- t(apply(x,1,sample))
> > >R> jj
> > > [,1] [,2] [,3] [,4]
> > >[1,] 1 41 10 81
> > >[2,] 2 11 82 42
> > >[3,] 12 3 43 83
> > >R> as.vector(jj)
> > >R>
> > > [1] 1 2 12 41 11 3 10 82 43 81 42 83
> > >
> > >
> > >
> > >
> > >and I think that does what you want...
> > >
> > >We take the vector, rearrange it into a matrix with three rows,
then
>sample
> > >*within* the rows,
> > >then rearrange into a vector again.
> > >
> > >There will be one forbidden permutation, namely the identity
(which may
>or
> > >may not be
> > >desirable).
> > >
> > >This method doesn't allow "intra block"
permutations.
> > >
> > >best
> > >
> > >rksh
> > >
> > >
> > >
> > >> Dear R users,
> > >> First of all, thanks for the incredibly fast answers and
help of
>Rolf,
> > >>Marc and Robert.
> > >> Yes, I noticed that it was a lot of permutacions, but my
intention
>was
> > >>to make this process automatic and take only 5.000 - 10.000
>permutations.
> > >>Therefore, I wanted only to take that "interesting
permutations" with
> > >>"some information" [inter-block permutations].
> > >> The reason why I'm interested in these permutations is
because I'm
>using
> > >>some packages of Bioconductor to analyse my data from some
microarrays
>and
> > >>I thought that perhaps could be interesting to see what
happens when I
> > >>permute my data and I compare it against the not permuted
data.
> > >> Thanks again for your time and suggestions.
> > >>
> > >>Jordi Altirriba
> > >>Ph. D. Student
> > >>
> > >>Hospital Clinic-Barcelona-Spain
> > >>
> > >>______________________________________________
> > >>R-help at 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
> > >
> > >
> > >--
> > >Robin Hankin
> > >Uncertainty Analyst
> > >Southampton Oceanography Centre
> > >SO14 3ZH
> > >tel +44(0)23-8059-7743
> > >initialDOTsurname at soc.soton.ac.uk (edit in obvious way; spam
>precaution)
> >
> > ______________________________________________
> > R-help at 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
> >
>
Dear R users,
First of all, I want to thank the algorithms , time and suggestions to
Rolf, Robert, Marc, Gabor, Adaikalavan, Cliff, Robin, Erich and Fernando.
I want to sum up a little bit all the e-mails, the algorithms and the
results of a test for 1000 permutations (in my last e-mail is explained (+
or -) what kind of permutations I wanted).
1.- Gabor Grothendieck
ordered.perm <- function(N) {
samp <- function() c(apply(matrix(sample(12,12),3),2,sort))
z <- vector(length=N, mode="character")
for(i in 1:N)
while( (z[i]<-paste(samp(),collapse=" ")) %in%
z[seq(len=i-1)] ) {}
matrix(as.numeric(unlist(strsplit(z, split = " "))), nc = 12, byrow
=
TRUE)
}
ordered.perm(1000)
##It's the correct algorithm, there isn't any repetition and there
aren't
"intra-block" permutations.
2.- Rolf Turner (1)
restr.perm <- function ()
{
S <- 4:12
G <- NULL
A <- list(1:3,4:6,7:9,10:12)
for(k in 1:4) {
for(i in A[[k]]) {
tmp <- union(i,S)
tmp <- setdiff(tmp,G)
if(length(tmp)==0) return(Recall())
x <- if(length(tmp)==1) tmp else sample(tmp,1)
G <- c(G,x)
S <- setdiff(S,G)
}
S <- union(S,A[[k]])
R <- if(k < 4) A[[k+1]] else NULL
R <- union(R,G)
S <- setdiff(S,R)
}
G
}
a<-matrix(1,1000,12)
for (i in 1:1000)
{
a[i,]<-restr.perm()
}
##With 1000 permutations I have found 3 "intra-block" permutations.
3.- Rolf Turner (2)
restr.perm2 <- function () {
#
okay <- function (x) {
m1 <- cbind(1:12,rep(1:4,rep(3,4)))
m2 <- m1[x,]
all((m2[,1] == m1[,1]) | (m2[,2] != m1[,2]))
}
#
repeat{
x <- sample(12,12)
if(okay(x)) return(x)
}
}
a<-matrix(1,1000,12)
for (i in 1:1000)
{
a[i,]<-restr.perm2()
}
##With 1000 permutations I have found 4 "intra-block" permutations.
4.- Marc Schwartz
library(gregmisc)
# Create non-allowable 'intra-block' permutations
# Need a generalizable way to do this, but
# good enough for now
a <- permutations(3, 3, 1:3)
b <- permutations(3, 3, 4:6)
c <- permutations(3, 3, 7:9)
d <- permutations(3, 3, 10:12)
intra <- rbind(a[-1, ], b[-1, ], c[-1, ], d[-1, ])
restr.perm3 <- function(runs)
{
results <- matrix(numeric(runs * 12), ncol = 12)
# use Gabor's function to check for row matches
# between 'x' and 'intra' to filter out in okay()
f1a <- function(a,b,sep=":")
{
f <- function(...) paste(..., sep=sep)
a2 <- do.call("f", as.data.frame(a))
b2 <- do.call("f", as.data.frame(b))
c(table(c(b2,unique(a2)))[a2] - 1)
}
okay <- function (x)
{
x.match <- matrix(x, ncol = 3, byrow = TRUE)
all(f1a(x.match, intra) == 0)
}
for (i in 1:runs)
{
x <- sample(12,12)
if (okay(x))
results[i, ] <- x
else
results[i, ] <- rep(NA, 12)
}
unique(results[complete.cases(results), ])
}
a<-matrix(1,1000,12)
for (i in 1:1000)
{
a[i,]<-restr.perm3()
}
restr.perm3(1000)
##With 1000 permutations, the function has taken 960 and I have found 4
"intra-block" permutations there.
5.- Fernando Tusell
permutations<-function(elements,blocks) {
n <- length(elements)
el.per.block <- n / blocks
for (i in 1:n) { # For each element in turn,
b <- floor(i/(el.per.block+.1))+1 # find which block it belongs to.
if (b==blocks) # If in the last block, we are done.
break
allow.pos <- b*el.per.block + 1 # Find first position it could
migrate to...
for (j in (allow.pos:n)) { # and create permutations with all
allowable
perm <- elements # interchanges.
perm[i] <- elements[j]
perm[j] <- elements[i]
print(perm)
}
} }
permutations(1:12,3)
##There are only 48 permutations
6.- Cliff Lunneborg
swap<-function(data,blocks)
{
dd<- data
cc<- 1:length(data)
bb<- unique(blocks)
aa<- sample(bb,2,replace=FALSE)
a1<- sample(cc[blocks==aa[1]],1)
a2<- sample(cc[blocks==aa[2]],1)
dd[a1]<- data[a2]
dd[a2]<- data[a1]
dd
}
x.d<- c(1,2,3,4,5,6,7,8,9,10,11,12)
x.b<- c(1,1,1,2,2,2,3,3,3,4,4,4)
a<-matrix(1,1000,12)
for (i in 1:1000)
{
if (i==1)
{a[i,]<-swap(x.d,x.b)
f<-swap(x.d,x.b)}
else
{a[i,]<-swap(f,x.b)
f<-swap(f,x.b)}
}
##There are 2 repetitions a 2 "intra-block" permutations
7.- Robin Hankin
a<-matrix(1,200,12)
for (i in 1:200)
{
x <- c(1,2,3,4,5,6,7,8,9,10,11,12)
dim(x) <- c(3,4)
jj <- t(apply(x,1,sample))
a[i,]<-as.vector(jj)
}
##In 200 permutations, there are 5 repetitions.
Thanks to all and sorryfor the confusion that have generated the
"intra-block" permutation.
Jordi Altirriba
PhD student
Hospital Clinic - Barcelona - Spain
P.S. I think that I don't have forgot to anybody...(sorry if I have done it)
hi again what a stimulating R discussion! This is R-help at its very best! I think I understand why you don't want pure inter-block permutations. My solution would be to realize that weeding out "forbidden" permutations is quite difficult and time-consuming (also as several people have pointed out forbidden permutations are very rare, accounting for only a proportion of (3!)^4/12! ...about one in 400000). The extra expense of this weeding process is likely to outweigh the slight loss of efficiency caused by generating a forbidden permutation. My solution would therefore be: x <- c(1,2,3,4,5,6,7,8,9,10,11,12) x.new <- sample(x) (note the not-inconsiderable advantage of code simplicity!) I think my algorithm generated repeats because in it there are only (4!)^3=13284 distinct permutations; see help(birthday). The system above has 12! ~= 4x10^8, much higher. Hope this helps Robin> >} >7.- Robin Hankin >a<-matrix(1,200,12) >for (i in 1:200) >{ >x <- c(1,2,3,4,5,6,7,8,9,10,11,12) >dim(x) <- c(3,4) > jj <- t(apply(x,1,sample)) >a[i,]<-as.vector(jj) >} >##In 200 permutations, there are 5 repetitions. > >Thanks to all and sorryfor the confusion that >have generated the "intra-block" permutation. > >Jordi Altirriba >PhD student >Hospital Clinic - Barcelona - Spain > >P.S. I think that I don't have forgot to anybody...(sorry if I have done it) > >_________________________________________________________________ >??Cu??nto vale tu auto? Tips para mantener tu >carro. ??De todo en MSN Latino Autos! >http://latino.msn.com/autos/-- Robin Hankin Uncertainty Analyst Southampton Oceanography Centre SO14 3ZH tel +44(0)23-8059-7743 initialDOTsurname at soc.soton.ac.uk (edit in obvious way; spam precaution)