53
Views
1
CrossRef citations to date
0
Altmetric
Original Articles

Distribution of distinguishable objects to bins: generating all distributions

&
Pages 953-965 | Received 04 Oct 2006, Accepted 07 Feb 2007, Published online: 01 Aug 2007
 

Abstract

In this paper we give an algorithm to generate all distributions of distinguishable objects to bins without repetition. Our algorithm generates each distribution in constant time. To the best of our knowledge, our algorithm is the first algorithm which generates each solution in O(1) time in the ordinary sense. As a byproduct of our algorithm, we obtain a new algorithm to enumerate all multiset partitions when the number of partitions is fixed and the partitions are numbered. In this case, the algorithm generates each multiset partitions in constant time (in the ordinary sense). Finally, we extend the algorithm to the case when the bins have priorities associated with them. Overall space complexity of the algorithm is O(mklgn), where there are m bins and the objects fall into k different classes. In a companion paper, the generation of all distributions of identical objects to bins is also considered.

Acknowledgements

We wish to thank the two anonymous referees for their valuable comments and suggestions for improving the presentation of the paper and for correcting the space complexity and .

Additional information

Notes on contributors

Md. Saidur Rahman

Email: [email protected]

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.