[R] expand.grid game --- never mind, I figured it out!

[Rolf Turner]

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.snow at imail.org
> 801.408.8111
>
>
>> -----Original Message-----
>> From: baptiste auguie [mailto:baptiste.auguie at 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.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.
>>>
>
> ______________________________________________
> 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.


######################################################################
Attention:\ This e-mail message is privileged and confid...{{dropped:9}}