Generating discrete random numbers under constraints
I won't code it for you but here's the logic to do the non brute force approach:
Let's define N(i,x) the number of possible samples of X[1],...,X[i] where X[i]=x. And S(i) the possible values for X[i]. You have the recursion formula N(i,x) = Sum over y in S(i-1) with y<=x of N(i-1,y). This allows you to very quickly compute all N(i,x). It is then easy to build up your sample from the end:
Knowing all N(n,x), you can draw X[n] from S(n) with probability N(n,X[n]) / (Sum over x in S(N) of N(n,x))
And then you keep building down: given you have already drawn X[n],X[n-1],...,X[i+1] you draw X[i] from S(i) with X[i]<=X[i+1] with probability N(i,X[i]) / (Sum over x in S(i) with x<=X[i+1] of N(i,x))
I have a problem that I'm not sure how to solve properly.
Suppose we have to generate 1 <= n <= 40 numbers: X[1], X[2], ..., X[n].
For each number, we have some discrete space we can draw a number from. This space is not always a range and can be quite large (thousands/millions of numbers).
Another constraint is that the resulting array of numbers should be sorted in ascending order: X[1] <= X[2] <= ... <= X[n].
As an example for three numbers:
X[1] in {8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}
X[2] in {10, 20, 30, 50}
X[3] in {1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003}
Examples of valid outputs for this test: [9, 20, 2001], [18, 30, 1995]
Example of invalid outputs for this test: [25, 10, 1998] (not increasing order)
I already tried different methods but what I'm not satisfied with is that they all yield not uniformly distributed results, i.e. there is a strong bias in all my solutions and some samples are underrepresented.
One of the methods is to try to randomly generate numbers one by one and at each iteration reduce the space for the upcoming numbers to satisfy the increasing order condition. This is bad because this solution always biases the last numbers towards the higher end of their possible range.
I already gave up on looking for an exact solution that could yield samples uniformly. I would really appreciate any reasonable solution (preferably, on Python, but anything will do, really).