Fast Algorithm for Generating Multiset Partitions
Mou Lian-ming · Journal of Neijiang Normal University · 2010
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.