# How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions

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.

• 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. – D.W. Jun 14 '17 at 1:23

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.
• Without loops or recursion you will only be able to handle constant $n,m$. – Yuval Filmus Jun 10 '17 at 7:29