多重集划分快速生成算法

Fast Algorithm for Generating Multiset Partitions

通过引入两种新结构：有序搜索树和向量进制运算,设计了多重集划分和多重集k划分的有效非递归生成算法,并对算法的正确性和有效性进行了分析.算法可以在划分数的线性时间复杂度内生成所有划分,并且在平均意义下可以用常量时间由一个划分生成下一个划分.同时,该算法可用于整数拆分、普通集合划分以及其它组合生成问题。

Effective Generation of multiset partitions has many practical applications.The partition of multiset is cleverly translated into the unordered split of integer vector in this article.Through the introduction of two new structures,the ordered search tree and the vector-based operation,the effective generation of non-recursive algorithms for the partition of multiset and multiset k-partitions is thus developed,the correctness and validity of which is also analyzed.The said algorithm is capable of generating all multiset partitions within the linear time complexity of number partitions,and in an average sense,by use of a constant time any partition can be generated by some other partition.Also such an algorithm can find applications in solving problems of combinational generation like integer splits and set partitions.