<p>This is called <a href="http://en.wikipedia.org/wiki/Run-length_limited">run-length-limited coding</a>, there has been lots of research done on it by the information theory community, and I will just refer you to the existing literature. After a brief glance at the wikipedia article I linked to, my impression is that you shouldn't rely on the references it contains, but do your own search of the literature. </p>

<p>One simple thing you could do that does better than doubling the string size is: </p>

<p>(1) add a 0 to the end of the original sequence, <br>
(2) break the original sequence greedily into blocks of either 0, 10, or 11, <br>
(3) encode using the encoding</p>

<blockquote>
  <p>&thinsp;&thinsp;&thinsp;0 &rarr; ab<br>
  10 &rarr; abb<br>
  11 &rarr; abbb  </p>
</blockquote>

<p>Step (2) is always possible, since after step (1) the sequence ends with a 0. Except for step (1), which adds at most two bits to your encoded sequence, this cannot do worse than double the string size, and generally does better.</p>

<p>For example, you encode <br>
0110100101 &rarr; 0.11.0.10.0.10.10 &rarr; ababbbababbababbabb, <br>
taking 10 characters into 19. </p>

<p>If I did my calculations right, starting with $n$ random bits, this encoding gives an expected length of 11/6&thinsp;$n$ bits, which is only slightly more than the optimal value of around 1.813&thinsp;$n$ bits.</p>

CC BY-SA 3.0
2012-02-22T22:35:00.910Z
We have already proven that $1.81... \cdot n$ bit is the optimal value using recursive formula's and counting the `legal` sequences. How have you found that that is the optimal value? Are there even more effective ways than this $1.83... \cdot n$ algorithm?
Rudy
CC BY-SA 3.0
2012-02-22T22:42:45.110Z
@Rudy: I used recursive formulas and counting the legal sequences to get $1.813\, n$ as well. There are certainly even more effective ways than the $1.833 \, n$ algorithm, but I don't know whether any of them are as simple.
Peter Shor 
CC BY-SA 3.0
2012-02-27T16:58:15.007Z
@Rudy: somewhere in the literature there should be theorem giving polynomial-time algorithms for doing run-length encoding with arbitrary constraints. So, yes, you can get more effective algorithms. But I don't have time to do the literature search for you, and offhand I don't know whether any of them are as simple as the encoding I give in my answer.
Peter Shor 
CC BY-SA 3.0
2012-02-22T17:16:08.997Z
2012-02-23T01:28:28.037Z
2012-02-23T01:28:28.037Z
Peter Shor 
<p>For the problem as you've posed it, it seems that you could simply replace every occurrence of an illegal sequence by a new symbol so that: aababbbaba -> xbayaba.</p>

<p>I guess that's probably too simple, but we'll need more information to provide a better solution (like the cost of adding symbols). </p>

CC BY-SA 3.0
2012-02-22T15:56:05.463Z
No, no new symbols are allowed, only $\{a,b\}$. So there are two symbols. We need to encode (il)illegal sequences to legal ones, and we must be able to go back to the original (il)legal sequences.
Rudy
CC BY-SA 3.0
2012-02-22T16:07:15.303Z
I see what you mean now: the x's represent a or b depending on the context. I'll have another think.
Peter
CC BY-SA 3.0
2012-02-22T15:22:10.447Z
2012-02-22T15:22:10.447Z
Peter
<p>Suppose we have the following symbols: $\{a,b\}$. Now there are some rules. More than 3 $b$'s are now allowed and $aa$ is not allowed. So $ababab$ is allowed, but for example $abbbbaba$ not (more than 3 $b$'s). There is an easy way to get this working. Suppose you have a string of $n$ characters. Just add between every two numbers a new number so the string is correct. Decoding is not hard: just remove all numbers on even positions. So $abbbbaba \rightarrow axbxbxbxbxaxbxax$ and decoding is the same as just removing the $x$'s. But the problem is that the string size doubles. Is there a more efficient way to accomplish encoding and decoding? So encoding means encode all strings to valid strings and decoding means decode that string back to the original string.</p>

CC BY-SA 3.0
2012-02-22T15:53:01.857Z
Using extra symbols is kind of cheating (you can encode up to $|\Sigma|^n$ strings of length $n$ using alphabet $\Sigma$). So you can actually _compress_ a binary string using larger alphabet! Could you please make the question more accurate?
Dmytro Korduban
CC BY-SA 3.0
2012-02-22T19:10:24.767Z
@Dmytro: The *x*'s in the original question stand for either *a* or *b* ... it is not hard to show that you can always replace the *x*'s with some combination of *a*'s and *b*'s to achieve a legal string.
Peter Shor 
CC BY-SA 3.0
2012-02-22T22:31:03.943Z
Then it would be even possible to compress any random string to a string of length one (using a alphabet of unbounded size).
Rudy
<ds.algorithms><it.information-theory><encoding>
Combinations with symbols
Rudy
# Combinations with symbols

(Asked by: username_0 on 2012-02-22)

Suppose we have the following symbols: $\{a,b\}$. Now there are some rules. More than 3 $b$'s are now allowed and $aa$ is not allowed. So $ababab$ is allowed, but for example $abbbbaba$ not (more than 3 $b$'s). There is an easy way to get this working. Suppose you have a string of $n$ characters. Just add between every two numbers a new number so the string is correct. Decoding is not hard: just remove all numbers on even positions. So $abbbbaba \rightarrow axbxbxbxbxaxbxax$ and decoding is the same as just removing the $x$'s. But the problem is that the string size doubles. Is there a more efficient way to accomplish encoding and decoding? So encoding means encode all strings to valid strings and decoding means decode that string back to the original string.

**Tags:** ds.algorithms, it.information-theory, encoding
> **Comments:**
> **username_1**: Using extra symbols is kind of cheating (you can encode up to $|\Sigma|^n$ strings of length $n$ using alphabet $\Sigma$). So you can actually _compress_ a binary string using larger alphabet! Could you please make the question more accurate?  
> **username_2**: @Dmytro: The *x*'s in the original question stand for either *a* or *b* ... it is not hard to show that you can always replace the *x*'s with some combination of *a*'s and *b*'s to achieve a legal string.  
> **username_0**: Then it would be even possible to compress any random string to a string of length one (using a alphabet of unbounded size).  

---

## 2 answers

### Answer by username_2 on 2012-02-22. Score: 6 | Accepted answer

This is called [run-length-limited coding](http://en.wikipedia.org/wiki/Run-length_limited), there has been lots of research done on it by the information theory community, and I will just refer you to the existing literature. After a brief glance at the wikipedia article I linked to, my impression is that you shouldn't rely on the references it contains, but do your own search of the literature.

One simple thing you could do that does better than doubling the string size is:

(1) add a 0 to the end of the original sequence,   
(2) break the original sequence greedily into blocks of either 0, 10, or 11,   
(3) encode using the encoding

>    0 → ab  
> 10 → abb  
> 11 → abbb

Step (2) is always possible, since after step (1) the sequence ends with a 0. Except for step (1), which adds at most two bits to your encoded sequence, this cannot do worse than double the string size, and generally does better.

For example, you encode   
0110100101 → 0.11.0.10.0.10.10 → ababbbababbababbabb,   
taking 10 characters into 19.

If I did my calculations right, starting with $n$ random bits, this encoding gives an expected length of 11/6 $n$ bits, which is only slightly more than the optimal value of around 1.813 $n$ bits.

> **Comments:**
> **username_0**: We have already proven that $1.81... \cdot n$ bit is the optimal value using recursive formula's and counting the `legal` sequences. How have you found that that is the optimal value? Are there even more effective ways than this $1.83... \cdot n$ algorithm?  
> **username_2**: @Rudy: I used recursive formulas and counting the legal sequences to get $1.813\, n$ as well. There are certainly even more effective ways than the $1.833 \, n$ algorithm, but I don't know whether any of them are as simple.  
> **username_2**: @Rudy: somewhere in the literature there should be theorem giving polynomial-time algorithms for doing run-length encoding with arbitrary constraints. So, yes, you can get more effective algorithms. But I don't have time to do the literature search for you, and offhand I don't know whether any of them are as simple as the encoding I give in my answer.  

---

### Answer by username_3 on 2012-02-22. Score: 2

For the problem as you've posed it, it seems that you could simply replace every occurrence of an illegal sequence by a new symbol so that: aababbbaba -> xbayaba.

I guess that's probably too simple, but we'll need more information to provide a better solution (like the cost of adding symbols).

> **Comments:**
> **username_0**: No, no new symbols are allowed, only $\{a,b\}$. So there are two symbols. We need to encode (il)illegal sequences to legal ones, and we must be able to go back to the original (il)legal sequences.  
> **username_3**: I see what you mean now: the x's represent a or b depending on the context. I'll have another think.  

---

