Re: [R] Permutations with replacement (final final final)
Hi Daniel, Turns out, your code, however simple, is quite elegant for my needs (sometimes I overanalyze :O). Here is my last code to do what I need to do: ### begin R code # generate a matrix of ten thousand rows of 1-8 z <- t(matrix(rep(1:8,1),8,1)) library(Matrix) # use the R sample function in a loop to sample each line with replacement zcomb=Matrix() for (i in 1:dim(z)[1]) { z1 <- t(matrix(sample(z,8,replace=TRUE))) zcomb = rbind(zcomb,z1) } zcomb ### end R code # Regards, Jesse A. Canchola "Daniel Nordlund" <[EMAIL PROTECTED]> Sent by: [EMAIL PROTECTED] 08/18/2006 05:16 PM To "'Jesse Albert Canchola'" <[EMAIL PROTECTED]>, "'r-help'" cc Subject Re: [R] Permutations with replacement > -Original Message- > From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] > On Behalf Of Jesse Albert Canchola > Sent: Friday, August 18, 2006 1:02 PM > To: r-help > Subject: [R] Permutations with replacement > > Is there a simple function or process that will create permutations with > replacement? > > I know that using the combinat package > > ## begin R code ## > > library(combinat) > > m <- t(array(unlist(permn(3)), dim = c(3, 6))) > > # we can get the permutations, for example 3!=6 > # gives us > > > m > [,1] [,2] [,3] > [1,]123 > [2,]132 > [3,]312 > [4,]321 > [5,]231 > [6,]213 > ## end R code ## > > I'd like to include the "with replacement possibilities" such as > > 1,1,3 > 1,1,2 > 2,3,3 > Isn't what you want just sampling with replacement? x <- c(1,2,3) sample(x,3,replace=TRUE) Hope this is helpful, Dan Dan Nordlund Bothell, WA USA __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. ___ The information contained in this e-mail is for the exclusive use of the intended recipient(s) and may be confidential, proprietary, and/or legally privileged. Inadvertent disclosure of this message does not constitute a waiver of any privilege. If you receive this message in error, please do not directly or indirectly use, print, copy, forward, or disclose any part of this message. Please also delete this e-mail and all copies and notify the sender. Thank you. For alternate languages please go to http://bayerdisclaimer.bayerweb.com __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] Permutations with replacement
Thanks, David. That worked fabulously! Here is the R code for the hypercube test example: ## begin R code library(combinat) x <- rep(3,3) # for partitions of 3 units into the three classes {1,2,3} hcube(x, scale=1, transl=0) ### end R code For the larger one I want (i.e., 8^8), I will take a random sample of 10,000 from the 16,777,216 possibilities. Regards, Jesse Canchola <[EMAIL PROTECTED]> Sent by: [EMAIL PROTECTED] 08/18/2006 01:33 PM To "Jesse Albert Canchola" <[EMAIL PROTECTED]>, "r-help" cc Subject Re: [R] Permutations with replacement If you also want 1,1,1 and so on, the number of these is n^n, (n choices for each of n slots.) In that case, you could use hcube from combinat. David L. Reiner Rho Trading Securities, LLC Chicago IL 60605 -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Jesse Albert Canchola Sent: Friday, August 18, 2006 3:26 PM To: r-help Subject: [R] Permutations with replacement Is there a simple function or process that will create a matrix of permutations with replacement? I know that using the combinat package ## begin R code ## > library(combinat) > m <- t(array(unlist(permn(3)), dim = c(3, 6))) # we can get the permutations, for example 3!=6 # gives us > m [,1] [,2] [,3] [1,]123 [2,]132 [3,]312 [4,]321 [5,]231 [6,]213 ## end R code ## I'd like to include the "with replacement possibilities" such as 1,1,3 1,1,2 2,3,3 and so on. This will eventually be done on 8!=40,320 rather than the development version using 3! as above. If no function exists (I've Googled on CRAN with no palpable luck), then perhaps this is more of a bootstrap type problem. Thanks for your help in advance, Jesse Canchola ___ The information contained in this e-mail is for the exclusive use of the intended recipient(s) and may be confidential, proprietary, and/or legally privileged. Inadvertent disclosure of this message does not constitute a waiver of any privilege. If you receive this message in error, please do not directly or indirectly use, print, copy, forward, or disclose any part of this message. Please also delete this e-mail and all copies and notify the sender. Thank you. For alternate languages please go to http://bayerdisclaimer.bayerweb.com __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] Permutations with replacement
> -Original Message- > From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] > On Behalf Of Jesse Albert Canchola > Sent: Friday, August 18, 2006 1:02 PM > To: r-help > Subject: [R] Permutations with replacement > > Is there a simple function or process that will create permutations with > replacement? > > I know that using the combinat package > > ## begin R code ## > > library(combinat) > > m <- t(array(unlist(permn(3)), dim = c(3, 6))) > > # we can get the permutations, for example 3!=6 > # gives us > > > m > [,1] [,2] [,3] > [1,]123 > [2,]132 > [3,]312 > [4,]321 > [5,]231 > [6,]213 > ## end R code ## > > I'd like to include the "with replacement possibilities" such as > > 1,1,3 > 1,1,2 > 2,3,3 > Isn't what you want just sampling with replacement? x <- c(1,2,3) sample(x,3,replace=TRUE) Hope this is helpful, Dan Dan Nordlund Bothell, WA USA __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] Permutations with replacement
If you also want 1,1,1 and so on, the number of these is n^n, (n choices for each of n slots.) In that case, you could use hcube from combinat. David L. Reiner Rho Trading Securities, LLC Chicago IL 60605 -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Jesse Albert Canchola Sent: Friday, August 18, 2006 3:26 PM To: r-help Subject: [R] Permutations with replacement Is there a simple function or process that will create a matrix of permutations with replacement? I know that using the combinat package ## begin R code ## > library(combinat) > m <- t(array(unlist(permn(3)), dim = c(3, 6))) # we can get the permutations, for example 3!=6 # gives us > m [,1] [,2] [,3] [1,]123 [2,]132 [3,]312 [4,]321 [5,]231 [6,]213 ## end R code ## I'd like to include the "with replacement possibilities" such as 1,1,3 1,1,2 2,3,3 and so on. This will eventually be done on 8!=40,320 rather than the development version using 3! as above. If no function exists (I've Googled on CRAN with no palpable luck), then perhaps this is more of a bootstrap type problem. Thanks for your help in advance, Jesse Canchola ___ The information contained in this e-mail is for the exclusive use of the intended recipient(s) and may be confidential, proprietary, and/or legally privileged. Inadvertent disclosure of this message does not constitute a waiver of any privilege. If you receive this message in error, please do not directly or indirectly use, print, copy, forward, or disclose any part of this message. Please also delete this e-mail and all copies and notify the sender. Thank you. For alternate languages please go to http://bayerdisclaimer.bayerweb.com __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
RE: [R] Permutations (summary)
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 Im 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(1) 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 Kirkmans 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 __ [EMAIL PROTECTED] 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
Re: [R] Permutations
On 7/14/04 7:42 PM, "Jordi Altirriba Gutiérrez" <[EMAIL PROTECTED]> wrote: > 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 9YES---Xth permutation > > 1 10 7 | 4 8 7 | 5 6 12 | 3 2 9NO 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, Hi Jordi, If it is allowed to combine permutations then allowing inter block permutations will generate all possible permutations: eg 1 2 3 | 4 5 6 1 4 3 | 2 5 6 2 4 3 | 1 5 6 2 1 3 | 4 5 6 According to your inter- and intra-block permissions, this sequence is allowed but the result is not ... best, ingmar __ [EMAIL PROTECTED] 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
RE: [R] Permutations
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) __ [EMAIL PROTECTED] 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
RE: [R] Permutations
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 40). 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 [EMAIL PROTECTED] (edit in obvious way; spam precaution) __ [EMAIL PROTECTED] 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
Re: [R] Permutations
On Wed, Jul 14, 2004 at 07:42:49PM +0200, Jordi Altirriba Gutiérrez wrote: > > 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) I am not a mathematician, but this sounds to me a little bit like Kirkman's Schoolgirl Problem: In a boarding school there are fifteen schoolgirls who always take their daily walks in rows of threes. How can it be arranged so that each schoolgirl walks in the same row with every other schoolgirl exactly once a week? http://mathworld.wolfram.com/KirkmansSchoolgirlProblem.html Christian __ [EMAIL PROTECTED] 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
Re: [R] Permutations
, 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 cancer.org.uk> : : >To: Jordi Altirriba GutiÃrrez hotmail.com> : : >CC: rksh soc.soton.ac.uk, R-help 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,]7231 11648910 512 : : > > [2,]1297 11648 1210 5 3 : : > > [3,]7291 11345610 812 : : > > [4,] 108645 12729 111 3 : : > > [5,] 102 121 119786 4 5 3 : : > > [6,]7861594 11 1210 2 3 : : > > [7,]15 127264891011 3 : : > > [8,]159 1086423 71112 : : > > [9,]1 11672 1245910 8 3 : : > > [10,]45 12 10 119186 7 2 3 : : > > [11,]1 11975648 1210 2 3 : : > > [12,]18342 12 1059 711 6 : : > > [13,]1237 116 105 12 4 8 9 : : > > [14,]483 105 12729 111 6 : : > > [15,] 10234867 119 1 512 : : > > [16,]489 102 12756 111 3 : : > > [17,]126 105378 12 411 9 : : > > [18,] 10294 11 12156 7 8 3 : : > > [19,]4867 11 1212910 5 3 : : > > [20,]18 12723 10 116 4 5 9 : : > > [21,] 102 121597 116 4 8 3 : : > > [22,]4 11 12123 1086 7 5 9 : : > > [23,]1 113726 1059 4 812 : : > > [24,]729 105 121 113 4 8 6 : : > > [25,]789126453101112 : : > > [26,]45 12 10237 116 1 8 9 : : > > [27
Re: [R] Permutations
Based on your description below and our off-list discussion I gather than the problem is equivalent to sampling ordered permutations in the sense defined by Erich (i.e. permutations which are increasing within blocks) WITHOUT replacement. Actually one of your valid permutations in your example is not ordered but it seems arbitrary which representative of the 3!^4 intrablock permutations is used which is why I believe this solves your problem. The following code (not extensively tested) does this: 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(3) # test run In the above, samp(), which is from my previous response, gets one sample WITH replacement. It generates an unrestricted permutation of 12 and then projects that onto its associated ordered permutation of 12. Note that samp does not use rejection. That comes later which is why there are relatively few rejections. Each iteration of the for loop gets one sample without replacement storing the unrejected sammples as character strings in vector z. Each iteration of this for loop uses a while to call samp() repeatedly until it finds a sample that has not previously been generated (i.e. rejecting the others). The line beginning with matrix converts the strings to numbers. Jordi Altirriba GutiÃrrez hotmail.com> writes: : : 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 9YES---Xth permutation : : 1 10 7 | 4 8 7 | 5 6 12 | 3 2 9NO 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 cancer.org.uk> : >To: Jordi Altirriba GutiÃrrez hotmail.com> : >CC: rksh soc.soton.ac.uk, R-help 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 samplin
Re: [R] Permutations
On Wed, 2004-07-14 at 08:06, Rolf Turner wrote: > 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? Rolf, I have not quite figured out what the issues are, but I took your approach above and combined it with Gabor's f1a() function that was the result of the recent thread on matching/counting rows between matrices and came up with the following. The basic concept is that we know (or think that we know) what the non-allowable set of intra-block permutations are: # 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, ]) 'intra' looks like: > intra [,1] [,2] [,3] [1,]132 [2,]213 [3,]231 [4,]312 [5,]321 [6,]465 [7,]546 [8,]564 [9,]645 [10,]654 [11,]798 [12,]879 [13,]897 [14,]978 [15,]987 [16,] 10 12 11 [17,] 11 10 12 [18,] 11 12 10 [19,] 12 10 11 [20,] 12 11 10 With that in place, we can then take the randomly generated 'x', coerce it into a 3 column matrix by row and use Gabor's function to check for any matches of the rows of 3 in 'x' with the non-allowable permutations in 'intra'. Thus, the function will assign 'x' to the appropriate row in 'results' (which is pre-allocated based upon the number of runs) if 'x' passes or sets the row to NA's if it does not. I then use complete.cases() to return only the valid rows. Presumably, some of the randomly generated 'x' vectors could be duplicates, so I also use unique(): 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), ]) } So, with all that in place, we can then do something like the following: r <- replicate(10, restr.perm3(1000)) > str(r) List of 10 $ : num [1:934, 1:12] 10 6 8 7 7 11 1 1 8 4 ... $ : num [1:944, 1:12] 7 4 4 11 1 11 8 3 3 9 ... $ : num [1:953, 1:12] 8 4 11 1 11 6 7 11 9 10 ... $ : num [1:951, 1:12] 1 2 1 4 4 10 8 10 3 12 ... $ : num [1:949, 1:12] 1 7 11 9 2 2 11 7 11 4 ... $ : num [1:937, 1:12] 3 3 11 10 4 8 12 10 3 2 ... $ : num [1:952, 1:12] 7 3 1 6 4 4 4 11 2 8 ... $ : num [1:946, 1:12] 1 9 3 10 11 6 1 7 8 11 ... $ : num [1:945, 1:12] 8 9 1 2 8 3 4 1 7 11 ... $ : num [1:933, 1:12] 9 1 12 3 4 1 10 1 1 8 ... So the above would suggest that indeed, the restricted permutations are a fairly high proportion of the total. I went ahead and did the following 50 replicates of 1000 each: > system.time(r <- replicate(50, restr.perm3(100
Re: [R] Permutations
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: 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 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 9YES---Xth permutation 1 10 7 | 4 8 7 | 5 6 12 | 3 2 9NO 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 <[EMAIL PROTECTED]> To: Jordi Altirriba Gutiérrez <[EMAIL PROTECTED]> CC: [EMAIL PROTECTED], R-help <[EMAIL PROTECTED]> 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,]7231 11648910 512 > [2,]1297 11648 1210 5 3 > [3,]7291 11345610 812 > [4,] 108645 12729 111 3 > [5,] 102 121 119786 4 5 3 > [6,
Re: [R] Permutations
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,]7231 11648910 512 > [2,]1297 11648 1210 5 3 > [3,]7291 11345610 812 > [4,] 108645 12729 111 3 > [5,] 102 121 119786 4 5 3 > [6,]7861594 11 1210 2 3 > [7,]15 127264891011 3 > [8,]159 1086423 71112 > [9,]1 11672 1245910 8 3 > [10,]45 12 10 119186 7 2 3 > [11,]1 11975648 1210 2 3 > [12,]18342 12 1059 711 6 > [13,]1237 116 105 12 4 8 9 > [14,]483 105 12729 111 6 > [15,] 10234867 119 1 512 > [16,]489 102 12756 111 3 > [17,]126 105378 12 411 9 > [18,] 10294 11 12156 7 8 3 > [19,]4867 11 1212910 5 3 > [20,]18 12723 10 116 4 5 9 > [21,] 102 121597 116 4 8 3 > [22,]4 11 12123 1086 7 5 9 > [23,]1 113726 1059 4 812 > [24,]729 105 121 113 4 8 6 > [25,]789126453101112 > [26,]45 12 10237 116 1 8 9 > [27,]4591 11378 1210 2 6 > [28,]1564 11378910 212 > [29,]4561 119 102 12 7 8 3 > [30,]4 11378 12 1056 1 2 9 > [31,] 10231 116789 4 512 > [32,] 10237891 116 4 512 > [33,]7 11618945 1210 2 3 > [34,]75 121864 11310 2 9 > [35,]123486759101112 > [36,]7831 119 102 12 4 5 6 > [37,] 10261 11 12753 4 8 9 > [38,]1594 11 1278310 2 6 > [39,]12 12759 1083 411 6 > [40,]183 102 127 116 4 5 9 > [41,]129483 10 11 12 7 5 6 > [42,]456129 1083 71112 > [43,]1267 11 12 1059 4 8 3 > [44,]129 10 11 12486 7 5 3 > [45,] 10597 116423 1 812 > [46,]1234 1167591
Re: [R] Permutations
As Erich points out, there is some question as to what the original problem really is but lets assume its as Erich describes. Then, to get a random ordered permutation we just get a random permutation of 12 elements and sort the intra-block elements like this: c(apply(matrix(sample(12,12),3),2,sort)) Note that there are 12! = 479,001,600 permutations of 12 elements and 3!^4 = 1,296 of those permutations correspond to each ordered permutation so there are 479,001,600 / 1,296 = 369,600 ordered permutations in all. Erich Neuwirth univie.ac.at> writes: : : 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â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 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 : > : __ [EMAIL PROTECTED] 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
Re: [R] Permutations
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,]7231 11648910 512 [2,]1297 11648 1210 5 3 [3,]7291 11345610 812 [4,] 108645 12729 111 3 [5,] 102 121 119786 4 5 3 [6,]7861594 11 1210 2 3 [7,]15 127264891011 3 [8,]159 1086423 71112 [9,]1 11672 1245910 8 3 [10,]45 12 10 119186 7 2 3 [11,]1 11975648 1210 2 3 [12,]18342 12 1059 711 6 [13,]1237 116 105 12 4 8 9 [14,]483 105 12729 111 6 [15,] 10234867 119 1 512 [16,]489 102 12756 111 3 [17,]126 105378 12 411 9 [18,] 10294 11 12156 7 8 3 [19,]4867 11 1212910 5 3 [20,]18 12723 10 116 4 5 9 [21,] 102 121597 116 4 8 3 [22,]4 11 12123 1086 7 5 9 [23,]1 113726 1059 4 812 [24,]729 105 121 113 4 8 6 [25,]789126453101112 [26,]45 12 10237 116 1 8 9 [27,]4591 11378 1210 2 6 [28,]1564 11378910 212 [29,]4561 119 102 12 7 8 3 [30,]4 11378 12 1056 1 2 9 [31,] 10231 116789 4 512 [32,] 10237891 116 4 512 [33,]7 11618945 1210 2 3 [34,]75 121864 11310 2 9 [35,]123486759101112 [36,]7831 119 102 12 4 5 6 [37,] 10261 11 12753 4 8 9 [38,]1594 11 1278310 2 6 [39,]12 12759 1083 411 6 [40,]183 102 127 116 4 5 9 [41,]129483 10 11 12 7 5 6 [42,]456129 1083 71112 [43,]1267 11 12 1059 4 8 3 [44,]129 10 11 12486 7 5 3 [45,] 10597 116423 1 812 [46,]1234 11675910 812 [47,]426183 105 12 711 9 [48,]48972315 121011 6 [49,] 108 121294 113 7 5 6 [50,] 108612375 12 411 9 [51,]72 12 10 116483 1 5 9 [52,]45612 12 10 119 7 8 3 [53,]123756489101112 [54,] 10537 119186 4 212 [55,]7 11 12423 1086 1 5 9 [56,]1594 11 12 1083 7 2 6 [57,]4597 113 1026 1 812 [58,] 10 11345618 12 7 2 9 [59,]489 1056723 11112 [60,]42 12186 1059 711 3 [61,]4867 119 105 12 1 2 3 [62,]783 10561 11
Re: [R] Permutations
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 [EMAIL PROTECTED] __ [EMAIL PROTECTED] 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
Re: [R] Permutations
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’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/ __ [EMAIL PROTECTED] 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 __ [EMAIL PROTECTED] 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
Re: [R] Permutations
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 910 11 12 and 1 4 2 3 5 6 7 8 910 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 TUSELLe-mail: Departamento de Econometría y Estadística [EMAIL PROTECTED] 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 __ [EMAIL PROTECTED] 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
For what it's worth (was Re: [R] Permutations).
For what it's worth, here is a mild revision of my restr.perm() function, which seems NOT to fall over. I.e. it appears to ``reliably'' generate restricted permutations. Whether these are genuinely ***random*** restricted permutations (i.e. does each restricted permutation of 1:12 have the same probability of being generated?) is not clear to me. So ***DON'T TRUST IT***!!! ===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+=== 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 } ===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+===+=== cheers, Rolf Turner [EMAIL PROTECTED] __ [EMAIL PROTECTED] 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
Re: [R] Permutations
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 [EMAIL PROTECTED] __ [EMAIL PROTECTED] 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
Re: [R] Permutations
On Tue, 2004-07-13 at 15:02, Rolf Turner wrote: > Marc Schwartz wrote (in response to a question from Jordi Altirriba): snip > 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. Rolf, You are correct. I missed that (not so subtle) change in the line above. I mis-read the "inter-blocks (no intra-blocks)" requirement as simply permuting the blocks, rather than allowing for the swapping of values between blocks. Time for new bi-focals... As Robert has also pointed out in his reply, this gets quite unwieldy. One of the follow up questions might be, is it only allowable that one value at a time can be swapped between blocks or can multiple values be swapped between blocks simultaneously? I am not sure that it makes a substantive impact on the problem or its solution, however. The question is what is to be done with the resultant set of permutations? FWIW, on a 3.2 Ghz P4 with 2Gb of RAM: > system.time(perms <- permutations(12, 12, 1:12)) Error: cannot allocate vector of size 1403325 Kb Timing stopped at: 2274.27 54.58 2787.76 0 0 Marc __ [EMAIL PROTECTED] 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
Re: [R] Permutations
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 [EMAIL PROTECTED] 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/ > > __ > [EMAIL PROTECTED] 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 [EMAIL PROTECTED] Tue Jul 13 17:19:55 2004 > From: "Baskin, Robert" <[EMAIL PROTECTED]> > To: =?iso-8859-1?Q?=27Jordi_Altirriba_Guti=E9rrez=27?= <[EMAIL PROTECTED]>, > [EMAIL PROTECTED] > 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 [EMAIL PROTECTED] does not designate > permitted sender hosts) > Received-SPF: none (hypatia: domain of [EMAIL PROTECTED] 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: [EMAIL PROTECTED] > X-Mailman-Version: 2.1.5 > List-Id: "Main R Mailing List: Primary help" > List-Unsubscribe: <https://www.stat.math.ethz.ch/mailman/listinfo/r-help>, > <mailto:[EMAIL PROTECTED]> > List-Archive: <https://www.stat.math.ethz.ch/pipermail/r-help> > List-Post: <mailto:[EMAIL PROTECTED]> > List-Help: <mailto:[EMAIL PROTECTED]> > List-Subscribe: <https://www.stat.math.ethz.ch/mailman/listinfo/r-help>, > <mailto:[EMAIL PROTECTED]> > 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-
RE: [R] Permutations
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:[EMAIL PROTECTED] Sent: Tuesday, July 13, 2004 3:07 PM To: [EMAIL PROTECTED] 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/ __ [EMAIL PROTECTED] 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 __ [EMAIL PROTECTED] 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
Re: [R] Permutations
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 [EMAIL PROTECTED] __ [EMAIL PROTECTED] 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
Re: [R] Permutations
On Tue, 2004-07-13 at 14:29, Marc Schwartz wrote: > 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) Ackone correction. The use of matrix() here was actually redundant. You can use: > permutations(4, 4, groups) [,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" Sorry about that. Marc __ [EMAIL PROTECTED] 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
Re: [R] Permutations
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 __ [EMAIL PROTECTED] 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
Re: [R] permutations function
lamack lamack wrote: > > Dear all > > If I consider > > d<- c(1,2,3,4) > N<- 4 > n<- 2 > out1<- matrix(0,N^n,n) > z<-1 > > for(i in 1:N) > { > for(j in 1:N) > { >out1[z,1] = d[i] >out1[z,2] = d[j] >z<- z+1 > } > } > > library(gregmisc) > out2<- permutations(N,n,d,T,T) > > I have that out1==out2. Ok > > Now, if I consider > > d<- c(1,2,3,4) > N<- 4 > n<- 3 > out1<- matrix(0,N^n,n) > z<-1 > > for(i in 1:N) > { > for(j in 1:N) > { > for(k in 1:N) > { > out1[z,1] = d[i] > out1[z,2] = d[j] > out1[z,3] = d[k] >z<- z+1 > } > } > } > > out2<- permutations(N,n,d,T,T) > > I have that out1 is not equal out1. > > My question is: Why out1 is not equal out2 ? Because the "gregmisc" implementation of permutations() seems to be buggy (CC'ing to Greg). Uwe Ligges > Best regards > > __ > [EMAIL PROTECTED] mailing list > https://www.stat.math.ethz.ch/mailman/listinfo/r-help __ [EMAIL PROTECTED] mailing list https://www.stat.math.ethz.ch/mailman/listinfo/r-help