9
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ I assume that by 'efficient' you mean O(n) or thereabouts, ruling out the "repeated random trials" argument ? $\endgroup$
    – Suresh Venkat
    Commented Sep 1, 2010 at 8:12
  • $\begingroup$ @Suresh, Would you be able to sketch the "repeated random trials" argument? $\endgroup$
    – Emil
    Commented Sep 1, 2010 at 13:53
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Sep 1, 2010 at 16:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 1, 2010 at 22:17
  • $\begingroup$ “Perfectly well-defined” up to possibly different interpretations of “efficiently,” I mean. But this is not the point of my previous comment. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 2, 2010 at 2:14

2 Answers 2

Reset to default
12
$\begingroup$

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$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ b(x) in the 3rd line should be b(y). $\endgroup$
    – Emil
    Commented Sep 1, 2010 at 13:42
  • $\begingroup$ 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). $\endgroup$
    – Emil
    Commented Sep 1, 2010 at 13:53
  • $\begingroup$ @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$). $\endgroup$
    – Jukka Suomela
    Commented Sep 1, 2010 at 13:58
  • $\begingroup$ @Jukka: Ah yes I see. $\endgroup$
    – Emil
    Commented Sep 1, 2010 at 14:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jukka Suomela
    Commented Sep 1, 2010 at 16:57
9
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 1, 2010 at 14:29
  • $\begingroup$ 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. $\endgroup$
    – Piotr
    Commented Sep 2, 2010 at 4:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.