Generating all distributions of objects to bins

Abstract

In this paper, we give an elegant algorithm to generate all distributions of n identical objects to m bins without repetition. The best known previous algorithm, due to Klingsberg, generates each distribution in constant time in average sense. Using a new technique of efficient tree traversal, in this paper we improve the time complexity to constant time (in ordinary sense). By modifying our algorithm, we can generate the distributions in anti-lexicographic order. Overall space complexity of our algorithm is O(mlgn), where m is the number of bins and n is the number of objects.

Keywords:

• combinatorial objects
• algorithm
• generating problems
• integer partitions
• set partitions

2000 AMS Subject Classifications :

• 05A15
• 05A17
• 05A18

Acknowledgements

We wish to thank the two anonymous referees for their valuable comments and suggestions for improving the presentation of the paper. We thank Shin-ichi Nakano for encouraging us to work in this area and for giving us valuable comments on the manuscript of the paper. We also thank Shin-ichiro Kawano for helpful discussions.