Skip to main content
2 of 2
edited tags
Jukka Suomela
  • 11.6k
  • 2
  • 56
  • 117

Quick encoding of balanced vectors

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.

Piotr
  • 971
  • 7
  • 15