Re: [R] expand.grid game
It did take me a good night's sleep to understand it. I was stuck with the exact same question but I see now how the remaining balls are shared among all 8 urns (therefore cases with 11, 12, 13, ... 17 balls are also dealt with). Thanks again, baptiste 2010/1/12 Rolf Turner r.tur...@auckland.ac.nz: On 13/01/2010, at 9:19 AM, Greg Snow wrote: How trivial is probably subjective, I don't think it is much above trivial. I would not have been surprised to see this question on an exam in my undergraduate (300 or junior level) probability course (the hard part was remembering the details from that class from over 20 years ago). My favorite test question of all time came from that course: You have a deck of poker cards with the 3's removed (and jokers), you deal yourself 5 cards at random, what is the probability of getting a straight (not including straight flushes)? This problem is simpler. Just think of the 8 places in the number as urns, and the 17 1's as balls to be put into the urns. One ball has to go in the first urn, so you have 16 left, there are choose(16+8-1,8-1) ways to distribute 16 undistinguishable balls among 8 distinguishable urns. But that includes some solutions with more than 9 balls in an urn which violates the digits restriction, so subtract off the illegal counts. If we place 10 balls in the first urn, then we have 7 remaining balls to distribute between the 8 urns or choose( 7+8-1, 7), If we place 1 ball in the first urn and 10 balls in one of the 7 other urns (7*), then there are choose( 6+8-1, 7 ) ways to distribute the remaining 6 balls in the 8 urns. Not too complicated once you remember (or look up) the formula for urns and balls. Sorry to be a thicko --- but doesn't the foregoing solution *leave in* the possibility of putting all 17 balls in the first urn? Or 3 balls in the first urn, 12 in the second, and the remaining 2 in any of the other six urns? Etc. I.e. don't more terms have to be subtracted? cheers, Rolf Turner ## Attention:This e-mail message is privileged and confidential. If you are not theintended recipient please delete the message and notify the sender.Any views or opinions presented are solely those of the author. This e-mail has been scanned and cleared by MailMarshalwww.marshalsoftware.com ## __ 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] expand.grid game
This also has a closed form solution:
choose(16+8-1,7) - choose(7+8-1, 7) - 7*choose(6+8-1,7)
[1] 229713
--
Gregory (Greg) L. Snow Ph.D.
Statistical Data Center
Intermountain Healthcare
greg.s...@imail.org
801.408.8111
-Original Message-
From: r-help-boun...@r-project.org [mailto:r-help-boun...@r-
project.org] On Behalf Of Brian Diggs
Sent: Thursday, December 31, 2009 3:08 PM
To: baptiste auguie; David Winsemius
Cc: r-help
Subject: Re: [R] expand.grid game
baptiste auguie wrote:
2009/12/19 David Winsemius dwinsem...@comcast.net:
On Dec 19, 2009, at 9:06 AM, baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm not
sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
And are you considering the number 0089 to be in the
acceptable set?
Or is the range of possible numbers in 1079:9800 ?
The latter, the first digit should not be 0. But if you have an
interesting solution for the other case, let me know anyway.
I should also stress that this is only for entertainment and
curiosity's sake.
baptiste
I realize I'm late coming to this, but I was reading it in my post-
vacation catch-up and it sounded interesting so I thought I'd give it a
shot.
After coding a couple of solutions that were exponential in time (for
the number of digits), I rearranged things and came up with something
that is linear in time (for the number of digits) and gives the count
of numbers for all sums at once:
library(plyr)
nsum3 - function(digits) {
digits - as.integer(digits)[[1L]]
if (digits==1) {
rep(1,9)
} else {
dm1 - nsum3(digits-1)
Reduce(+, llply(0:9, function(x) {c(rep(0,x),dm1,rep(0,9-x))}))
}
}
nsums - llply(1:8, nsum3)
nsums[[5]][17]
# [1] 3675
nsums[[8]][17]
# [1] 229713
The whole thing runs in well under a second on my machine (a several
years old dual core Windows machine). In the results of nsum3, the i-
th element is the number of numbers whose digits sum to i. The basic
idea is recursion on the number of digits; if n_{t,d} is the number of
d-digit numbers that sum to t, then n_{t,d} = \sum_{i\in(0,9)} n_{t-
i,d-1}. (Adding the digit i to each of those numbers makes their sum
t and increases the digits to d). When digits==1, then 0 isn't a valid
choice and that also implies the sum of digits can't be 0, which fits
well with the 1 indexing of arrays.
--
Brian Diggs, Ph.D.
Senior Research Associate, Department of Surgery, Oregon Health
Science University
__
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] expand.grid game
Nice --- am I missing something or was this closed form solution not
entirely trivial to find?
I ought to compile the various clever solutions given in this thread
someday, it's fascinating!
Thanks,
baptiste
2010/1/12 Greg Snow greg.s...@imail.org:
This also has a closed form solution:
choose(16+8-1,7) - choose(7+8-1, 7) - 7*choose(6+8-1,7)
[1] 229713
--
Gregory (Greg) L. Snow Ph.D.
Statistical Data Center
Intermountain Healthcare
greg.s...@imail.org
801.408.8111
-Original Message-
From: r-help-boun...@r-project.org [mailto:r-help-boun...@r-
project.org] On Behalf Of Brian Diggs
Sent: Thursday, December 31, 2009 3:08 PM
To: baptiste auguie; David Winsemius
Cc: r-help
Subject: Re: [R] expand.grid game
baptiste auguie wrote:
2009/12/19 David Winsemius dwinsem...@comcast.net:
On Dec 19, 2009, at 9:06 AM, baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm not
sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
And are you considering the number 0089 to be in the
acceptable set?
Or is the range of possible numbers in 1079:9800 ?
The latter, the first digit should not be 0. But if you have an
interesting solution for the other case, let me know anyway.
I should also stress that this is only for entertainment and
curiosity's sake.
baptiste
I realize I'm late coming to this, but I was reading it in my post-
vacation catch-up and it sounded interesting so I thought I'd give it a
shot.
After coding a couple of solutions that were exponential in time (for
the number of digits), I rearranged things and came up with something
that is linear in time (for the number of digits) and gives the count
of numbers for all sums at once:
library(plyr)
nsum3 - function(digits) {
digits - as.integer(digits)[[1L]]
if (digits==1) {
rep(1,9)
} else {
dm1 - nsum3(digits-1)
Reduce(+, llply(0:9, function(x) {c(rep(0,x),dm1,rep(0,9-x))}))
}
}
nsums - llply(1:8, nsum3)
nsums[[5]][17]
# [1] 3675
nsums[[8]][17]
# [1] 229713
The whole thing runs in well under a second on my machine (a several
years old dual core Windows machine). In the results of nsum3, the i-
th element is the number of numbers whose digits sum to i. The basic
idea is recursion on the number of digits; if n_{t,d} is the number of
d-digit numbers that sum to t, then n_{t,d} = \sum_{i\in(0,9)} n_{t-
i,d-1}. (Adding the digit i to each of those numbers makes their sum
t and increases the digits to d). When digits==1, then 0 isn't a valid
choice and that also implies the sum of digits can't be 0, which fits
well with the 1 indexing of arrays.
--
Brian Diggs, Ph.D.
Senior Research Associate, Department of Surgery, Oregon Health
Science University
__
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] expand.grid game
How trivial is probably subjective, I don't think it is much above trivial. I
would not have been surprised to see this question on an exam in my
undergraduate (300 or junior level) probability course (the hard part was
remembering the details from that class from over 20 years ago). My favorite
test question of all time came from that course: You have a deck of poker
cards with the 3's removed (and jokers), you deal yourself 5 cards at random,
what is the probability of getting a straight (not including straight flushes)?
This problem is simpler. Just think of the 8 places in the number as urns, and
the 17 1's as balls to be put into the urns. One ball has to go in the first
urn, so you have 16 left, there are choose(16+8-1,8-1) ways to distribute 16
undistinguishable balls among 8 distinguishable urns. But that includes some
solutions with more than 9 balls in an urn which violates the digits
restriction, so subtract off the illegal counts. If we place 10 balls in the
first urn, then we have 7 remaining balls to distribute between the 8 urns or
choose( 7+8-1, 7), If we place 1 ball in the first urn and 10 balls in one of
the 7 other urns (7*), then there are choose( 6+8-1, 7 ) ways to distribute the
remaining 6 balls in the 8 urns. Not too complicated once you remember (or
look up) the formula for urns and balls.
--
Gregory (Greg) L. Snow Ph.D.
Statistical Data Center
Intermountain Healthcare
greg.s...@imail.org
801.408.8111
-Original Message-
From: baptiste auguie [mailto:baptiste.aug...@googlemail.com]
Sent: Tuesday, January 12, 2010 12:20 PM
To: Greg Snow
Cc: r-help
Subject: Re: [R] expand.grid game
Nice --- am I missing something or was this closed form solution not
entirely trivial to find?
I ought to compile the various clever solutions given in this thread
someday, it's fascinating!
Thanks,
baptiste
2010/1/12 Greg Snow greg.s...@imail.org:
This also has a closed form solution:
choose(16+8-1,7) - choose(7+8-1, 7) - 7*choose(6+8-1,7)
[1] 229713
--
Gregory (Greg) L. Snow Ph.D.
Statistical Data Center
Intermountain Healthcare
greg.s...@imail.org
801.408.8111
-Original Message-
From: r-help-boun...@r-project.org [mailto:r-help-boun...@r-
project.org] On Behalf Of Brian Diggs
Sent: Thursday, December 31, 2009 3:08 PM
To: baptiste auguie; David Winsemius
Cc: r-help
Subject: Re: [R] expand.grid game
baptiste auguie wrote:
2009/12/19 David Winsemius dwinsem...@comcast.net:
On Dec 19, 2009, at 9:06 AM, baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm
not
sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum
of
their digits equal to 17?
And are you considering the number 0089 to be in the
acceptable set?
Or is the range of possible numbers in 1079:9800 ?
The latter, the first digit should not be 0. But if you have an
interesting solution for the other case, let me know anyway.
I should also stress that this is only for entertainment and
curiosity's sake.
baptiste
I realize I'm late coming to this, but I was reading it in my post-
vacation catch-up and it sounded interesting so I thought I'd give
it a
shot.
After coding a couple of solutions that were exponential in time
(for
the number of digits), I rearranged things and came up with
something
that is linear in time (for the number of digits) and gives the
count
of numbers for all sums at once:
library(plyr)
nsum3 - function(digits) {
digits - as.integer(digits)[[1L]]
if (digits==1) {
rep(1,9)
} else {
dm1 - nsum3(digits-1)
Reduce(+, llply(0:9, function(x) {c(rep(0,x),dm1,rep(0,9-
x))}))
}
}
nsums - llply(1:8, nsum3)
nsums[[5]][17]
# [1] 3675
nsums[[8]][17]
# [1] 229713
The whole thing runs in well under a second on my machine (a several
years old dual core Windows machine). In the results of nsum3, the
i-
th element is the number of numbers whose digits sum to i. The
basic
idea is recursion on the number of digits; if n_{t,d} is the number
of
d-digit numbers that sum to t, then n_{t,d} = \sum_{i\in(0,9)}
n_{t-
i,d-1}. (Adding the digit i to each of those numbers makes their
sum
t and increases the digits to d). When digits==1, then 0 isn't a
valid
choice and that also implies the sum of digits can't be 0, which
fits
well with the 1 indexing of arrays.
--
Brian Diggs, Ph.D.
Senior Research Associate, Department of Surgery, Oregon Health
Science University
__
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] expand.grid game
On 13/01/2010, at 9:19 AM, Greg Snow wrote:
How trivial is probably subjective, I don't think it is much above
trivial. I would not have been surprised to see this question on
an exam in my undergraduate (300 or junior level) probability
course (the hard part was remembering the details from that class
from over 20 years ago). My favorite test question of all time
came from that course: You have a deck of poker cards with the 3's
removed (and jokers), you deal yourself 5 cards at random, what is
the probability of getting a straight (not including straight
flushes)?
This problem is simpler. Just think of the 8 places in the number
as urns, and the 17 1's as balls to be put into the urns. One ball
has to go in the first urn, so you have 16 left, there are choose(16
+8-1,8-1) ways to distribute 16 undistinguishable balls among 8
distinguishable urns. But that includes some solutions with more
than 9 balls in an urn which violates the digits restriction, so
subtract off the illegal counts. If we place 10 balls in the first
urn, then we have 7 remaining balls to distribute between the 8
urns or choose( 7+8-1, 7), If we place 1 ball in the first urn and
10 balls in one of the 7 other urns (7*), then there are choose( 6
+8-1, 7 ) ways to distribute the remaining 6 balls in the 8 urns.
Not too complicated once you remember (or look up) the formula for
urns and balls.
Sorry to be a thicko --- but doesn't the foregoing solution *leave
in* the possibility
of putting all 17 balls in the first urn? Or 3 balls in the first
urn, 12 in the second,
and the remaining 2 in any of the other six urns? Etc. I.e. don't
more terms have to
be subtracted?
cheers,
Rolf Turner
##
Attention:\ This e-mail message is privileged and confid...{{dropped:9}}
__
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] expand.grid game --- never mind, I figured it out!
I re-read the solution that you posted and realized where my thinking
was going wrong. Sorry (again!) for being a thicko.
cheers,
Rolf Turner
On 13/01/2010, at 9:19 AM, Greg Snow wrote:
How trivial is probably subjective, I don't think it is much above
trivial. I would not have been surprised to see this question on
an exam in my undergraduate (300 or junior level) probability
course (the hard part was remembering the details from that class
from over 20 years ago). My favorite test question of all time
came from that course: You have a deck of poker cards with the 3's
removed (and jokers), you deal yourself 5 cards at random, what is
the probability of getting a straight (not including straight
flushes)?
This problem is simpler. Just think of the 8 places in the number
as urns, and the 17 1's as balls to be put into the urns. One ball
has to go in the first urn, so you have 16 left, there are choose(16
+8-1,8-1) ways to distribute 16 undistinguishable balls among 8
distinguishable urns. But that includes some solutions with more
than 9 balls in an urn which violates the digits restriction, so
subtract off the illegal counts. If we place 10 balls in the first
urn, then we have 7 remaining balls to distribute between the 8
urns or choose( 7+8-1, 7), If we place 1 ball in the first urn and
10 balls in one of the 7 other urns (7*), then there are choose( 6
+8-1, 7 ) ways to distribute the remaining 6 balls in the 8 urns.
Not too complicated once you remember (or look up) the formula for
urns and balls.
--
Gregory (Greg) L. Snow Ph.D.
Statistical Data Center
Intermountain Healthcare
greg.s...@imail.org
801.408.8111
-Original Message-
From: baptiste auguie [mailto:baptiste.aug...@googlemail.com]
Sent: Tuesday, January 12, 2010 12:20 PM
To: Greg Snow
Cc: r-help
Subject: Re: [R] expand.grid game
Nice --- am I missing something or was this closed form solution not
entirely trivial to find?
I ought to compile the various clever solutions given in this thread
someday, it's fascinating!
Thanks,
baptiste
2010/1/12 Greg Snow greg.s...@imail.org:
This also has a closed form solution:
choose(16+8-1,7) - choose(7+8-1, 7) - 7*choose(6+8-1,7)
[1] 229713
--
Gregory (Greg) L. Snow Ph.D.
Statistical Data Center
Intermountain Healthcare
greg.s...@imail.org
801.408.8111
-Original Message-
From: r-help-boun...@r-project.org [mailto:r-help-boun...@r-
project.org] On Behalf Of Brian Diggs
Sent: Thursday, December 31, 2009 3:08 PM
To: baptiste auguie; David Winsemius
Cc: r-help
Subject: Re: [R] expand.grid game
baptiste auguie wrote:
2009/12/19 David Winsemius dwinsem...@comcast.net:
On Dec 19, 2009, at 9:06 AM, baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm
not
sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum
of
their digits equal to 17?
And are you considering the number 0089 to be in the
acceptable set?
Or is the range of possible numbers in 1079:9800 ?
The latter, the first digit should not be 0. But if you have an
interesting solution for the other case, let me know anyway.
I should also stress that this is only for entertainment and
curiosity's sake.
baptiste
I realize I'm late coming to this, but I was reading it in my post-
vacation catch-up and it sounded interesting so I thought I'd give
it a
shot.
After coding a couple of solutions that were exponential in time
(for
the number of digits), I rearranged things and came up with
something
that is linear in time (for the number of digits) and gives the
count
of numbers for all sums at once:
library(plyr)
nsum3 - function(digits) {
digits - as.integer(digits)[[1L]]
if (digits==1) {
rep(1,9)
} else {
dm1 - nsum3(digits-1)
Reduce(+, llply(0:9, function(x) {c(rep(0,x),dm1,rep(0,9-
x))}))
}
}
nsums - llply(1:8, nsum3)
nsums[[5]][17]
# [1] 3675
nsums[[8]][17]
# [1] 229713
The whole thing runs in well under a second on my machine (a
several
years old dual core Windows machine). In the results of nsum3, the
i-
th element is the number of numbers whose digits sum to i. The
basic
idea is recursion on the number of digits; if n_{t,d} is the number
of
d-digit numbers that sum to t, then n_{t,d} = \sum_{i\in(0,9)}
n_{t-
i,d-1}. (Adding the digit i to each of those numbers makes their
sum
t and increases the digits to d). When digits==1, then 0 isn't a
valid
choice and that also implies the sum of digits can't be 0, which
fits
well with the 1 indexing of arrays.
--
Brian Diggs, Ph.D.
Senior Research Associate, Department of Surgery, Oregon Health
Science University
__
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
Re: [R] expand.grid game
baptiste auguie wrote:
2009/12/19 David Winsemius dwinsem...@comcast.net:
On Dec 19, 2009, at 9:06 AM, baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm not sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
And are you considering the number 0089 to be in the acceptable set?
Or is the range of possible numbers in 1079:9800 ?
The latter, the first digit should not be 0. But if you have an
interesting solution for the other case, let me know anyway.
I should also stress that this is only for entertainment and curiosity's sake.
baptiste
I realize I'm late coming to this, but I was reading it in my post-vacation
catch-up and it sounded interesting so I thought I'd give it a shot.
After coding a couple of solutions that were exponential in time (for the
number of digits), I rearranged things and came up with something that is
linear in time (for the number of digits) and gives the count of numbers for
all sums at once:
library(plyr)
nsum3 - function(digits) {
digits - as.integer(digits)[[1L]]
if (digits==1) {
rep(1,9)
} else {
dm1 - nsum3(digits-1)
Reduce(+, llply(0:9, function(x) {c(rep(0,x),dm1,rep(0,9-x))}))
}
}
nsums - llply(1:8, nsum3)
nsums[[5]][17]
# [1] 3675
nsums[[8]][17]
# [1] 229713
The whole thing runs in well under a second on my machine (a several years old
dual core Windows machine). In the results of nsum3, the i-th element is the
number of numbers whose digits sum to i. The basic idea is recursion on the
number of digits; if n_{t,d} is the number of d-digit numbers that sum to t,
then n_{t,d} = \sum_{i\in(0,9)} n_{t-i,d-1}. (Adding the digit i to each of
those numbers makes their sum t and increases the digits to d). When
digits==1, then 0 isn't a valid choice and that also implies the sum of digits
can't be 0, which fits well with the 1 indexing of arrays.
--
Brian Diggs, Ph.D.
Senior Research Associate, Department of Surgery, Oregon Health Science
University
__
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] expand.grid game
Hi
library(partitions)
jj - blockparts(rep(9,8),17)
dim(jj)
gives 318648
HTH
rksh
baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm not sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
The brute-force answer could be:
maxi - 9 # digits from 0 to 9
N - 5 # 8 is too large
test - 17 # for example's sake
sum(rowSums(do.call(expand.grid, c(list(1:maxi), rep(list(0:maxi),
N-1 == test)
## 3675
Now, if I make N = 8, R stalls for some time and finally gives up with:
Error: cannot allocate vector of size 343.3 Mb
I thought I could get around this using Reduce() to recursively apply
rowSum to intermediate results, but it doesn't seem to help,
a=list(1:maxi)
b=rep(list(0:maxi), N-1)
foo - function(a, b, fun=sum, ...){
switch(fun,
'sum' = rowSums(do.call(expand.grid, c(a, b))),
'mean' = rowMeans(do.call(expand.grid, c(a, b))),
apply(do.call(expand.grid, c(a, b)), 1, fun, ...)) # generic case
}
sum(Reduce(foo, list(b), init=a) == test)
## 3675 # OK
Same problem with N=8.
Now, if N was fixed I could write a little C code to do this
calculation term-by-term, something along those lines,
test = 0;
for (i1=1, i1=9, i1++) {
for (i2=0, i2=9, i2++) {
[... other nested loops ]
test = test + (i1 + i2 + [...] == 17);
} [...]
}
but here the number of for loops, N, should remain a variable.
In despair I coded this in R as a wicked eval(parse()) construct, and
it does produce the expected result after an awfully long time.
makeNestedLoops - function(N=3){
startLoop - function(ii, start=1, end=9){
paste(for (i, ii, in seq(,start,, ,end,)) {\n, sep=)
}
first - startLoop(1)
inner.start - lapply(seq(2, N), startLoop, start=0)
calculation - paste(test - test + (, paste(i, seq(1, N),
sep=, collapse=+), ==17 )\n)
end - replicate(N, }\n)
code.to.run - do.call(paste, c(list(first), inner.start, calculation, end))
cat(code.to.run)
invisible(code.to.run)
}
test - 0
eval(parse(text = makeNestedLoops(8)) )
## 229713
I hope I have missed a better way to do this in R. Otherwise, I
believe what I'm after is some kind of C or C++ macro expansion,
because the number of loops should not be hard coded.
Thanks for any tips you may have!
Best regards,
baptiste
__
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.
--
Robin K. S. Hankin
Uncertainty Analyst
University of Cambridge
19 Silver Street
Cambridge CB3 9EP
01223-764877
__
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] expand.grid game
Wow!
system.time({
all = blockparts(rep(9,8),17)
print( dim(all[,all[1,]!=0])[2] ) # remove leading 0s
})
## 229713
user system elapsed
0.160 0.068 0.228
In some ways I think this is close to Hadley's suggestion, though I
didn't know how to implement it.
Thanks a lot to everybody who participated, I have learned interesting
things from a seemingly innocuous question.
Best regards,
baptiste
2009/12/21 Robin Hankin rk...@cam.ac.uk:
Hi
library(partitions)
jj - blockparts(rep(9,8),17)
dim(jj)
gives 318648
HTH
rksh
baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm not sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
The brute-force answer could be:
maxi - 9 # digits from 0 to 9
N - 5 # 8 is too large
test - 17 # for example's sake
sum(rowSums(do.call(expand.grid, c(list(1:maxi), rep(list(0:maxi),
N-1 == test)
## 3675
Now, if I make N = 8, R stalls for some time and finally gives up with:
Error: cannot allocate vector of size 343.3 Mb
I thought I could get around this using Reduce() to recursively apply
rowSum to intermediate results, but it doesn't seem to help,
a=list(1:maxi)
b=rep(list(0:maxi), N-1)
foo - function(a, b, fun=sum, ...){
switch(fun,
'sum' = rowSums(do.call(expand.grid, c(a, b))),
'mean' = rowMeans(do.call(expand.grid, c(a, b))),
apply(do.call(expand.grid, c(a, b)), 1, fun, ...)) # generic case
}
sum(Reduce(foo, list(b), init=a) == test)
## 3675 # OK
Same problem with N=8.
Now, if N was fixed I could write a little C code to do this
calculation term-by-term, something along those lines,
test = 0;
for (i1=1, i1=9, i1++) {
for (i2=0, i2=9, i2++) {
[... other nested loops ]
test = test + (i1 + i2 + [...] == 17);
} [...]
}
but here the number of for loops, N, should remain a variable.
In despair I coded this in R as a wicked eval(parse()) construct, and
it does produce the expected result after an awfully long time.
makeNestedLoops - function(N=3){
startLoop - function(ii, start=1, end=9){
paste(for (i, ii, in seq(,start,, ,end,)) {\n, sep=)
}
first - startLoop(1)
inner.start - lapply(seq(2, N), startLoop, start=0)
calculation - paste(test - test + (, paste(i, seq(1, N),
sep=, collapse=+), ==17 )\n)
end - replicate(N, }\n)
code.to.run - do.call(paste, c(list(first), inner.start, calculation,
end))
cat(code.to.run)
invisible(code.to.run)
}
test - 0
eval(parse(text = makeNestedLoops(8)) )
## 229713
I hope I have missed a better way to do this in R. Otherwise, I
believe what I'm after is some kind of C or C++ macro expansion,
because the number of loops should not be hard coded.
Thanks for any tips you may have!
Best regards,
baptiste
__
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.
--
Robin K. S. Hankin
Uncertainty Analyst
University of Cambridge
19 Silver Street
Cambridge CB3 9EP
01223-764877
__
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] expand.grid game
Hello again everybody.
I fired off my reply before reading the correspondence about
the leading zeros.
You can also assume that there is at least one block
at the leading position, [so that position can take 0,1,2,...,8 additional
blocks] and distribute the remaining 16 blocks amongst all 8
places:
system.time(dim(blockparts(c(8,rep(9,7)),16)))
user system elapsed
0.056 0.016 0.069
this is faster! :-)
best wishes
rksh
baptiste auguie wrote:
Wow!
system.time({
all = blockparts(rep(9,8),17)
print( dim(all[,all[1,]!=0])[2] ) # remove leading 0s
})
## 229713
user system elapsed
0.160 0.068 0.228
In some ways I think this is close to Hadley's suggestion, though I
didn't know how to implement it.
Thanks a lot to everybody who participated, I have learned interesting
things from a seemingly innocuous question.
Best regards,
baptiste
2009/12/21 Robin Hankin rk...@cam.ac.uk:
Hi
library(partitions)
jj - blockparts(rep(9,8),17)
dim(jj)
gives 318648
HTH
rksh
baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm not sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
The brute-force answer could be:
maxi - 9 # digits from 0 to 9
N - 5 # 8 is too large
test - 17 # for example's sake
sum(rowSums(do.call(expand.grid, c(list(1:maxi), rep(list(0:maxi),
N-1 == test)
## 3675
Now, if I make N = 8, R stalls for some time and finally gives up with:
Error: cannot allocate vector of size 343.3 Mb
I thought I could get around this using Reduce() to recursively apply
rowSum to intermediate results, but it doesn't seem to help,
a=list(1:maxi)
b=rep(list(0:maxi), N-1)
foo - function(a, b, fun=sum, ...){
switch(fun,
'sum' = rowSums(do.call(expand.grid, c(a, b))),
'mean' = rowMeans(do.call(expand.grid, c(a, b))),
apply(do.call(expand.grid, c(a, b)), 1, fun, ...)) # generic case
}
sum(Reduce(foo, list(b), init=a) == test)
## 3675 # OK
Same problem with N=8.
Now, if N was fixed I could write a little C code to do this
calculation term-by-term, something along those lines,
test = 0;
for (i1=1, i1=9, i1++) {
for (i2=0, i2=9, i2++) {
[... other nested loops ]
test = test + (i1 + i2 + [...] == 17);
} [...]
}
but here the number of for loops, N, should remain a variable.
In despair I coded this in R as a wicked eval(parse()) construct, and
it does produce the expected result after an awfully long time.
makeNestedLoops - function(N=3){
startLoop - function(ii, start=1, end=9){
paste(for (i, ii, in seq(,start,, ,end,)) {\n, sep=)
}
first - startLoop(1)
inner.start - lapply(seq(2, N), startLoop, start=0)
calculation - paste(test - test + (, paste(i, seq(1, N),
sep=, collapse=+), ==17 )\n)
end - replicate(N, }\n)
code.to.run - do.call(paste, c(list(first), inner.start, calculation,
end))
cat(code.to.run)
invisible(code.to.run)
}
test - 0
eval(parse(text = makeNestedLoops(8)) )
## 229713
I hope I have missed a better way to do this in R. Otherwise, I
believe what I'm after is some kind of C or C++ macro expansion,
because the number of loops should not be hard coded.
Thanks for any tips you may have!
Best regards,
baptiste
__
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.
--
Robin K. S. Hankin
Uncertainty Analyst
University of Cambridge
19 Silver Street
Cambridge CB3 9EP
01223-764877
--
Robin K. S. Hankin
Uncertainty Analyst
University of Cambridge
19 Silver Street
Cambridge CB3 9EP
01223-764877
__
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] expand.grid game
I wonder whether this answers Baptiste's question as asked.
1: An 8-digit number can have some digits equal to 0;
see Baptiste's comment maxi - 9 # digits from 0 to 9
2: According to the man-page fror blockparts in partitions,
all sets of a=(a1,...,an) satisfying Sum[ai] = n subject
to 0 ai = yi are given in lexicographical order.
So it would seem that blockparts would not count 8-digit numbers
which have some zero digits.
One could presumably fake it by looping over the number of
non-zero digits, from 2 to 8 -- something like:
all - 0
for(i in (2:8)){
jj - blockparts(rep(9,8),17)
all - all + dim(jj)
}
Or am I missing something?!
Ted.
On 21-Dec-09 07:57:32, Robin Hankin wrote:
Hi
library(partitions)
jj - blockparts(rep(9,8),17)
dim(jj)
gives 318648
HTH
rksh
baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm not sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
The brute-force answer could be:
maxi - 9 # digits from 0 to 9
N - 5 # 8 is too large
test - 17 # for example's sake
sum(rowSums(do.call(expand.grid, c(list(1:maxi), rep(list(0:maxi),
N-1 == test)
## 3675
Now, if I make N = 8, R stalls for some time and finally gives up
with:
Error: cannot allocate vector of size 343.3 Mb
I thought I could get around this using Reduce() to recursively apply
rowSum to intermediate results, but it doesn't seem to help,
a=list(1:maxi)
b=rep(list(0:maxi), N-1)
foo - function(a, b, fun=sum, ...){
switch(fun,
'sum' = rowSums(do.call(expand.grid, c(a, b))),
'mean' = rowMeans(do.call(expand.grid, c(a, b))),
apply(do.call(expand.grid, c(a, b)), 1, fun, ...)) # generic
case
}
sum(Reduce(foo, list(b), init=a) == test)
## 3675 # OK
Same problem with N=8.
Now, if N was fixed I could write a little C code to do this
calculation term-by-term, something along those lines,
test = 0;
for (i1=1, i1=9, i1++) {
for (i2=0, i2=9, i2++) {
[... other nested loops ]
test = test + (i1 + i2 + [...] == 17);
} [...]
}
but here the number of for loops, N, should remain a variable.
In despair I coded this in R as a wicked eval(parse()) construct, and
it does produce the expected result after an awfully long time.
makeNestedLoops - function(N=3){
startLoop - function(ii, start=1, end=9){
paste(for (i, ii, in seq(,start,, ,end,)) {\n, sep=)
}
first - startLoop(1)
inner.start - lapply(seq(2, N), startLoop, start=0)
calculation - paste(test - test + (, paste(i, seq(1, N),
sep=, collapse=+), ==17 )\n)
end - replicate(N, }\n)
code.to.run - do.call(paste, c(list(first), inner.start,
calculation, end))
cat(code.to.run)
invisible(code.to.run)
}
test - 0
eval(parse(text = makeNestedLoops(8)) )
## 229713
I hope I have missed a better way to do this in R. Otherwise, I
believe what I'm after is some kind of C or C++ macro expansion,
because the number of loops should not be hard coded.
Thanks for any tips you may have!
Best regards,
baptiste
E-Mail: (Ted Harding) ted.hard...@manchester.ac.uk
Fax-to-email: +44 (0)870 094 0861
Date: 21-Dec-09 Time: 08:45:09
-- XFMail --
__
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] expand.grid game
OOPS!! See correction below!
On 21-Dec-09 08:45:13, Ted Harding wrote:
I wonder whether this answers Baptiste's question as asked.
1: An 8-digit number can have some digits equal to 0;
see Baptiste's comment maxi - 9 # digits from 0 to 9
2: According to the man-page fror blockparts in partitions,
all sets of a=(a1,...,an) satisfying Sum[ai] = n subject
to 0 ai = yi are given in lexicographical order.
So it would seem that blockparts would not count 8-digit numbers
which have some zero digits.
One could presumably fake it by looping over the number of
non-zero digits, from 2 to 8 -- something like:
all - 0
for(i in (2:8)){
jj - blockparts(rep(9,8),17)
jj - blockparts(rep(9,i),17)
all - all + dim(jj)
}
Or am I missing something?!
Ted.
On 21-Dec-09 07:57:32, Robin Hankin wrote:
Hi
library(partitions)
jj - blockparts(rep(9,8),17)
dim(jj)
gives 318648
HTH
rksh
baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm not
sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
The brute-force answer could be:
maxi - 9 # digits from 0 to 9
N - 5 # 8 is too large
test - 17 # for example's sake
sum(rowSums(do.call(expand.grid, c(list(1:maxi), rep(list(0:maxi),
N-1 == test)
## 3675
Now, if I make N = 8, R stalls for some time and finally gives up
with:
Error: cannot allocate vector of size 343.3 Mb
I thought I could get around this using Reduce() to recursively apply
rowSum to intermediate results, but it doesn't seem to help,
a=list(1:maxi)
b=rep(list(0:maxi), N-1)
foo - function(a, b, fun=sum, ...){
switch(fun,
'sum' = rowSums(do.call(expand.grid, c(a, b))),
'mean' = rowMeans(do.call(expand.grid, c(a, b))),
apply(do.call(expand.grid, c(a, b)), 1, fun, ...)) # generic
case
}
sum(Reduce(foo, list(b), init=a) == test)
## 3675 # OK
Same problem with N=8.
Now, if N was fixed I could write a little C code to do this
calculation term-by-term, something along those lines,
test = 0;
for (i1=1, i1=9, i1++) {
for (i2=0, i2=9, i2++) {
[... other nested loops ]
test = test + (i1 + i2 + [...] == 17);
} [...]
}
but here the number of for loops, N, should remain a variable.
In despair I coded this in R as a wicked eval(parse()) construct, and
it does produce the expected result after an awfully long time.
makeNestedLoops - function(N=3){
startLoop - function(ii, start=1, end=9){
paste(for (i, ii, in seq(,start,, ,end,)) {\n, sep=)
}
first - startLoop(1)
inner.start - lapply(seq(2, N), startLoop, start=0)
calculation - paste(test - test + (, paste(i, seq(1, N),
sep=, collapse=+), ==17 )\n)
end - replicate(N, }\n)
code.to.run - do.call(paste, c(list(first), inner.start,
calculation, end))
cat(code.to.run)
invisible(code.to.run)
}
test - 0
eval(parse(text = makeNestedLoops(8)) )
## 229713
I hope I have missed a better way to do this in R. Otherwise, I
believe what I'm after is some kind of C or C++ macro expansion,
because the number of loops should not be hard coded.
Thanks for any tips you may have!
Best regards,
baptiste
E-Mail: (Ted Harding) ted.hard...@manchester.ac.uk
Fax-to-email: +44 (0)870 094 0861
Date: 21-Dec-09 Time: 08:45:09
-- XFMail --
__
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.
E-Mail: (Ted Harding) ted.hard...@manchester.ac.uk
Fax-to-email: +44 (0)870 094 0861
Date: 21-Dec-09 Time: 08:49:59
-- XFMail --
__
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] expand.grid game
Hi Ted.
you've found a bug in the documentation for blockparts().
It should read 0 = ai = yi. I'll fix it before the next
major release (which will include sampling without replacement from
a multiset, Insha'Allah).
Best wishes
rksh
(Ted Harding) wrote:
I wonder whether this answers Baptiste's question as asked.
1: An 8-digit number can have some digits equal to 0;
see Baptiste's comment maxi - 9 # digits from 0 to 9
2: According to the man-page fror blockparts in partitions,
all sets of a=(a1,...,an) satisfying Sum[ai] = n subject
to 0 ai = yi are given in lexicographical order.
So it would seem that blockparts would not count 8-digit numbers
which have some zero digits.
One could presumably fake it by looping over the number of
non-zero digits, from 2 to 8 -- something like:
all - 0
for(i in (2:8)){
jj - blockparts(rep(9,8),17)
all - all + dim(jj)
}
Or am I missing something?!
Ted.
On 21-Dec-09 07:57:32, Robin Hankin wrote:
Hi
library(partitions)
jj - blockparts(rep(9,8),17)
dim(jj)
gives 318648
HTH
rksh
baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm not sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
The brute-force answer could be:
maxi - 9 # digits from 0 to 9
N - 5 # 8 is too large
test - 17 # for example's sake
sum(rowSums(do.call(expand.grid, c(list(1:maxi), rep(list(0:maxi),
N-1 == test)
## 3675
Now, if I make N = 8, R stalls for some time and finally gives up
with:
Error: cannot allocate vector of size 343.3 Mb
I thought I could get around this using Reduce() to recursively apply
rowSum to intermediate results, but it doesn't seem to help,
a=list(1:maxi)
b=rep(list(0:maxi), N-1)
foo - function(a, b, fun=sum, ...){
switch(fun,
'sum' = rowSums(do.call(expand.grid, c(a, b))),
'mean' = rowMeans(do.call(expand.grid, c(a, b))),
apply(do.call(expand.grid, c(a, b)), 1, fun, ...)) # generic
case
}
sum(Reduce(foo, list(b), init=a) == test)
## 3675 # OK
Same problem with N=8.
Now, if N was fixed I could write a little C code to do this
calculation term-by-term, something along those lines,
test = 0;
for (i1=1, i1=9, i1++) {
for (i2=0, i2=9, i2++) {
[... other nested loops ]
test = test + (i1 + i2 + [...] == 17);
} [...]
}
but here the number of for loops, N, should remain a variable.
In despair I coded this in R as a wicked eval(parse()) construct, and
it does produce the expected result after an awfully long time.
makeNestedLoops - function(N=3){
startLoop - function(ii, start=1, end=9){
paste(for (i, ii, in seq(,start,, ,end,)) {\n, sep=)
}
first - startLoop(1)
inner.start - lapply(seq(2, N), startLoop, start=0)
calculation - paste(test - test + (, paste(i, seq(1, N),
sep=, collapse=+), ==17 )\n)
end - replicate(N, }\n)
code.to.run - do.call(paste, c(list(first), inner.start,
calculation, end))
cat(code.to.run)
invisible(code.to.run)
}
test - 0
eval(parse(text = makeNestedLoops(8)) )
## 229713
I hope I have missed a better way to do this in R. Otherwise, I
believe what I'm after is some kind of C or C++ macro expansion,
because the number of loops should not be hard coded.
Thanks for any tips you may have!
Best regards,
baptiste
E-Mail: (Ted Harding) ted.hard...@manchester.ac.uk
Fax-to-email: +44 (0)870 094 0861
Date: 21-Dec-09 Time: 08:45:09
-- XFMail --
--
Robin K. S. Hankin
Uncertainty Analyst
University of Cambridge
19 Silver Street
Cambridge CB3 9EP
01223-764877
__
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] expand.grid game
Dear list,
In a little numbers game, I've hit a performance snag and I'm not sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
The brute-force answer could be:
maxi - 9 # digits from 0 to 9
N - 5 # 8 is too large
test - 17 # for example's sake
sum(rowSums(do.call(expand.grid, c(list(1:maxi), rep(list(0:maxi),
N-1 == test)
## 3675
Now, if I make N = 8, R stalls for some time and finally gives up with:
Error: cannot allocate vector of size 343.3 Mb
I thought I could get around this using Reduce() to recursively apply
rowSum to intermediate results, but it doesn't seem to help,
a=list(1:maxi)
b=rep(list(0:maxi), N-1)
foo - function(a, b, fun=sum, ...){
switch(fun,
'sum' = rowSums(do.call(expand.grid, c(a, b))),
'mean' = rowMeans(do.call(expand.grid, c(a, b))),
apply(do.call(expand.grid, c(a, b)), 1, fun, ...)) # generic case
}
sum(Reduce(foo, list(b), init=a) == test)
## 3675 # OK
Same problem with N=8.
Now, if N was fixed I could write a little C code to do this
calculation term-by-term, something along those lines,
test = 0;
for (i1=1, i1=9, i1++) {
for (i2=0, i2=9, i2++) {
[... other nested loops ]
test = test + (i1 + i2 + [...] == 17);
} [...]
}
but here the number of for loops, N, should remain a variable.
In despair I coded this in R as a wicked eval(parse()) construct, and
it does produce the expected result after an awfully long time.
makeNestedLoops - function(N=3){
startLoop - function(ii, start=1, end=9){
paste(for (i, ii, in seq(,start,, ,end,)) {\n, sep=)
}
first - startLoop(1)
inner.start - lapply(seq(2, N), startLoop, start=0)
calculation - paste(test - test + (, paste(i, seq(1, N),
sep=, collapse=+), ==17 )\n)
end - replicate(N, }\n)
code.to.run - do.call(paste, c(list(first), inner.start, calculation, end))
cat(code.to.run)
invisible(code.to.run)
}
test - 0
eval(parse(text = makeNestedLoops(8)) )
## 229713
I hope I have missed a better way to do this in R. Otherwise, I
believe what I'm after is some kind of C or C++ macro expansion,
because the number of loops should not be hard coded.
Thanks for any tips you may have!
Best regards,
baptiste
__
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] expand.grid game
On Dec 19, 2009, at 9:06 AM, baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm not sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
The brute-force answer could be:
maxi - 9 # digits from 0 to 9
N - 5 # 8 is too large
test - 17 # for example's sake
sum(rowSums(do.call(expand.grid, c(list(1:maxi), rep(list(0:maxi),
N-1 == test)
## 3675
Now, if I make N = 8, R stalls for some time and finally gives up
with:
Error: cannot allocate vector of size 343.3 Mb
I thought I could get around this using Reduce() to recursively apply
rowSum to intermediate results, but it doesn't seem to help,
a=list(1:maxi)
b=rep(list(0:maxi), N-1)
foo - function(a, b, fun=sum, ...){
switch(fun,
'sum' = rowSums(do.call(expand.grid, c(a, b))),
'mean' = rowMeans(do.call(expand.grid, c(a, b))),
apply(do.call(expand.grid, c(a, b)), 1, fun, ...)) # generic
case
}
sum(Reduce(foo, list(b), init=a) == test)
## 3675 # OK
And are you considering the number 0089 to be in the acceptable
set? Or is the range of possible numbers in 1079:9800 ?
--
David
Same problem with N=8.
Now, if N was fixed I could write a little C code to do this
calculation term-by-term, something along those lines,
test = 0;
for (i1=1, i1=9, i1++) {
for (i2=0, i2=9, i2++) {
[... other nested loops ]
test = test + (i1 + i2 + [...] == 17);
} [...]
}
but here the number of for loops, N, should remain a variable.
In despair I coded this in R as a wicked eval(parse()) construct, and
it does produce the expected result after an awfully long time.
makeNestedLoops - function(N=3){
startLoop - function(ii, start=1, end=9){
paste(for (i, ii, in seq(,start,, ,end,)) {\n, sep=)
}
first - startLoop(1)
inner.start - lapply(seq(2, N), startLoop, start=0)
calculation - paste(test - test + (, paste(i, seq(1, N),
sep=, collapse=+), ==17 )\n)
end - replicate(N, }\n)
code.to.run - do.call(paste, c(list(first), inner.start,
calculation, end))
cat(code.to.run)
invisible(code.to.run)
}
test - 0
eval(parse(text = makeNestedLoops(8)) )
## 229713
I hope I have missed a better way to do this in R. Otherwise, I
believe what I'm after is some kind of C or C++ macro expansion,
because the number of loops should not be hard coded.
Thanks for any tips you may have!
Best regards,
baptiste
__
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.
David Winsemius, MD
Heritage Laboratories
West Hartford, CT
__
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] expand.grid game
2009/12/19 David Winsemius dwinsem...@comcast.net: On Dec 19, 2009, at 9:06 AM, baptiste auguie wrote: Dear list, In a little numbers game, I've hit a performance snag and I'm not sure how to code this in C. The game is the following: how many 8-digit numbers have the sum of their digits equal to 17? And are you considering the number 0089 to be in the acceptable set? Or is the range of possible numbers in 1079:9800 ? The latter, the first digit should not be 0. But if you have an interesting solution for the other case, let me know anyway. I should also stress that this is only for entertainment and curiosity's sake. baptiste __ 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] expand.grid game
I hope I have missed a better way to do this in R. Otherwise, I believe what I'm after is some kind of C or C++ macro expansion, because the number of loops should not be hard coded. Why not generate the list of integers that sum to 17, and then mix with 0s as appropriate? Hadley -- http://had.co.nz/ __ 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] expand.grid game
On Dec 19, 2009, at 1:36 PM, baptiste auguie wrote:
2009/12/19 David Winsemius dwinsem...@comcast.net:
On Dec 19, 2009, at 9:06 AM, baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm not
sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
And are you considering the number 0089 to be in the
acceptable set?
Or is the range of possible numbers in 1079:9800 ?
The latter, the first digit should not be 0. But if you have an
interesting solution for the other case, let me know anyway.
I should also stress that this is only for entertainment and
curiosity's sake.
The sequence of numbers whose digit sum is 13 is one of the ATT
integer sequences:
http://www.research.att.com/~njas/sequences/A143164
No R implementations there, only Maple and Mathematica. Rather than
doing strsplit()'s, I thought that a mathematical approach would be
faster for a sumdigits function:
sumdigits - function(x) { s=0; for (i in 1:(1+floor(log(x,
base=10))) ){
s-s+x%%10; x-x%/%10}
return(s) }
# what follows would be expected to take roughly 1/100th and 1/50th
of the time of a complete enumeration but is useful for estimating the
size of the result and the time of an exhaustive search:
system.time( for (i in 1079:1179) if (sumdigits(i)==17)
{idx-c(idx,i)})
user system elapsed
30.997 3.516 34.403
system.time( for (i in 1079:1279) if (sumdigits(i)==17)
{idx-c(idx,i)})
user system elapsed
55.975 2.433 58.218
head(idx)
[1] 1079 1088 1097 1169 1178 1187
length(idx)
[1] 31572
So it looks as though an exhaustive strategy would take a bit under an
hour on my machine (a 2 year-old device) and be a vector around
1578600 elements in length. (Takes very little memory, and would
undoubtedly be faster if I could use more than one core.)
baptiste
David Winsemius, MD
Heritage Laboratories
West Hartford, CT
__
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] expand.grid game
Hi,
Thanks for the link, I guess it's some kind of a classic game. I'm a
bit surprised by your timing, my ugly eval(parse()) solution
definitely took less than one hour with a machine not so different
from yours,
system.time( for (i in 1079:1179) if (sumdigits(i)==17) {idx-c(idx,i)})
user system elapsed
34.050 1.109 35.791
I'm surprised by idx-c(idx,i), isn't that considered a sin in the R
Inferno? Presumably growing idx will waste time for large N.
Thanks,
baptiste
2009/12/19 David Winsemius dwinsem...@comcast.net:
On Dec 19, 2009, at 1:36 PM, baptiste auguie wrote:
2009/12/19 David Winsemius dwinsem...@comcast.net:
On Dec 19, 2009, at 9:06 AM, baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm not sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
And are you considering the number 0089 to be in the acceptable
set?
Or is the range of possible numbers in 1079:9800 ?
The latter, the first digit should not be 0. But if you have an
interesting solution for the other case, let me know anyway.
I should also stress that this is only for entertainment and curiosity's
sake.
The sequence of numbers whose digit sum is 13 is one of the ATT integer
sequences:
http://www.research.att.com/~njas/sequences/A143164
No R implementations there, only Maple and Mathematica. Rather than doing
strsplit()'s, I thought that a mathematical approach would be faster for a
sumdigits function:
sumdigits - function(x) { s=0; for (i in 1:(1+floor(log(x, base=10))) ){
s-s+x%%10; x-x%/%10}
return(s) }
# what follows would be expected to take roughly 1/100th and 1/50th of the
time of a complete enumeration but is useful for estimating the size of the
result and the time of an exhaustive search:
system.time( for (i in 1079:1179) if (sumdigits(i)==17)
{idx-c(idx,i)})
user system elapsed
30.997 3.516 34.403
system.time( for (i in 1079:1279) if (sumdigits(i)==17)
{idx-c(idx,i)})
user system elapsed
55.975 2.433 58.218
head(idx)
[1] 1079 1088 1097 1169 1178 1187
length(idx)
[1] 31572
So it looks as though an exhaustive strategy would take a bit under an hour
on my machine (a 2 year-old device) and be a vector around 1578600 elements
in length. (Takes very little memory, and would undoubtedly be faster if I
could use more than one core.)
baptiste
David Winsemius, MD
Heritage Laboratories
West Hartford, CT
__
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] expand.grid game
This problem does yield some interesting and unexpected distributions.
Here is another, the number of positive cases as a function of number
of digits (8 in the original question) and of test value (17).
maxi - 9
N - 5
test - 17
foo - function(N=2, test=1){
sum(rowSums(do.call(expand.grid, c(list(1:maxi), rep(list(0:maxi),
N-1 == test)
}
library(plyr)
N - seq(1, 6)
maxi - 9*N
params - data.frame(from=N, to=maxi+1)
params2 - mlply(params, seq)
NN - lapply(seq_along(params2), function(x) rep(x, length(params2[[x]])))
params3 - data.frame(N=do.call(c, NN), test=do.call(c, params2))
results - mdply(params3, foo)
library(ggplot2)
p -
qplot(test, V1, data=results, geom=path)+
facet_wrap(~N, scales=free) +
scale_x_continuous(expand=c(0, 0))+
xlab(test) + ylab(number of match)
p
Best,
baptiste
[David: sorry for the duplicate, i initially sent an attachment that
was too large for the list]
2009/12/19 David Winsemius dwinsem...@comcast.net:
On Dec 19, 2009, at 2:10 PM, David Winsemius wrote:
On Dec 19, 2009, at 1:36 PM, baptiste auguie wrote:
2009/12/19 David Winsemius dwinsem...@comcast.net:
On Dec 19, 2009, at 9:06 AM, baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm not sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
And are you considering the number 0089 to be in the acceptable
set?
Or is the range of possible numbers in 1079:9800 ?
The latter, the first digit should not be 0. But if you have an
interesting solution for the other case, let me know anyway.
I should also stress that this is only for entertainment and curiosity's
sake.
The sequence of numbers whose digit sum is 13 is one of the ATT integer
sequences:
http://www.research.att.com/~njas/sequences/A143164
No R implementations there, only Maple and Mathematica. Rather than doing
strsplit()'s, I thought that a mathematical approach would be faster for a
sumdigits function:
sumdigits - function(x) { s=0; for (i in 1:(1+floor(log(x, base=10))) ){
s-s+x%%10; x-x%/%10}
return(s) }
# what follows would be expected to take roughly 1/100th and 1/50th of
the time of a complete enumeration but is useful for estimating the size of
the result and the time of an exhaustive search:
system.time( for (i in 1079:1179) if (sumdigits(i)==17)
{idx-c(idx,i)})
user system elapsed
30.997 3.516 34.403
system.time( for (i in 1079:1279) if (sumdigits(i)==17)
{idx-c(idx,i)})
user system elapsed
55.975 2.433 58.218
head(idx)
[1] 1079 1088 1097 1169 1178 1187
length(idx)
[1] 31572
So it looks as though an exhaustive strategy would take a bit under an
hour on my machine (a 2 year-old device) and be a vector around 1578600
elements in length. (Takes very little memory, and would undoubtedly be
faster if I could use more than one core.)
I was assuming that it would be a relatively constant density of numbers in
that range which can be seen to be false by examining a density plot of
roughly the first 5% of that range.
system.time( for (i in 1079:1479) if (sumdigits(i)==17)
{idx-c(idx,i)})
user system elapsed
113.074 5.764 118.391
plot(density(idx))
Plot attached:
baptiste
David Winsemius, MD
Heritage Laboratories
West Hartford, CT
__
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] expand.grid game
On Dec 19, 2009, at 2:28 PM, baptiste auguie wrote:
Hi,
Thanks for the link, I guess it's some kind of a classic game. I'm a
bit surprised by your timing, my ugly eval(parse()) solution
definitely took less than one hour with a machine not so different
from yours,
system.time( for (i in 1079:1179) if (sumdigits(i)==17)
{idx-c(idx,i)})
user system elapsed
34.050 1.109 35.791
I'm surprised by idx-c(idx,i), isn't that considered a sin in the R
Inferno? Presumably growing idx will waste time for large N.
So you want a vectorized solution?
vsum - Vectorize(sumdigits)
i - 1079:1479
system.time( v - i[vsum(i) == 17] ) # how's that for compact!
user system elapsed
166.595 0.973 170.047
Does not seem that much more efficient, although there is a lot about
this testing that I may be missing. What does it mean to have a system
time that is 1/5 the other method but the user time is longer? Am I
causing that by taking the focus away from the console window?
system.time( for (i in 1079:1479) if (sumdigits(i)==17)
{idx-c(idx,i)})
user system elapsed
113.074 5.764 118.391
--
David
Thanks,
baptiste
2009/12/19 David Winsemius dwinsem...@comcast.net:
On Dec 19, 2009, at 1:36 PM, baptiste auguie wrote:
2009/12/19 David Winsemius dwinsem...@comcast.net:
On Dec 19, 2009, at 9:06 AM, baptiste auguie wrote:
Dear list,
In a little numbers game, I've hit a performance snag and I'm
not sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum
of
their digits equal to 17?
And are you considering the number 0089 to be in the
acceptable
set?
Or is the range of possible numbers in 1079:9800 ?
The latter, the first digit should not be 0. But if you have an
interesting solution for the other case, let me know anyway.
I should also stress that this is only for entertainment and
curiosity's
sake.
The sequence of numbers whose digit sum is 13 is one of the ATT
integer
sequences:
http://www.research.att.com/~njas/sequences/A143164
No R implementations there, only Maple and Mathematica. Rather than
doing
strsplit()'s, I thought that a mathematical approach would be
faster for a
sumdigits function:
sumdigits - function(x) { s=0; for (i in 1:(1+floor(log(x,
base=10))) ){
s-s+x%%10; x-x%/%10}
return(s) }
# what follows would be expected to take roughly 1/100th and
1/50th of the
time of a complete enumeration but is useful for estimating the
size of the
result and the time of an exhaustive search:
system.time( for (i in 1079:1179) if (sumdigits(i)==17)
{idx-c(idx,i)})
user system elapsed
30.997 3.516 34.403
system.time( for (i in 1079:1279) if (sumdigits(i)==17)
{idx-c(idx,i)})
user system elapsed
55.975 2.433 58.218
head(idx)
[1] 1079 1088 1097 1169 1178 1187
length(idx)
[1] 31572
So it looks as though an exhaustive strategy would take a bit under
an hour
on my machine (a 2 year-old device) and be a vector around 1578600
elements
in length. (Takes very little memory, and would undoubtedly be
faster if I
could use more than one core.)
baptiste
David Winsemius, MD
Heritage Laboratories
West Hartford, CT
David Winsemius, MD
Heritage Laboratories
West Hartford, CT
__
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.
