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'
r-help@stat.math.ethz.ch
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
r-help@stat.math.ethz.ch
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
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 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 (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 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
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
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
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-blockpermutation 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
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
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 Gutirrez 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 - - 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
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 12
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 erich.neuwirth at 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 Gutirrez 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 :- - : : : 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 : : __ [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
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 Gutirrez 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 11675910 812
[47,]426183 105 12 711
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-blockpermutation 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,]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
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(1000)))
[1] 91.20 0.06 92.98 0.00 0.00
mean(unlist(lapply(r, nrow)))
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 Gutirrez altirriba at 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:
:
: 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-blockpermutation 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 Gutirrez 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
Re: [R] Permutations
.
: :
: : P.S. Sorry for having forgotten the title of the last e-mail
: :
: :
: : From: Adaikalavan Ramasamy ramasamy at cancer.org.uk
: : To: Jordi Altirriba Gutirrez 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 Gutirrez 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 127
Re: [R] Permutations
On Tue, 2004-07-13 at 14:07, Jordi Altirriba Gutirrez 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 310 11 12 4 5 67 8 9 [2,] 1 2 310 11 12 7 8 94 5 6 [3,] 1 2 34 5 610 11 12 7 8 9 [4,] 1 2 34 5 67 8 910 11 12 [5,] 1 2 37 8 910 11 12 4 5 6 [6,] 1 2 37 8 94 5 610 11 12 [7,] 10 11 12 1 2 34 5 67 8 9 [8,] 10 11 12 1 2 37 8 94 5 6 [9,] 10 11 12 4 5 61 2 37 8 9 [10,] 10 11 12 4 5 67 8 91 2 3 [11,] 10 11 12 7 8 91 2 34 5 6 [12,] 10 11 12 7 8 94 5 61 2 3 [13,] 4 5 61 2 310 11 12 7 8 9 [14,] 4 5 61 2 37 8 910 11 12 [15,] 4 5 610 11 12 1 2 37 8 9 [16,] 4 5 610 11 12 7 8 91 2 3 [17,] 4 5 67 8 91 2 310 11 12 [18,] 4 5 67 8 910 11 12 1 2 3 [19,] 7 8 91 2 310 11 12 4 5 6 [20,] 7 8 91 2 34 5 610 11 12 [21,] 7 8 910 11 12 1 2 34 5 6 [22,] 7 8 910 11 12 4 5 61 2 3 [23,] 7 8 94 5 61 2 310 11 12 [24,] 7 8 94 5 610 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
On Tue, 2004-07-13 at 14:29, Marc Schwartz wrote: On Tue, 2004-07-13 at 14:07, Jordi Altirriba Gutirrez 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 310 11 12 4 5 67 8 9 [2,] 1 2 310 11 12 7 8 94 5 6 [3,] 1 2 34 5 610 11 12 7 8 9 [4,] 1 2 34 5 67 8 910 11 12 [5,] 1 2 37 8 910 11 12 4 5 6 [6,] 1 2 37 8 94 5 610 11 12 [7,] 10 11 12 1 2 34 5 67 8 9 [8,] 10 11 12 1 2 37 8 94 5 6 [9,] 10 11 12 4 5 61 2 37 8 9 [10,] 10 11 12 4 5 67 8 91 2 3 [11,] 10 11 12 7 8 91 2 34 5 6 [12,] 10 11 12 7 8 94 5 61 2 3 [13,] 4 5 61 2 310 11 12 7 8 9 [14,] 4 5 61 2 37 8 910 11 12 [15,] 4 5 610 11 12 1 2 37 8 9 [16,] 4 5 610 11 12 7 8 91 2 3 [17,] 4 5 67 8 91 2 310 11 12 [18,] 4 5 67 8 910 11 12 1 2 3 [19,] 7 8 91 2 310 11 12 4 5 6 [20,] 7 8 91 2 34 5 610 11 12 [21,] 7 8 910 11 12 1 2 34 5 6 [22,] 7 8 910 11 12 4 5 61 2 3 [23,] 7 8 94 5 61 2 310 11 12 [24,] 7 8 94 5 610 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
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 310 11 12 4 5 67 8 9 [2,] 1 2 310 11 12 7 8 94 5 6 [3,] 1 2 34 5 610 11 12 7 8 9 [4,] 1 2 34 5 67 8 910 11 12 [5,] 1 2 37 8 910 11 12 4 5 6 [6,] 1 2 37 8 94 5 610 11 12 [7,] 10 11 12 1 2 34 5 67 8 9 [8,] 10 11 12 1 2 37 8 94 5 6 [9,] 10 11 12 4 5 61 2 37 8 9 [10,] 10 11 12 4 5 67 8 91 2 3 [11,] 10 11 12 7 8 91 2 34 5 6 [12,] 10 11 12 7 8 94 5 61 2 3 [13,] 4 5 61 2 310 11 12 7 8 9 [14,] 4 5 61 2 37 8 910 11 12 [15,] 4 5 610 11 12 1 2 37 8 9 [16,] 4 5 610 11 12 7 8 91 2 3 [17,] 4 5 67 8 91 2 310 11 12 [18,] 4 5 67 8 910 11 12 1 2 3 [19,] 7 8 91 2 310 11 12 4 5 6 [20,] 7 8 91 2 34 5 610 11 12 [21,] 7 8 910 11 12 1 2 34 5 6 [22,] 7 8 910 11 12 4 5 61 2 3 [23,] 7 8 94 5 61 2 310 11 12 [24,] 7 8 94 5 610 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
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
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 r-help.stat.math.ethz.ch
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-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
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
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
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 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
