0
$\begingroup$

How to encode a sequence of n non-decreasing integer of [0, ..., m] fulfilling the following conditions:

  1. no or minimal redundancy
  2. only use 1 integer variable or k independent integer variables with a range of [0, ..., j(k)], It means there exist an inverse function f-1(x) to map the encoded sequence, an integer x of the domain [0, 1, ..., |valid sequence| - 1], back the original sequence.
  3. usual integer operations
  4. no or minimal lookup tables
  5. closed form formula to decode back to the sequence without loops or recursions

For example,

0, 0, 0, 0
0, 0, 0, 1
0, 0, 0, 2
...
0, 0, 0, m
0, 0, 1, 1
0, 0, 1, 2
...
m, m, m, m

The purpose of this counting function is to enumerate all possible values in the non-decreasing integer sequence later being used in constraints.

$\endgroup$
  • $\begingroup$ What do you mean by "only use 1 integer variable"? Also if you want to insist on no loops and no recursion, that needs to be in the question, rather than in a comment to an answer, so I encourage you to edit the question to clarify your requirements. $\endgroup$ – D.W. Jun 14 '17 at 1:23
3
$\begingroup$

Let $\mathcal{C}(n,m)$ denote the set of sequences you are interested in, namely non-decreasing sequences of length $n$ consisting of integers from $\{0,\ldots,m\}$, and let $C(n,m) = |\mathcal C(n,m)|$ be the number of such sequences. It is not hard to verify the following recursion: $$ \begin{align*} &C(0,m) = 1, \\ &C(n,m) = \sum_{k=0}^m C(n-1,k) \text{ for } n > 0. \end{align*} $$ In fact, it is not hard to check that $$ C(n,m) = \binom{n+m}{m}. $$ But the recursion allows us to rank and unrank sequences. More explicitly, we will now describe a bijection $r_{n,m}$ from $\mathcal C(n,m)$ to $[0,C(n,m))$ (i.e., $\{0,\ldots,C(n,m)-1\}$). The bijection is defined recursively as follows (below, $\lambda$ is the empty sequence): $$ \begin{align*} &r_{0,m}(\lambda) = 0, \\ &r_{n,m}(\sigma_1,\ldots,\sigma_n) = \sum_{k < \sigma_n} C(n-1,k) + r_{n-1,\sigma_n}(\sigma_1,\ldots,\sigma_{n-1}). \end{align*} $$ This doesn't order the sequences in the order you listed, though one can easily adapt it to your order (by considering the first rather than last element). We can also describe the inverse bijection explicitly: $$ \begin{align*} &r^{-1}_{0,m}(0) = \lambda, \\ &r^{-1}_{n,m}(r) = r^{-1}_{n-1,k}\left(r - \sum_{\ell<k} C(n-1,\ell)\right),k, \\ &\qquad \text{ where $k$ is defined by } \sum_{\ell < k} C(n-1,\ell) \leq r < \sum_{\ell \leq k} C(n-1,\ell). \end{align*} $$

Finally, if all you want is to list the sequences in order, say the order in your post, then you can use the following simple "counter" algorithm. Start with the all-zero sequence $\sigma_1 = \cdots = \sigma_n = 0$. At each step, find the maximal $i$ such that $\sigma_i < m$ (if $\sigma_1 = \cdots = \sigma_n = m$, we are done). Increase $\sigma_i$, and set all numbers following it to its new value. This will enumerate all sequences in lexicographic order, in amortized time $O(1)$ per sequence.

$\endgroup$
  • $\begingroup$ Sorry for not being clear in the question. Loops and recursions are not allowed. Is it possible to unroll the sum in the inverse function? $\endgroup$ – keithyip Jun 10 '17 at 2:28
  • $\begingroup$ That's a question you'll have to answer on your own. $\endgroup$ – Yuval Filmus Jun 10 '17 at 6:52
  • 2
    $\begingroup$ Without loops or recursion you will only be able to handle constant $n,m$. $\endgroup$ – Yuval Filmus Jun 10 '17 at 7:29
  • $\begingroup$ it is possible to make an index to pattern extraction, to enumerate all of them. in short it is a modified Radix calculation, where each extraction affects the range of the next Radix extractions ... and now I see that is what Yuval Filmus was eluding to. enumeration/extraction for each entry is O(1) $\endgroup$ – Phillip Williams Jun 15 '17 at 15:41

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.