RESEARCH ON DISTRIBUTING BALLS INTO BOXES ENUMERATION ALGORITHM
The existing researches on the problem of distributing balls into boxes usually focus on the total number of different ways to distribute balls into boxes,but there are no public computer algorithms to enumerate them.However,enumerating them is the foundation to design some partition optimal algorithms in Bioinformatics.Inspired by the recursive formula of the Stifling numbers of the second kind,the paper proposes a new data structure-Stirling diagram,and based on the data structure,designs an algorithm to enumerate all different ways to distribute p different balls into q same boxes.When p and q are larger and none of the schemes is feasible,we design another algorithm to achieve uniform sampling of a given number of different ways.Test results show that these algorithms can enumerate millions of different distributing ways in a reasonable period of time on a PC with 8 GB memory.
Distributing balls into boxes problemStirling numbers of the second kindEnumerating algorithmStirling diagramUniform sampling
国家科技期刊平台
NSTL
万方数据
维普
