<p>Just omit the last digit.</p>

<p>(Extra text to get over the 30-chaacter minimum.)</p>

CC BY-SA 3.0
2012-01-16T01:21:59.123Z
But if your typical data looks like {"1000002000101000", "100000100000010001001"}, merely encoding it as {"100000200010100", "10000010000001000100"} does not seem to be the most efficient approach. I thing the approach outlined by @ctgPi sounds good, as it actually exploits sparsity.
Jukka Suomela
CC BY-SA 3.0
2012-01-16T08:19:25.867Z
Yeah, but the only assumption he gave about his input numbers is that they all have the same digit sum.  I assumed that was the point of the question.  The more general question "How do I encode integers?" would be out of scope as too vague.
Jeffε
CC BY-SA 3.0
2012-01-14T19:54:26.337Z
2012-01-14T19:54:26.337Z
Jeffε
<p>What about writing each number as a sum of powers of 10 (or whatever is the base for your problem) in ascending order and then delta-encode the exponents with some <a href="http://en.wikipedia.org/wiki/Universal_code_%28data_compression%29" rel="nofollow">universal code</a>? You might need to nudge the deltas since most codes start with '1', but if you use e.g. <a href="http://en.wikipedia.org/wiki/Universal_code_%28data_compression%29" rel="nofollow">Levenstein coding</a> to encode 122:</p>

<p>122 = 10^0 + 10^0 + 10^1 + 10^1 + 10^2</p>

<p>The exponent tuple is (0, 0, 1, 1, 2), and the deltas (pretend there's an extra 0 at the beginning of the sequence) are (0, 0, 1, 0, 1), so this encodes as "0010010" binary. You might want to encode somewhere (beginning of the sequence?) what are the base and sum of the digits, though.</p>

<p>This has a minor inefficiency in that you will never see nine consecutive zero deltas. If you're that desperate for space, you can stipulate that if a zero delta would cause a digit overflow, one is subtracted from it during encoding (and added to it during decoding). For instance, 19 would be encoded as (0 * 9, 0), not (0 * 9, 1). </p>

CC BY-SA 3.0
2012-01-14T18:47:50.527Z
2012-01-14T18:47:50.527Z
ctgPi
<p>Simple idea, but fits problem statement. I propose following encoding:</p>

<p>Pair of integers: $(S, N)$</p>

<p>Where</p>

<ul>
<li>$S$ - desired sum</li>
<li>$N$ - place of number in sorted sequence of all possible positive integers with desired sum of digits.</li>
</ul>

<p>For your example sequence of integers with sum=5 :</p>

<pre><code>(5,1) = 5
(5,2) = 14
(5,3) = 23
(5,4) = 32
(5,5) = 41
(5,6) = 50
(5,7) = 105
(5,8) = 114
...
</code></pre>

<p>As you stated, that complexity is not important, you can even enumerate all integers and count those fitting given sum, once you find n-th you are done.
Of course it's brute-force approach, just as proof of concept of encoding. For sure you can make searching for "n-th" number much more efficient (but as it is not part of your question and complexity is not important, I will not elaborate).</p>

<p>To be more specific, you might ask: "<em>Pair of integers</em> - how to encode those integers?"</p>

<p>You can choose integer encoding as you like. Examples: Fixed length 64bit, Prefix code generated with <a href="http://en.wikipedia.org/wiki/Huffman_coding" rel="nofollow">Huffman encoding</a>, etc.</p>

<p>P.S. I assumed from your example sequence, you mean numbers greater than zero.</p>

CC BY-SA 3.0
2012-01-16T14:05:09.643Z
This is actually the implementation I'm using right now. I just had the feeling that this could be done smarter.
Allan
CC BY-SA 3.0
2012-01-14T18:11:46.633Z
2012-01-14T18:11:46.633Z
Grzegorz Wierzowiecki
<p>Let's say you are dealing with numbers in base $b$ with up to $n$ digits whose digit values sum to $M$. To encode a number $N$ of length $l = \lfloor \log_b  N \rfloor + 1 \leq n$, just create a bit vector of length $\log n + (M - 1)\log l$. </p>

<p>The first $\log n$ bits of the vector tell you how many digits $N$ has. The second $l$ bits tell you the position $p$ (from the right) of the first not-zero bit. The subsequent $M - 2$ blocks of $log l$ bits tell you offsets $d_i$ for $1 \leq i \leq M - 2$. You use these offsets to reconstruct the number quickly, as:</p>

<p>$$
N = b^{l - 1} + b^{p} + \sum_{1 \leq i \leq M - 2} b^{p + \sum_{1 \leq j \leq i} d_i}
$$</p>

CC BY-SA 3.0
2012-01-19T07:19:31.403Z
There is something strange about that displayed formula as it is adding only powerr of $b$. I expected to see the digits someplace. For example, why is the leading digit always 1? But otherwise, this might even be optimal.
Andrej Bauer
CC BY-SA 3.0
2012-01-18T01:25:56.940Z
2012-01-18T01:25:56.940Z
Artem Kaznatcheev
<p>$X = \{\{0,5\}, \{1,4\}, \{1,1,3\}, \{1,1,1,2\}, \{1,1,1,1,1\}, \{2,3\}, \{2,2,1\} \}$</p>

<p>$X$ is partition of 5 where only single digit numbers are allowed.</p>

<p><strong>Observation:</strong><br>
Any number with digit sum 5 can be represented by permutation of one of the above sets stuffed with 0s. </p>

<p><strong>Example:</strong></p>

<p>$\begin{eqnarray*}
14 \rightarrow 10^040^0 \rightarrow 14:0,0\\
104 \rightarrow 10^{1}40^0  \rightarrow 14:1,0\\
10000000000004 \rightarrow 10^{12}40^0 \rightarrow 14:12,0\\
100040000000000000000 \rightarrow 10^{3}40^{16} \rightarrow 14:3,16 

\end{eqnarray*}$</p>

<p>All these four numbers can be stored in a dictionary with 14 as key and list of number of zeros to stuff between each non-zero digits. </p>

<pre><code>{
14: [
      [0,0],
      [1,0],
      [12,0],
      [3,16]
    ]
}
</code></pre>

<p><strong>Space savings:</strong></p>

<p>$log_{10}$ roughly computes length of a number in base 10. If you store a number N, as a string then $L \approx \log_{10}N$ bytes are required (assuming 1 byte per char). </p>

<p>But if we use representation of numbers given above then approximate number of bytes needed are $\approx \log_{10}L$. Reason for this is lots of zeros in the number. </p>

<p>$$space  \ savings \approx 1 - \frac{log_{10} \ L}{L} = 1-\frac{log_{10}\ log_{10} \ N}{log_{10}\ N}$$</p>

<p><strong>Python Code:</strong></p>

<pre><code>d = {} 
def insert(n):
        key, xs = '', []
        for x in n:
                if x is not '0':
                        key += x
                        xs += [0]
                else:
                        xs[-1] += 1

        if not key in d.keys():
                d[key] = []
        d[key] += [xs]
</code></pre>

CC BY-SA 3.0
2012-01-18T08:55:12.187Z
2012-01-18T10:48:22.363Z
2012-01-18T10:48:22.363Z
Pratik Deoghare
<p><strong>LAST EDIT:</strong> just a refinement of the previous answer.</p>

<p>Suppose you have $n$ numbers, the digits must sum to $k$.</p>

<p>First enumerate the permutations of the digits that sum to $k$, merged with the  combinations of non-empty 0 subsequences; for example, if $k=5$:</p>

<pre><code> 0: 5      1: 5z
 2: 23     3: 23z     4: 2z3    5: 2z3z
 6: 32     7: 32z     8: 3z2    9: 3z2z
 ...
 __: 11111  __: 11111z ......   ___: 1z1z1z1z1z

 (z means: non-empty zero sequence)
</code></pre>

<p>We can represent a single number $v$, with the corresponding index $I(v)$ in the above enumeration plus the lengths of the non-empty interleaving 0 sequences.</p>

<p>For example:</p>

<pre><code>v = 2 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 0 0
      +-seq1--+   +seq2-+   +--seq3-----+
       |seq1|=5   |seq2|=4    |seq3|=7
I(v) = 2z1z2z
v can be represented with (2z1z2z,(5,4,7))
( "2z1z2z" should be replaced with the entry number of 2z1z2z in the permutation table)
</code></pre>

<p>We can group the $n$ values $v_i$ of the set according to $I({v_i})$.</p>

<pre><code>set: [ 2300, 10112, 100112, 2003000, 2000300000 ]

representation: [ 23z:[[2]], 1z112:[[1],[2]], 2z3z:[[2,3],[3,5] ]
</code></pre>

<p>We can gain more space if we add a lookup-table of the most frequent 0 (non contiguous) subsequences ( 0_0, 0_0_0, ...):</p>

<pre><code>set: [ 2300, 100112, 100110002,  2003000, 2000300000, 3000200000 ]

representation:
zero-sequences-table: [ h1:[2,3], h2:[3,5] ]
encoded-set: [23:[2], 1z112:[2,h1], 2z3z:[h1,h2], 3z2z:[h2]]
</code></pre>

<p>Note:</p>

<ul>
<li>the numbers with few digits should be left unencoded;</li>
<li>as noted by Pratik both the permutation table and the zero-sequences-table can be generated dinamically;</li>
</ul>

CC BY-SA 3.0
2012-01-18T12:32:16.420Z
There is no need to enumerate permutations beforehand. You can add permutations to the list as and when you encounter a new one.
Pratik Deoghare
CC BY-SA 3.0
2012-01-18T19:03:56.750Z
@Pratik: yes, the permutations can be generated dinamically.
Marzio De Biasi
CC BY-SA 3.0
2012-01-18T12:18:06.257Z
2012-01-18T19:17:18.040Z
2012-01-18T19:17:18.040Z
Marzio De Biasi
<p>How can a large set of integers all with a known constant digit sum be encoded?</p>

<p>Example of integers in base 10, with digit sum 5:</p>

<pre><code>14, 41, 104, 113, 122, 131, 140, 203 ....
</code></pre>

<p>The most important factor is space, but computing time is not completely unimportant.</p>

CC BY-SA 3.0
2012-01-14T13:16:21.517Z
What do you want to do with the encoded data?  Also, if the computation time is really completely irrelevant, then there is no need to store any data: you can recompute everything when you need the data instead of accessing the stored data.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-14T13:54:02.117Z
What I want to do with the data is a long story, but not relevant for this. To day I use a B-tree map to associate a given integer (with const. digit sum) to a sequence number, and the map is then used for decoding. I just thought that this could be done smarter.
Allan
CC BY-SA 3.0
2012-01-14T14:20:11.867Z
As I said, which operations you want to perform with the data is the integral part of your question.  I voted to close as not a real question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-14T16:30:40.737Z
@TsuyoshiIto: OP writes "computing time is not completely unimportant". And I think the idea here is that we have an arbitrary *subset* $X$ of integers with a constant digit sum, and hence *some* storage is needed. In general, I think this is a reasonably good question. In base 2 the question is very closely related to the efficient storage of sparse vectors.
Jukka Suomela
CC BY-SA 3.0
2012-01-15T03:27:21.667Z
Do we know how sparse the set is?  That is, compared to using every possible number that fits the description, do we have an idea what percent or ratio of these numbers we'll be encoding?  Also, do we have an idea of the size of the digit sum we're talking about?  Is it more like 10 or more like a million?
Matt Groff
CC BY-SA 3.0
2012-01-15T17:51:00.413Z
Is sum modulo 10 allowed ? (e.g. 96 -> 9+6 = 15, 15 mod 10 = 5) If it is not allowed, then every number has obviously max 5 non-zero digits.
Marzio De Biasi
CC BY-SA 3.0
2012-01-15T23:12:09.493Z
I had been completely misunderstanding the question.  My apologies.  And thanks to @Jukka for letting me realize it.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-15T23:14:54.670Z
@Matt: There are infinitely many integers with a fixed sum of digits (e.g. 5, 50, 500, 5000, …), so you cannot define the ratio without an upper bound on, say, the number of digits.  This may be a nitpicking, but I had overlooked it before.
Tsuyoshi Ito
<encoding>
Efficient encoding of integers with constant digit sum
Allan
# Efficient encoding of integers with constant digit sum

(Asked by: username_0 on 2012-01-14)

How can a large set of integers all with a known constant digit sum be encoded?
Example of integers in base 10, with digit sum 5:
14, 41, 104, 113, 122, 131, 140, 203 ....

The most important factor is space, but computing time is not completely unimportant.

**Tags:** encoding
> **Comments:**
> **username_1**: What do you want to do with the encoded data?  Also, if the computation time is really completely irrelevant, then there is no need to store any data: you can recompute everything when you need the data instead of accessing the stored data.  
> **username_0**: What I want to do with the data is a long story, but not relevant for this. To day I use a B-tree map to associate a given integer (with const. digit sum) to a sequence number, and the map is then used for decoding. I just thought that this could be done smarter.  
> **username_1**: As I said, which operations you want to perform with the data is the integral part of your question.  I voted to close as not a real question.  
> **username_2**: @TsuyoshiIto: OP writes "computing time is not completely unimportant". And I think the idea here is that we have an arbitrary *subset* $X$ of integers with a constant digit sum, and hence *some* storage is needed. In general, I think this is a reasonably good question. In base 2 the question is very closely related to the efficient storage of sparse vectors.  
> **username_3**: Do we know how sparse the set is?  That is, compared to using every possible number that fits the description, do we have an idea what percent or ratio of these numbers we'll be encoding?  Also, do we have an idea of the size of the digit sum we're talking about?  Is it more like 10 or more like a million?  
> **username_4**: Is sum modulo 10 allowed ? (e.g. 96 -> 9+6 = 15, 15 mod 10 = 5) If it is not allowed, then every number has obviously max 5 non-zero digits.  
> **username_1**: I had been completely misunderstanding the question.  My apologies.  And thanks to @Jukka for letting me realize it.  
> **username_1**: @Matt: There are infinitely many integers with a fixed sum of digits (e.g. 5, 50, 500, 5000, …), so you cannot define the ratio without an upper bound on, say, the number of digits.  This may be a nitpicking, but I had overlooked it before.  

---

## 6 answers

### Answer by username_5 on 2012-01-14. Score: 7

Just omit the last digit.

(Extra text to get over the 30-chaacter minimum.)

> **Comments:**
> **username_2**: But if your typical data looks like {"1000002000101000", "100000100000010001001"}, merely encoding it as {"100000200010100", "10000010000001000100"} does not seem to be the most efficient approach. I thing the approach outlined by @ctgPi sounds good, as it actually exploits sparsity.  
> **username_5**: Yeah, but the only assumption he gave about his input numbers is that they all have the same digit sum.  I assumed that was the point of the question.  The more general question "How do I encode integers?" would be out of scope as too vague.  

---

### Answer by username_6 on 2012-01-14. Score: 4

What about writing each number as a sum of powers of 10 (or whatever is the base for your problem) in ascending order and then delta-encode the exponents with some [universal code](http://en.wikipedia.org/wiki/Universal_code_%28data_compression%29)? You might need to nudge the deltas since most codes start with '1', but if you use e.g. [Levenstein coding](http://en.wikipedia.org/wiki/Universal_code_%28data_compression%29) to encode 122:

122 = 10^0 + 10^0 + 10^1 + 10^1 + 10^2

The exponent tuple is (0, 0, 1, 1, 2), and the deltas (pretend there's an extra 0 at the beginning of the sequence) are (0, 0, 1, 0, 1), so this encodes as "0010010" binary. You might want to encode somewhere (beginning of the sequence?) what are the base and sum of the digits, though.

This has a minor inefficiency in that you will never see nine consecutive zero deltas. If you're that desperate for space, you can stipulate that if a zero delta would cause a digit overflow, one is subtracted from it during encoding (and added to it during decoding). For instance, 19 would be encoded as (0 \* 9, 0), not (0 \* 9, 1).


---

### Answer by username_7 on 2012-01-14. Score: 2

Simple idea, but fits problem statement. I propose following encoding:
Pair of integers: $(S, N)$
Where

$S$ - desired sum
$N$ - place of number in sorted sequence of all possible positive integers with desired sum of digits.

For your example sequence of integers with sum=5 :
(5,1) = 5
(5,2) = 14
(5,3) = 23
(5,4) = 32
(5,5) = 41
(5,6) = 50
(5,7) = 105
(5,8) = 114
...

As you stated, that complexity is not important, you can even enumerate all integers and count those fitting given sum, once you find n-th you are done.
Of course it's brute-force approach, just as proof of concept of encoding. For sure you can make searching for "n-th" number much more efficient (but as it is not part of your question and complexity is not important, I will not elaborate).
To be more specific, you might ask: "Pair of integers - how to encode those integers?"
You can choose integer encoding as you like. Examples: Fixed length 64bit, Prefix code generated with Huffman encoding, etc.
P.S. I assumed from your example sequence, you mean numbers greater than zero.

> **Comments:**
> **username_0**: This is actually the implementation I'm using right now. I just had the feeling that this could be done smarter.  

---

### Answer by username_8 on 2012-01-18. Score: 1

Let's say you are dealing with numbers in base $b$ with up to $n$ digits whose digit values sum to $M$. To encode a number $N$ of length $l = \lfloor \log\_b N \rfloor + 1 \leq n$, just create a bit vector of length $\log n + (M - 1)\log l$.

The first $\log n$ bits of the vector tell you how many digits $N$ has. The second $l$ bits tell you the position $p$ (from the right) of the first not-zero bit. The subsequent $M - 2$ blocks of $log l$ bits tell you offsets $d\_i$ for $1 \leq i \leq M - 2$. You use these offsets to reconstruct the number quickly, as:

$$
N = b^{l - 1} + b^{p} + \sum\_{1 \leq i \leq M - 2} b^{p + \sum\_{1 \leq j \leq i} d\_i}
$$

> **Comments:**
> **username_9**: There is something strange about that displayed formula as it is adding only powerr of $b$. I expected to see the digits someplace. For example, why is the leading digit always 1? But otherwise, this might even be optimal.  

---

### Answer by username_10 on 2012-01-18. Score: 1

$X = \{\{0,5\}, \{1,4\}, \{1,1,3\}, \{1,1,1,2\}, \{1,1,1,1,1\}, \{2,3\}, \{2,2,1\} \}$
$X$ is partition of 5 where only single digit numbers are allowed.
Observation:
Any number with digit sum 5 can be represented by permutation of one of the above sets stuffed with 0s. 
Example:
$\begin{eqnarray*}
14 \rightarrow 10^040^0 \rightarrow 14:0,0\\
104 \rightarrow 10^{1}40^0  \rightarrow 14:1,0\\
10000000000004 \rightarrow 10^{12}40^0 \rightarrow 14:12,0\\
100040000000000000000 \rightarrow 10^{3}40^{16} \rightarrow 14:3,16 

\end{eqnarray*}$
All these four numbers can be stored in a dictionary with 14 as key and list of number of zeros to stuff between each non-zero digits. 
{
14: [
      [0,0],
      [1,0],
      [12,0],
      [3,16]
    ]
}

Space savings:
$log_{10}$ roughly computes length of a number in base 10. If you store a number N, as a string then $L \approx \log_{10}N$ bytes are required (assuming 1 byte per char). 
But if we use representation of numbers given above then approximate number of bytes needed are $\approx \log_{10}L$. Reason for this is lots of zeros in the number. 
$$space  \ savings \approx 1 - \frac{log_{10} \ L}{L} = 1-\frac{log_{10}\ log_{10} \ N}{log_{10}\ N}$$
Python Code:
d = {} 
def insert(n):
        key, xs = '', []
        for x in n:
                if x is not '0':
                        key += x
                        xs += [0]
                else:
                        xs[-1] += 1

        if not key in d.keys():
                d[key] = []
        d[key] += [xs]


---

### Answer by username_4 on 2012-01-18. Score: 0

LAST EDIT: just a refinement of the previous answer.
Suppose you have $n$ numbers, the digits must sum to $k$.
First enumerate the permutations of the digits that sum to $k$, merged with the  combinations of non-empty 0 subsequences; for example, if $k=5$:
 0: 5      1: 5z
 2: 23     3: 23z     4: 2z3    5: 2z3z
 6: 32     7: 32z     8: 3z2    9: 3z2z
 ...
 __: 11111  __: 11111z ......   ___: 1z1z1z1z1z

 (z means: non-empty zero sequence)

We can represent a single number $v$, with the corresponding index $I(v)$ in the above enumeration plus the lengths of the non-empty interleaving 0 sequences.
For example:
v = 2 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 0 0
      +-seq1--+   +seq2-+   +--seq3-----+
       |seq1|=5   |seq2|=4    |seq3|=7
I(v) = 2z1z2z
v can be represented with (2z1z2z,(5,4,7))
( "2z1z2z" should be replaced with the entry number of 2z1z2z in the permutation table)

We can group the $n$ values $v_i$ of the set according to $I({v_i})$.
set: [ 2300, 10112, 100112, 2003000, 2000300000 ]

representation: [ 23z:[[2]], 1z112:[[1],[2]], 2z3z:[[2,3],[3,5] ]

We can gain more space if we add a lookup-table of the most frequent 0 (non contiguous) subsequences ( 0_0, 0_0_0, ...):
set: [ 2300, 100112, 100110002,  2003000, 2000300000, 3000200000 ]

representation:
zero-sequences-table: [ h1:[2,3], h2:[3,5] ]
encoded-set: [23:[2], 1z112:[2,h1], 2z3z:[h1,h2], 3z2z:[h2]]

Note:

the numbers with few digits should be left unencoded;
as noted by Pratik both the permutation table and the zero-sequences-table can be generated dinamically;

> **Comments:**
> **username_10**: There is no need to enumerate permutations beforehand. You can add permutations to the list as and when you encounter a new one.  
> **username_4**: @Pratik: yes, the permutations can be generated dinamically.  

---

