[R] expand.grid game

[baptiste auguie]

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.Snow at 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.snow at imail.org
> 801.408.8111
>
>
>> -----Original Message-----
>> From: r-help-bounces at r-project.org [mailto:r-help-bounces at 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 <dwinsemius at 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 "00000089" to be in the
>> acceptable set?
>> >> Or is the range of possible numbers in 10000079:98000000 ?
>> >>
>> >
>> > 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 at 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.
>