[R] expand.grid game

[Robin Hankin]

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