0
$\begingroup$

I have a generator of non-decreasing sequences of numbers 0..M:

M = 9;
c = 0; //counter

for (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. 0000
2. 0001
3. 0002
...
10. 0009
11. 0011
12. 0012
...
19. 0019
20. 0022
21. 0023
...

I need to calculate ONLY the n-th element. For example:

input: n = 21
result: 0023

It takes O(M^4) iterations to calculate it

  1. How can I calculate the n-th element more efficiently? (without generating all previous elements)
  2. Is there an O(1) algorithm for this problem?
  3. If not how can we show that there is no such algorithm.

Thank you!

$\endgroup$
  • $\begingroup$ What have you tried and where did you get stuck? What is the precise output specification? (Some sequence? A particular sequence? How many values do we have to yield?) $\endgroup$ – Raphael Nov 17 '14 at 15:12
  • $\begingroup$ @Raphael thank you for your feedback that the question is unclear, I added an example to clarify it. $\endgroup$ – Alvin Nov 17 '14 at 17:05
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.