[R] Indistinguishable balls into distinguishable boxes

[Marc Girondot]

Hi "the list" !

I would like to create a dataframe that answer to : "all the 
combinations of the different way to distribute n indistinguishable 
balls into k distinguishable boxes". Let take an example: 2 balls in 3 
boxes:
Box1 Box2 Box3
2       0       0
1       1       0
1       0       1
0       2       0
0       1       1
0       0       2

I have made a script (see script below) using expand.grid but it 
generates huge number of unnecessary solutions that I must filter. And 
when the number of balls or box is large, the size of the dataframe can 
be huge.

Has someone a solution for this problem ?

Thanks a lot

(I don't play with balls and box... it is a way to manage uncertainty. I 
know that 2 events have occured during a period of 3 days but I don't 
know when exactly)

Marc




Nballs<-2
nbbox<-3


# The number of different ways to distribute n indistinguishable balls
# into k distinguishable boxes is C(n+k-1,k-1).
# nb<-choose(Nballs+nbbox-1,nbbox-1)=dim(tb)[1]

if (Nballs==0) {
tb<-as.data.frame(matrix(rep(0, nbbox), ncol=nbbox))

} else {

es<-list(0:(Nballs-1))
es<-rep(es, nbbox)

tb<-expand.grid(es)
tb<-tb[apply(tb, 1, sum)==Nballs,1:nbbox]

# trick to have smaller tb after expand.grid
tbfull<- as.data.frame(matrix(rep(0, nbbox*nbbox), ncol=nbbox, 
dimnames=list(NULL, names(tb))))
for(i in 1:nbbox) {tbfull[i, i]<-Nballs}

tb<-rbind(tb, tbfull)

}

Result:

 > tb
    Var1 Var2 Var3
4     1    1    0
6     1    0    1
7     0    1    1
41    2    0    0
5     0    2    0
61    0    0    2

-- 
__________________________________________________________
Marc Girondot, Pr

Laboratoire Ecologie, Systématique et Evolution
Equipe de Conservation des Populations et des Communautés
CNRS, AgroParisTech et Université Paris-Sud 11 , UMR 8079
Bâtiment 362
91405 Orsay Cedex, France

Tel:  33 1 (0)1.69.15.72.30   Fax: 33 1 (0)1.69.15.73.53
e-mail: marc.girondot at u-psud.fr
Web: http://www.ese.u-psud.fr/epc/conservation/Marc.html
Skype: girondot