I'd like to sample a random sorted combination with replacement.
(Ideally I'd like to do this without rejection, or otherwise in a computationally-efficient manner)
I can start by sampling a combination with replacement normally, then sort the results, but some results (ones with more unique elements) are overrepresented.
For example, choosing 2 binary items and sorting we get (0, 1) is twice as common as (0, 0).
I think this might be the same as how do I sample from random sorted combinations without replacement, and then subtracting the index from each item.
For example (0, 1, 2) would then become (0, 0, 0), and (0, 3, 4) would become (0, 2, 2), etc.
(The problem seems to be the same: how to fairly choose from sorted combinations).
Suppose we have $k$ kinds of objects and we want a uniform-probability size-$n$ sorted sample of them with replacement.
By stars and bars this is equivalent to choosing $k-1$ objects out of $n+k-1$ initially identical objects to be the bars, which then partition the remaining $n$ stars into $k$ groups which naturally associate with the object types in some predetermined sorted order. For example, if $k=4$ and $n=6$ the selection with replacement $0,0,1,1,2,3$ is equivalent to the selection without replacement $××2××\ 5×7\ ×$ (indices starting from 0).
Thus the problem reduces to sampling from sorted combinations without replacement, which you know how to do (or otherwise is easy to do with a partial Fisher–Yates shuffle and then sorting).