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.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

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.

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

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
######################################################################