I’d like to sample from a well-defined population of superexponential size with uniform probability among the population. For example, say the population is the set of unique permutations of combinations without replacement of the integers {0, 1, ..., n-1}, where the sequence length is AT MOST n.

Valid members for n=5:

(0,1,2,3)
(0,1,2,4,3)
(1,)
()

Invalid members for n=5:

(1,3,3) # No repeated elements
(0,1,2,3,4,5)  # Only in the range [0,4]

How would you write a function sample_bounded_permutations(n) to return a random permutation in polynomial time where each valid member is equally-likely to be selected? The brute force approach of computing all population members and sampling from the list is, of course, at least factorial time.