60
Views
1
CrossRef citations to date
0
Altmetric
Section A

Generating all distributions of objects to bins

&
Pages 383-392 | Received 08 Jul 2007, Accepted 08 Aug 2007, Published online: 21 Feb 2009
 

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.

2000 AMS Subject Classifications :

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.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.