<p>Use the mapping that preserves the lexicographical order.
To find the $k$-th length-$n$ balanced vector with $n/2$ 1's, do it recursively:
if $k\leq{n-1\choose n/2}$, then set the first bit 0 and then find the $k$-th length-$(n-1)$ vector with $n/2$ 1's to complete the remaining $n-1$ bits. Otherwise set the first bit 1 and find the $k-{n-1\choose n/2}$-th length-$(n-1)$ vector with $n/2-1$ 1's.</p>

CC BY-SA 2.5
2010-09-01T14:29:17.647Z
And if you reuse the value of a binomial coefficient to compute the next required binomial coefficient, the whole algorithm runs in O(n) time.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T04:22:39.470Z
Thanks! This makes sense. 

I guess the running time will depend on the computational model. If you can perform operations on n-bit numbers in unit time, the implementation by Tsuyoshi Ito will run in O(n) time. On the other hand, if you count bit operations, the time will be O(n^2), I think.
Piotr
CC BY-SA 2.5
2010-09-01T11:20:51.433Z
2010-09-01T11:20:51.433Z
Zeyu
<p>Let's consider $n$-bit strings $x$. Definitions:</p>

<ul>
<li>$f(x,i)$ = bit string $x$ with last $i$ bits complemented.</li>
<li>$b(x)$ = "imbalance" of $x$: number of 1s in $x$ $-$ number of 0s in $x$.</li>
</ul>

<p>Now fix a string $x$. Consider the function $g(i) = b(f(x,i))$. Observations:</p>

<ul>
<li>$g(0) = b(x)$.</li>
<li>$g(n) = -g(0)$.</li>
<li>$|g(i) - g(i+1)| = 2$ for all $i$. We either remove one 0 and add one 1 or vice versa.</li>
</ul>

<p>Now it follows that there exists an $i$ such that $-1 \le g(i) \le +1$.</p>

<p>Hence we can construct an $(n+O(\log n))$-bit string $y$ as follows: concatenate $f(x,i)$ and the binary encoding of the index $i$. The absolute value of the imbalance of $y$ is $O(\log n)$. Moreover, we can recover $x$ given $y$; the mapping is bijection.</p>

<p>Finally, you can add $O(\log n)$ dummy bits that reduce the imbalance of $y$ from $O(\log n)$ to $0$.</p>

CC BY-SA 2.5
2010-09-01T13:42:41.707Z
b(x) in the 3rd line should be b(y).
Emil
CC BY-SA 2.5
2010-09-01T13:53:01.713Z
I think that you need to possibly add another bit to the string x to ensure that it has even length (so that you can be sure that g(i) is zero for some i).
Emil
CC BY-SA 2.5
2010-09-01T13:58:13.780Z
@Emil: I don't claim that $g(i)$ is be zero for some $i$; it is sufficient that the absolute value of $g(i)$ is "fairly small" for some $i$ (at most logarithmic would be enough, but it's easy to show that it will be at most $1$ for some $i$).
Jukka Suomela
CC BY-SA 2.5
2010-09-01T14:06:43.160Z
@Jukka: Ah yes I see.
Emil
CC BY-SA 2.5
2010-09-01T16:57:04.603Z
But yes, you are right, there are many variants of the same basic approach. For example, as you suggested, you can first use a padding bit to ensure that $g(i)$ will be equal zero for some $i$; then you can encode $i$ by using bit pairs $01$ or $10$, that is $2\log(n)$ extra bits; then the result of the concatenation is strictly balanced and you don't need to add anything else.
Jukka Suomela
CC BY-SA 2.5
2010-09-01T11:22:29.000Z
2010-09-01T13:45:31.743Z
2010-09-01T13:45:31.743Z
Jukka Suomela
<p>It is easy to see that for any $n$ there exists a 1-1 mapping $F$ from {0,1}$^n$ to {0,1}$^{n+O(\log n)}$ such that for any $x$ the vector $F(x)$ is "balanced", i.e., it has equal number of 1s and 0s. Is it possible to define such $F$ so that given $x$ we can compute $F(x)$  efficiently ?</p>

<p>Thanks.</p>

CC BY-SA 2.5
2010-09-01T08:12:33.750Z
I assume that by 'efficient' you mean O(n) or thereabouts, ruling out the "repeated random trials" argument ?
Suresh Venkat
CC BY-SA 2.5
2010-09-01T13:53:44.057Z
@Suresh, Would you be able to sketch the "repeated random trials" argument?
Emil
CC BY-SA 2.5
2010-09-01T16:42:50.243Z
one way of proving that the mapping exists is by the probabilistic method: pick F at random, and then the mapping works with some probability. that's what I meant.
Suresh Venkat
CC BY-SA 2.5
2010-09-01T22:17:31.213Z
The question is perfectly well-defined but, in my opinion, the title is misleading.  I would not call a mapping F satisfying the stated condition an “encoding of balanced vectors” unless F is bijective.  It is more like an encoding of an n-bit string _by_ a balanced vector.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T02:14:33.747Z
“Perfectly well-defined” up to possibly different interpretations of “efficiently,” I mean.  But this is not the point of my previous comment.
Tsuyoshi Ito
<ds.algorithms><ds.data-structures><encoding>
Quick encoding of balanced vectors
Piotr
# Quick encoding of balanced vectors

(Asked by: username_0 on 2010-09-01)

It is easy to see that for any $n$ there exists a 1-1 mapping $F$ from {0,1}$^n$ to {0,1}$^{n+O(\log n)}$ such that for any $x$ the vector $F(x)$ is "balanced", i.e., it has equal number of 1s and 0s. Is it possible to define such $F$ so that given $x$ we can compute $F(x)$ efficiently ?

Thanks.

**Tags:** ds.algorithms, ds.data-structures, encoding

> **Comments:**
> **username_1**: I assume that by 'efficient' you mean O(n) or thereabouts, ruling out the "repeated random trials" argument ?  
> **username_2**: @Suresh, Would you be able to sketch the "repeated random trials" argument?  
> **username_1**: one way of proving that the mapping exists is by the probabilistic method: pick F at random, and then the mapping works with some probability. that's what I meant.  
> **username_3**: The question is perfectly well-defined but, in my opinion, the title is misleading.  I would not call a mapping F satisfying the stated condition an “encoding of balanced vectors” unless F is bijective.  It is more like an encoding of an n-bit string _by_ a balanced vector.  
> **username_3**: “Perfectly well-defined” up to possibly different interpretations of “efficiently,” I mean.  But this is not the point of my previous comment.  

---

## 2 answers

### Answer by username_5 on 2010-09-01. Score: 12 | Accepted answer

Let's consider $n$-bit strings $x$. Definitions:

* $f(x,i)$ = bit string $x$ with last $i$ bits complemented.
* $b(x)$ = "imbalance" of $x$: number of 1s in $x$ $-$ number of 0s in $x$.

Now fix a string $x$. Consider the function $g(i) = b(f(x,i))$. Observations:

* $g(0) = b(x)$.
* $g(n) = -g(0)$.
* $|g(i) - g(i+1)| = 2$ for all $i$. We either remove one 0 and add one 1 or vice versa.

Now it follows that there exists an $i$ such that $-1 \le g(i) \le +1$.

Hence we can construct an $(n+O(\log n))$-bit string $y$ as follows: concatenate $f(x,i)$ and the binary encoding of the index $i$. The absolute value of the imbalance of $y$ is $O(\log n)$. Moreover, we can recover $x$ given $y$; the mapping is bijection.

Finally, you can add $O(\log n)$ dummy bits that reduce the imbalance of $y$ from $O(\log n)$ to $0$.

> **Comments:**
> **username_2**: b(x) in the 3rd line should be b(y).  
> **username_2**: I think that you need to possibly add another bit to the string x to ensure that it has even length (so that you can be sure that g(i) is zero for some i).  
> **username_5**: @username_2: I don't claim that $g(i)$ is be zero for some $i$; it is sufficient that the absolute value of $g(i)$ is "fairly small" for some $i$ (at most logarithmic would be enough, but it's easy to show that it will be at most $1$ for some $i$).  
> **username_2**: @Jukka: Ah yes I see.  
> **username_5**: But yes, you are right, there are many variants of the same basic approach. For example, as you suggested, you can first use a padding bit to ensure that $g(i)$ will be equal zero for some $i$; then you can encode $i$ by using bit pairs $01$ or $10$, that is $2\log(n)$ extra bits; then the result of the concatenation is strictly balanced and you don't need to add anything else.  

---

### Answer by username_4 on 2010-09-01. Score: 9

Use the mapping that preserves the lexicographical order.
To find the $k$-th length-$n$ balanced vector with $n/2$ 1's, do it recursively:
if $k\leq{n-1\choose n/2}$, then set the first bit 0 and then find the $k$-th length-$(n-1)$ vector with $n/2$ 1's to complete the remaining $n-1$ bits. Otherwise set the first bit 1 and find the $k-{n-1\choose n/2}$-th length-$(n-1)$ vector with $n/2-1$ 1's.

> **Comments:**
> **username_3**: And if you reuse the value of a binomial coefficient to compute the next required binomial coefficient, the whole algorithm runs in O(n) time.  
> **username_0**: Thanks! This makes sense.   I guess the running time will depend on the computational model. If you can perform operations on n-bit numbers in unit time, the implementation by username_3 will run in O(n) time. On the other hand, if you count bit operations, the time will be O(n^2), I think.  

---

