Re: [R] generating unordered combinations
Thanks Bryan, sorry for the late reply - I only just noticed this
post. I'm not specifically interested in that sum, but something
related to the sum so this may also be very useful.
Dan
On 18 Sep, 18:24, Bryan Keller bskel...@wisc.edu wrote:
The combn solution offered by Bill is great. It struck me that what you are
doing, in fact, is generating the null distribution of the two-sample
Wilcoxon test where the first group has size m and the second group has size
n. In general, the length of the array has size choose(n+m-1,m) which gets
very big very fast. For example,
choose(20+20-1,20)
[1] 68923264410
If, on the off chance that you are interested in *summing* the unordered
combinations across columns, there is a very slick way to do this that takes
a tiny fraction of the time and memory that generating huge arrays entails.
If not, obviously, you already have your solution.
Just in case, here is the code to generate the distribution of sums. It is
based on an algorithm due to Harding (1984).
f - function(m,n) {
umax - (m*n+1)
ifelse (umax%%2==0, umaxp - (umax/2)-1, umaxp - (umax-1)/2)
#umaxp is analagous to “M” from Harding (1984)
p - min((m+n),umaxp)
q - min(m,umaxp)
dis - c(1,numeric(umaxp))
if ((n+1)umaxp) {
for (i in 1:q) { #steps for denominator of generating
function
for (j in i:umaxp) {
dis[j+1] - (dis[j+1] + dis[(j-i)+1])
}
}
} else {
for (i in (n+1):(p)) { #steps for numerator of generating function
for (j in (umaxp):i) {
dis[j+1] - (dis[j+1] - dis[(j-i)+1])
}
}
for (i in 1:q) { #steps for denominator of generating
function
for (j in i:umaxp) {
dis[j+1] - (dis[j+1] + dis[(j-i)+1])
}
}
}
ldis - length(dis)
ifelse(umax%%2==0,dis - c(dis,dis[ldis:1]),dis - c(dis,dis[(ldis-1):1]))
dispr - dis/choose((n+m),n)
ws - sum(1:m):sum((n+1):(n+m))
lws - length(ws)
mat3 - cbind(ws,dis,dispr,numeric(lws),numeric(lws))
mat3[,4] - cumsum(mat3[,3])
mat3[,5] - cumsum(mat3[,3][lws:1])[lws:1]
colnames(mat3) - c(W,Freq,Probability,Sum up,Sum down)
print(mat3)
}
system.time(f(20,20))
user system elapsed
0.11 0.00 0.11
Bryan
That's brilliant - thanks.
On 17 Sep 2009, at 23:36, William Dunlap wrote:
There is a 1-1 correspondance between your n-sets
consisting of m possible element types (0 through m-1
in your example) and the number of n-subsets of a (n+m-1)-set.
E.g., your example had m=3 and n=3 and subtracting
1:3 from each column of combn(3+3-1,3) gives your result:
t(combn(3+3-1, 3)-(1:3))
[,1] [,2] [,3]
[1,] 0 0 0
[2,] 0 0 1
[3,] 0 0 2
[4,] 0 1 1
[5,] 0 1 2
[6,] 0 2 2
[7,] 1 1 1
[8,] 1 1 2
[9,] 1 2 2
[10,] 2 2 2
Bill Dunlap
TIBCO Software Inc - Spotfire Division
wdunlap tibco.com
-Original Message-
From: r-help-boun...@r-project.org
[mailto:r-help-boun...@r-project.org] On Behalf Of DanHalligan
Sent: Thursday, September 17, 2009 1:31 PM
To: r-h...@r-project.org
Subject: [R] generating unordered combinations
Hi,
I am trying to generate all unordered combinations of a set of
numbers / characters, and I can only find a (very) clumsy way of
doing
this using expand.grid. For example, all unordered combinations of
the numbers 0, 1, 2 are:
0, 0, 0
0, 0, 1
0, 0, 2
0, 1, 1
0, 1, 2
0, 2, 2
1, 1, 1
1, 1, 2
1, 2, 2
2, 2, 2
(I have not included, for example, 1, 0, 0, since it is equivalent to
0, 0, 1).
I have found a way to generate this data.frame using expand.grid as
follows:
g - expand.grid(c(0,1,2), c(0,1,2), c(0,1,2))
for(i in 1:nrow(g)) {
g[i,] - sort(as.character(g[i,]))
}
o - order(g$Var1, g$Var2, g$Var3)
unique(g[o,]).
This is obviously quite clumsy and hard to generalise to a greater
number of characters, so I'm keen to find any other solutions. Can
anyone suggest a better (more general, quicker) method?
Cheers
__
r-h...@r-project.org 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.
-
Bryan Keller, Doctoral Student/Project Assistant
Educational Psychology - Quantitative Methods
The University of Wisconsin - Madison
__
r-h...@r-project.org mailing listhttps://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guidehttp://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
__
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read
Re: [R] generating unordered combinations
That's brilliant - thanks.
On 17 Sep 2009, at 23:36, William Dunlap wrote:
There is a 1-1 correspondance between your n-sets
consisting of m possible element types (0 through m-1
in your example) and the number of n-subsets of a (n+m-1)-set.
E.g., your example had m=3 and n=3 and subtracting
1:3 from each column of combn(3+3-1,3) gives your result:
t(combn(3+3-1, 3)-(1:3))
[,1] [,2] [,3]
[1,]000
[2,]001
[3,]002
[4,]011
[5,]012
[6,]022
[7,]111
[8,]112
[9,]122
[10,]222
Bill Dunlap
TIBCO Software Inc - Spotfire Division
wdunlap tibco.com
-Original Message-
From: r-help-boun...@r-project.org
[mailto:r-help-boun...@r-project.org] On Behalf Of Dan Halligan
Sent: Thursday, September 17, 2009 1:31 PM
To: r-help@r-project.org
Subject: [R] generating unordered combinations
Hi,
I am trying to generate all unordered combinations of a set of
numbers / characters, and I can only find a (very) clumsy way of
doing
this using expand.grid. For example, all unordered combinations of
the numbers 0, 1, 2 are:
0, 0, 0
0, 0, 1
0, 0, 2
0, 1, 1
0, 1, 2
0, 2, 2
1, 1, 1
1, 1, 2
1, 2, 2
2, 2, 2
(I have not included, for example, 1, 0, 0, since it is equivalent to
0, 0, 1).
I have found a way to generate this data.frame using expand.grid as
follows:
g - expand.grid(c(0,1,2), c(0,1,2), c(0,1,2))
for(i in 1:nrow(g)) {
g[i,] - sort(as.character(g[i,]))
}
o - order(g$Var1, g$Var2, g$Var3)
unique(g[o,]).
This is obviously quite clumsy and hard to generalise to a greater
number of characters, so I'm keen to find any other solutions. Can
anyone suggest a better (more general, quicker) method?
Cheers
__
R-help@r-project.org 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@r-project.org 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] generating unordered combinations
The combn solution offered by Bill is great. It struck me that what you are
doing, in fact, is generating the null distribution of the two-sample Wilcoxon
test where the first group has size m and the second group has size n. In
general, the length of the array has size choose(n+m-1,m) which gets very big
very fast. For example,
choose(20+20-1,20)
[1] 68923264410
If, on the off chance that you are interested in *summing* the unordered
combinations across columns, there is a very slick way to do this that takes a
tiny fraction of the time and memory that generating huge arrays entails. If
not, obviously, you already have your solution.
Just in case, here is the code to generate the distribution of sums. It is
based on an algorithm due to Harding (1984).
f - function(m,n) {
umax - (m*n+1)
ifelse (umax%%2==0, umaxp - (umax/2)-1, umaxp - (umax-1)/2)
#umaxp is analagous to “M” from Harding (1984)
p - min((m+n),umaxp)
q - min(m,umaxp)
dis - c(1,numeric(umaxp))
if ((n+1)umaxp) {
for (i in 1:q) {#steps for denominator of generating
function
for (j in i:umaxp) {
dis[j+1] - (dis[j+1] + dis[(j-i)+1])
}
}
} else {
for (i in (n+1):(p)) { #steps for numerator of generating function
for (j in (umaxp):i) {
dis[j+1] - (dis[j+1] - dis[(j-i)+1])
}
}
for (i in 1:q) {#steps for denominator of generating
function
for (j in i:umaxp) {
dis[j+1] - (dis[j+1] + dis[(j-i)+1])
}
}
}
ldis - length(dis)
ifelse(umax%%2==0,dis - c(dis,dis[ldis:1]),dis - c(dis,dis[(ldis-1):1]))
dispr - dis/choose((n+m),n)
ws - sum(1:m):sum((n+1):(n+m))
lws - length(ws)
mat3 - cbind(ws,dis,dispr,numeric(lws),numeric(lws))
mat3[,4] - cumsum(mat3[,3])
mat3[,5] - cumsum(mat3[,3][lws:1])[lws:1]
colnames(mat3) - c(W,Freq,Probability,Sum up,Sum down)
print(mat3)
}
system.time(f(20,20))
user system elapsed
0.110.000.11
Bryan
That's brilliant - thanks.
On 17 Sep 2009, at 23:36, William Dunlap wrote:
There is a 1-1 correspondance between your n-sets
consisting of m possible element types (0 through m-1
in your example) and the number of n-subsets of a (n+m-1)-set.
E.g., your example had m=3 and n=3 and subtracting
1:3 from each column of combn(3+3-1,3) gives your result:
t(combn(3+3-1, 3)-(1:3))
[,1] [,2] [,3]
[1,]000
[2,]001
[3,]002
[4,]011
[5,]012
[6,]022
[7,]111
[8,]112
[9,]122
[10,]222
Bill Dunlap
TIBCO Software Inc - Spotfire Division
wdunlap tibco.com
-Original Message-
From: r-help-boun...@r-project.org
[mailto:r-help-boun...@r-project.org] On Behalf Of Dan Halligan
Sent: Thursday, September 17, 2009 1:31 PM
To: r-help@r-project.org
Subject: [R] generating unordered combinations
Hi,
I am trying to generate all unordered combinations of a set of
numbers / characters, and I can only find a (very) clumsy way of
doing
this using expand.grid. For example, all unordered combinations of
the numbers 0, 1, 2 are:
0, 0, 0
0, 0, 1
0, 0, 2
0, 1, 1
0, 1, 2
0, 2, 2
1, 1, 1
1, 1, 2
1, 2, 2
2, 2, 2
(I have not included, for example, 1, 0, 0, since it is equivalent to
0, 0, 1).
I have found a way to generate this data.frame using expand.grid as
follows:
g - expand.grid(c(0,1,2), c(0,1,2), c(0,1,2))
for(i in 1:nrow(g)) {
g[i,] - sort(as.character(g[i,]))
}
o - order(g$Var1, g$Var2, g$Var3)
unique(g[o,]).
This is obviously quite clumsy and hard to generalise to a greater
number of characters, so I'm keen to find any other solutions. Can
anyone suggest a better (more general, quicker) method?
Cheers
__
R-help@r-project.org 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.
-
Bryan Keller, Doctoral Student/Project Assistant
Educational Psychology - Quantitative Methods
The University of Wisconsin - Madison
__
R-help@r-project.org 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] generating unordered combinations
Hi,
I am trying to generate all unordered combinations of a set of
numbers / characters, and I can only find a (very) clumsy way of doing
this using expand.grid. For example, all unordered combinations of
the numbers 0, 1, 2 are:
0, 0, 0
0, 0, 1
0, 0, 2
0, 1, 1
0, 1, 2
0, 2, 2
1, 1, 1
1, 1, 2
1, 2, 2
2, 2, 2
(I have not included, for example, 1, 0, 0, since it is equivalent to
0, 0, 1).
I have found a way to generate this data.frame using expand.grid as
follows:
g - expand.grid(c(0,1,2), c(0,1,2), c(0,1,2))
for(i in 1:nrow(g)) {
g[i,] - sort(as.character(g[i,]))
}
o - order(g$Var1, g$Var2, g$Var3)
unique(g[o,]).
This is obviously quite clumsy and hard to generalise to a greater
number of characters, so I'm keen to find any other solutions. Can
anyone suggest a better (more general, quicker) method?
Cheers
__
R-help@r-project.org 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] generating unordered combinations
Dan,
Still maybe a bit ugly, but no looping...
unique(as.data.frame(t(apply(expand.grid(0:2, 0:2, 0:2), 1, sort
V1 V2 V3
1 0 0 0
2 0 0 1
3 0 0 2
5 0 1 1
6 0 1 2
9 0 2 2
14 1 1 1
15 1 1 2
18 1 2 2
27 2 2 2
Best,
Erik
-Original Message-
From: r-help-boun...@r-project.org [mailto:r-help-boun...@r-project.org]
On Behalf Of Dan Halligan
Sent: Thursday, September 17, 2009 3:31 PM
To: r-help@r-project.org
Subject: [R] generating unordered combinations
Hi,
I am trying to generate all unordered combinations of a set of
numbers / characters, and I can only find a (very) clumsy way of doing
this using expand.grid. For example, all unordered combinations of
the numbers 0, 1, 2 are:
0, 0, 0
0, 0, 1
0, 0, 2
0, 1, 1
0, 1, 2
0, 2, 2
1, 1, 1
1, 1, 2
1, 2, 2
2, 2, 2
(I have not included, for example, 1, 0, 0, since it is equivalent to
0, 0, 1).
I have found a way to generate this data.frame using expand.grid as
follows:
g - expand.grid(c(0,1,2), c(0,1,2), c(0,1,2))
for(i in 1:nrow(g)) {
g[i,] - sort(as.character(g[i,]))
}
o - order(g$Var1, g$Var2, g$Var3)
unique(g[o,]).
This is obviously quite clumsy and hard to generalise to a greater
number of characters, so I'm keen to find any other solutions. Can
anyone suggest a better (more general, quicker) method?
Cheers
__
R-help@r-project.org 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@r-project.org 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] generating unordered combinations
Dear Dan, On Thu, Sep 17, 2009 at 5:31 PM, Erik Iverson eiver...@nmdp.org wrote: Dan, Still maybe a bit ugly, but no looping... unique(as.data.frame(t(apply(expand.grid(0:2, 0:2, 0:2), 1, sort The prob package provides a convenience wrapper for (essentially) Erik's solution: library(prob) urnsamples(0:2, size = 3, replace = TRUE, ordered = FALSE) Regards, Jay *** G. Jay Kerns, Ph.D. Associate Professor Department of Mathematics Statistics Youngstown State University Youngstown, OH 44555-0002 USA Office: 1035 Cushwa Hall Phone: (330) 941-3310 Office (voice mail) -3302 Department -3170 FAX VoIP: gjke...@ekiga.net E-mail: gke...@ysu.edu http://www.cc.ysu.edu/~gjkerns/ __ R-help@r-project.org 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] generating unordered combinations
There is a 1-1 correspondance between your n-sets
consisting of m possible element types (0 through m-1
in your example) and the number of n-subsets of a (n+m-1)-set.
E.g., your example had m=3 and n=3 and subtracting
1:3 from each column of combn(3+3-1,3) gives your result:
t(combn(3+3-1, 3)-(1:3))
[,1] [,2] [,3]
[1,]000
[2,]001
[3,]002
[4,]011
[5,]012
[6,]022
[7,]111
[8,]112
[9,]122
[10,]222
Bill Dunlap
TIBCO Software Inc - Spotfire Division
wdunlap tibco.com
-Original Message-
From: r-help-boun...@r-project.org
[mailto:r-help-boun...@r-project.org] On Behalf Of Dan Halligan
Sent: Thursday, September 17, 2009 1:31 PM
To: r-help@r-project.org
Subject: [R] generating unordered combinations
Hi,
I am trying to generate all unordered combinations of a set of
numbers / characters, and I can only find a (very) clumsy way of doing
this using expand.grid. For example, all unordered combinations of
the numbers 0, 1, 2 are:
0, 0, 0
0, 0, 1
0, 0, 2
0, 1, 1
0, 1, 2
0, 2, 2
1, 1, 1
1, 1, 2
1, 2, 2
2, 2, 2
(I have not included, for example, 1, 0, 0, since it is equivalent to
0, 0, 1).
I have found a way to generate this data.frame using expand.grid as
follows:
g - expand.grid(c(0,1,2), c(0,1,2), c(0,1,2))
for(i in 1:nrow(g)) {
g[i,] - sort(as.character(g[i,]))
}
o - order(g$Var1, g$Var2, g$Var3)
unique(g[o,]).
This is obviously quite clumsy and hard to generalise to a greater
number of characters, so I'm keen to find any other solutions. Can
anyone suggest a better (more general, quicker) method?
Cheers
__
R-help@r-project.org 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@r-project.org 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.
