I'm trying to randomly distribute N items over B indistinguishable bins. There are no constraints as to the capacities of the individual bins, and the items themselves are also all indistinguishable. I want my algorithm to generate distributions in a uniform manner, that is each distinct distribution has equal probability of occurring. Since the bins are indistinguishable, bin order is irrelevant and duplicates need to be accounted for. Let me explain with a small example:

If we have 3 bins and 3 items to distribute, then the following sets each only contain identical distributions:

$A = \{0|1|2, 0|2|1, 1|0|2, 1|2|0, 2|0|1, 2|1|0\}$

$B = \{3|0|0, 0|3|0, 0|0|3\}$

And if $x$ is the resulting distribution, then I want $P(x \in A) = P(x \in B)$.

I've thought about this problem for a while and found that's not trivial at all. At first, I thought that I could successively pick a random bin for each item. But this has two problems:

1. It favors distributions with many duplicates.
2. Some distinct distributions have more ways of items falling into bins which lead up to them than others. The distribution where all items fall into the same bin will be much more unlikely than the one where they are distributed perfectly even. And this problem remains even if we get rid of duplicates.

I found out that my problem can also be understood through partitions from number theory. Unfortunately, there's no known closed-form expression for the number of distinct partitions. So it seems to me that it's not feasible to find a clever encoding of distinct distributions and somehow exploit that in combination with a uniform RNG.

But I'm still curious if there's some way to achieve my goal? Or would the lack of such an expression imply that I'm trying to achieve something impossible?

The only solution I could think of is to enumerate all distributions explicitly, then sort the bins by size to filter out duplicates, and then randomly pick one of the remaining distributions. But due to memory explosion, this obviously isn't feasible for any non-toy problem size.