[R] expand.grid game

[Greg Snow]

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.