一种基于Stirling图枚举算法的分球入盒问题求解

摘要

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图.在此基础上设计一个算法来枚举p个不同球分配到g个相同盒子里的所有不同的方案.当p和q较大,枚举出所有的方案不可行时,设计另一个算法在整个方案空间实现均匀采样,输出指定个数的方案.测试结果表明,这些算法在内存为8 GB的普通PC上可在合理的时间内枚举出上百万组不同的方案.