Generating all distributions of objects to bins
Muhammad Abdullah Adnan, Md. Saidur Rahman · International Journal of Computer Mathematics · 2008
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.