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

已有的分球入盒问题解法通常只关注分球的总方案数,目前尚没有公开的计算机算法来枚举出所有具体的分球方案,而方案的枚举是生物信息学中一些分区优化算法的基础。受第二类Stirling数的递推公式的启发,提出一个新的数据结构——Stirling图。在此基础上设计一个算法来枚举p个不同球分配到q个相同盒子里的所有不同的方案。当p和q较大,枚举出所有的方案不可行时,设计另一个算法在整个方案空间实现均匀采样,输出指定个数的方案。测试结果表明,这些算法在内存为8 GB的普通PC上可在合理的时间内枚举出上百万组不同的方案。