<p>Answer to question 1: $\left\lceil \log_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode the variables.</p>

<p>Proof: Count how many ways there are to choose $y_1,\ldots,y_r$ such that $y_i \ge 0$ and $\sum y_i = M-r$. There are exactly $\binom{M-1}{r-1}$ such ways (see e.g. <a href="http://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29" rel="nofollow">here</a>). Now, if there are only $k$ possible values for a variable, then $\lceil \log k \rceil$ bits suffice to encode that variable. Therefore, $opt=\left\lceil \log_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode our input.</p>

<p>Answer to question 2: This is a bit more tricky. The best approach is to check the literature on succinct rank-select or other succinct data structures: I suspect you can match the results for succinct rank-select, so to get something like $opt+o(M)$ space and $O(\log M)$ running times for all operations. If you're interested, tell me in the comments and I'll try to look it up and tell you my best guess on what's possible. You might also want to check out <a href="http://people.csail.mit.edu/mip/papers/trits/paper.pdf" rel="nofollow">Dodis-Patrascu-Thorup</a> for some ideas.</p>

CC BY-SA 3.0
2014-06-15T00:47:14.893Z
Also, R.B.: since there's a lot of literature on the topic, if you'd like me to check it for you, please say specifically which solutions you'd like over others in the tradeoff. For example, do you prefer a solution with $2M+O(\sqrt{M})$ space and $O(1)$ operation times over a solution with $2M+O(M^{1/3})$ space and $O(\sqrt{M})$ operation times? etc etc
greg
CC BY-SA 3.0
2014-06-16T21:45:01.223Z
Because $x_i \ge 1$ for all $i$, the variables can be encoded in $M$ bits. Just take binary sequence $B$ of length $M$, and set $B[k]=1$, if $\sum_{i=1}^{j} x_{i} = k$ for some $j$.
Jouni Sirén
CC BY-SA 3.0
2014-06-15T00:42:23.337Z
2014-06-17T14:43:41.917Z
2014-06-17T14:43:41.917Z
greg
<p>Assume we'd like to be able to encode variables $x_1,x_2,\cdots,x_r\in \mathbb{N}$, such that $\forall i\in[r]:1\leq x_i\leq N$ and $$\sum_{i=1}^{r}x_i=M$$</p>

<p>It's easy to store the variables using $r\log N$ bits, but this doesn't take advantage of the fact that their sum is bounded.</p>

<p>Furthermore, in my application $r$ is not fixed and could vary from $\frac{M}{N}$ to $M$, so I would need $M\log N$ bits in the worst case if I use the naive encoding.</p>

<p>So the questions are as follows:</p>

<p><strong>How many bits are required to encode the variables, given that an adversary picks the values of $r$ and $x_1,x_2,\cdots,x_r$?</strong></p>

<p><strong>Is there an data structure that uses close-to-optimal space for this that supports efficient replacement operations (where replace$(i,j)$ increases the value of $x_j$ by 1 and decrements the value of $x_i$ by 1)?</strong></p>

<hr>

<p>If it helps, you may assume $M=N$ (which is what I need for my application), but I think it's interesting for general $M,N$.</p>

CC BY-SA 3.0
2014-06-14T10:55:35.260Z
I'm not an expert, but I think that you can get a good bound if you think that with  $M,x_1,...,x_r$ you can encode an arbitrary binary string $y$ of length $|y| = \log M + \log x_1 + ... + \log x_r$; the sum constraint allows each $x_i$ to be $M/r$ so $|y|= \log M + r \log(M/r)$. If you pick $y$ incompressible, then there is no way to do better.
Marzio De Biasi
CC BY-SA 3.0
2014-06-14T11:08:34.063Z
... a little fix: $|y| = \log M + (r-1)\log(M/r)$ because the last $x_r$ must be use to "pad" the sum to $M$.
Marzio De Biasi
CC BY-SA 3.0
2014-06-14T12:58:55.443Z
@MarzioDeBiasi - As I wrote in the question, $r$ isn't fixed (I'd like to be able to perform "replace" operations). Do you mean I need $\text{max}\{\log M + (r-1)\log(\frac{M}{r}) | r\in \{\frac{M}{N},\frac{M}{N}+1,\ldots,M\}\}$ bits? Do you think of a way I could use such encoding and perform the "replacement" operations in reasonable time (say $O(\log(MN))$)?
R B
CC BY-SA 3.0
2014-06-17T12:19:07.263Z
This seems to be the same question as http://cstheory.stackexchange.com/questions/24869/minimal-encoding-of-a-set-unordered-collection-of-elements#comment61776_24869 or at least very close.
Zsbán Ambrus
CC BY-SA 3.0
2014-06-17T13:40:04.347Z
@ZsbánAmbrus - it's related but not the same. In the other question I was wondering about a arbitrary set encoding and here I'd like to encode a multi set with fixed number of total elements. While you can use the solution there over here, it'll be inefficient.
R B
<ds.algorithms><ds.data-structures><space-bounded><encoding>
Number of bits required for encoding variables with fixed sum?
R B
# Number of bits required for encoding variables with fixed sum?

(Asked by: username_0 on 2014-06-14)

Assume we'd like to be able to encode variables $x\_1,x\_2,\cdots,x\_r\in \mathbb{N}$, such that $\forall i\in[r]:1\leq x\_i\leq N$ and $$\sum\_{i=1}^{r}x\_i=M$$

It's easy to store the variables using $r\log N$ bits, but this doesn't take advantage of the fact that their sum is bounded.

Furthermore, in my application $r$ is not fixed and could vary from $\frac{M}{N}$ to $M$, so I would need $M\log N$ bits in the worst case if I use the naive encoding.

So the questions are as follows:

**How many bits are required to encode the variables, given that an adversary picks the values of $r$ and $x\_1,x\_2,\cdots,x\_r$?**

**Is there an data structure that uses close-to-optimal space for this that supports efficient replacement operations (where replace$(i,j)$ increases the value of $x\_j$ by 1 and decrements the value of $x\_i$ by 1)?**

---

If it helps, you may assume $M=N$ (which is what I need for my application), but I think it's interesting for general $M,N$.

**Tags:** ds.algorithms, ds.data-structures, space-bounded, encoding
> **Comments:**
> **username_1**: I'm not an expert, but I think that you can get a good bound if you think that with  $M,x_1,...,x_r$ you can encode an arbitrary binary string $y$ of length $|y| = \log M + \log x_1 + ... + \log x_r$; the sum constraint allows each $x_i$ to be $M/r$ so $|y|= \log M + r \log(M/r)$. If you pick $y$ incompressible, then there is no way to do better.  
> **username_1**: ... a little fix: $|y| = \log M + (r-1)\log(M/r)$ because the last $x_r$ must be use to "pad" the sum to $M$.  
> **username_0**: @MarzioDeBiasi - As I wrote in the question, $r$ isn't fixed (I'd like to be able to perform "replace" operations). Do you mean I need $\text{max}\{\log M + (r-1)\log(\frac{M}{r}) | r\in \{\frac{M}{N},\frac{M}{N}+1,\ldots,M\}\}$ bits? Do you think of a way I could use such encoding and perform the "replacement" operations in reasonable time (say $O(\log(MN))$)?  
> **username_2**: This seems to be the same question as http://cstheory.stackexchange.com/questions/24869/minimal-encoding-of-a-set-unordered-collection-of-elements#comment61776_24869 or at least very close.  
> **username_0**: @ZsbánAmbrus - it's related but not the same. In the other question I was wondering about a arbitrary set encoding and here I'd like to encode a multi set with fixed number of total elements. While you can use the solution there over here, it'll be inefficient.  

---

## 1 answers

### Answer by username_3 on 2014-06-15. Score: 4

Answer to question 1: $\left\lceil \log\_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode the variables.

Proof: Count how many ways there are to choose $y\_1,\ldots,y\_r$ such that $y\_i \ge 0$ and $\sum y\_i = M-r$. There are exactly $\binom{M-1}{r-1}$ such ways (see e.g. [here](http://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29)). Now, if there are only $k$ possible values for a variable, then $\lceil \log k \rceil$ bits suffice to encode that variable. Therefore, $opt=\left\lceil \log\_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode our input.

Answer to question 2: This is a bit more tricky. The best approach is to check the literature on succinct rank-select or other succinct data structures: I suspect you can match the results for succinct rank-select, so to get something like $opt+o(M)$ space and $O(\log M)$ running times for all operations. If you're interested, tell me in the comments and I'll try to look it up and tell you my best guess on what's possible. You might also want to check out [Dodis-Patrascu-Thorup](http://people.csail.mit.edu/mip/papers/trits/paper.pdf) for some ideas.

> **Comments:**
> **username_3**: Also, R.B.: since there's a lot of literature on the topic, if you'd like me to check it for you, please say specifically which solutions you'd like over others in the tradeoff. For example, do you prefer a solution with $2M+O(\sqrt{M})$ space and $O(1)$ operation times over a solution with $2M+O(M^{1/3})$ space and $O(\sqrt{M})$ operation times? etc etc  
> **username_4**: Because $x_i \ge 1$ for all $i$, the variables can be encoded in $M$ bits. Just take binary sequence $B$ of length $M$, and set $B[k]=1$, if $\sum_{i=1}^{j} x_{i} = k$ for some $j$.  

---

