计算机应用与软件2017，Vol.34Issue(10)：248-251,274,5.DOI:10.3969/j.issn.1000-386x.2017.10.044
一种基于Stirling图枚举算法的分球入盒问题求解
RESEARCH ON DISTRIBUTING BALLS INTO BOXES ENUMERATION ALGORITHM
摘要
Abstract
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.关键词
分球入盒问题/第二类Stirling数/枚举算法/Stirling图/均匀采样Key words
Distributing balls into boxes problem/Stirling numbers of the second kind/Enumerating algorithm/Stirling diagram/Uniform sampling分类
信息技术与安全科学引用本文复制引用
彭哲也,谢民主..一种基于Stirling图枚举算法的分球入盒问题求解[J].计算机应用与软件,2017,34(10):248-251,274,5.基金项目
国家自然科学基金项目(61370172) （61370172）
