I have a generator of non-decreasing sequences of numbers 0..M:M = 9;c = 0; //counterfor (i1 = 0;  i1 <= M; i1++)    for (i2 = i1; i2 <= M; i2++)        for (i3 = i2; i3 <= M; i3++)            for (i4 = i3; i4 <= M; i4++)                printf(%d. %d%d%d%d, ++c, i1, i2, i3, i4);Result:1. 00002. 00013. 0002...10. 000911. 001112. 0012...19. 001920. 002221. 0023...I need to calculate ONLY the n-th element. For example:input: n = 21result: 0023It takes O(M^4) iterations to calculate itHow can I calculate the n-th element more efficiently? (without generating all previous elements)Is there an O(1) algorithm for this problem? If not how can we show that there is no such algorithm.Thank you!
n-th non-decreasing sequence
algorithms;combinatorics
This is yet another example of combinatorial enumeration. There are altogether $\binom{M+4}{4}$ different quadruples. Given $j_0$, there are $\binom{M+3-j_0}{3}$ quadruples with $i_0 = j_0$. This means that the first $\binom{M+3}{3}$ quadruples start with $0$; the following $\binom{M+2}{3}$ start with $1$; the next $\binom{M+1}{3}$ start with $2$; and so on. In this way, given a number between $1$ and $\binom{M+4}{4}$, you can find $i_0$.You then zoom in on a list of length $\binom{M+3-i_0}{3}$, and again you are given a $1$-based index to it. There are $\binom{M+2-(j_1-i_0)}{2}$ quadruples with $i_1 = j_1$. This means that the first $\binom{M+2}{2}$ quadruples start with $i_0,i_0$; the following $\binom{M+1}{2}$ with $i_0,i_0+1$; and so on. Having found $i_1$ this way, you can find $i_2$ and $i_3$ by repeating the same argument twice more.The same argument, run in reverse, can be used to calculate the index given the quadruple.  Assuming binomial coefficients can be calculated in constant time and that integer arithmetic is constant time, this algorithm runs in time $O(4\cdot M)$, or $O(4\cdot\log M)$ with $O(4\cdot M)$ preprocessing (for fixed $M$). I'm including the $4$ since if you had $t$-tuples instead of quadruples, you could replace it with $t$.