Codificação rápida de vetores balanceados

É fácil ver que para qualquer existe um mapeamento 1-1 F de {0,1} n a {0,1} n + O ( log n ), de modo que, para qualquer x, o vetor F ( x ) é " equilibrado ", ou seja, possui número igual de 1s e 0s. É possível definir tal F para que, dado x , possamos calcular F ( x ) eficientemente?$n$$F$$^n$$^{n+O(\log n)}$$x$$F(x)$$F$$x$$F(x)$

Obrigado.

Vamos considerar as cadeias bits x . Definições:$n$$x$

• = sequência de bits x com os últimos i bits complementados.$f(x,i)$$x$$i$
• = "desequilíbrio" de x : número de 1s em x - número de 0s em x .$b(x)$$x$$x$ $-$$x$

Agora corrija uma string . Considere a função g ( i ) = b ( f ( x , i ) ) . Observações:$x$$g(i) = b(f(x,i))$

• .$g(0) = b(x)$
• .$g(n) = -g(0)$
• para todos i . Nós removemos um 0 e adicionamos um 1 ou vice-versa.$|g(i) - g(i+1)| = 2$$i$

Agora segue-se que existe um tal que - 1 ≤ g ( i ) ≤ + 1 .$i$$-1 \le g(i) \le +1$

Portanto, podemos construir uma sequência de bits y da seguinte forma: concatenar f ( x , i ) e a codificação binária do índice i . O valor absoluto do desequilíbrio de y é O ( log n ) . Além disso, podemos recuperar x dado y ; o mapeamento é bijeção.$(n+O(\log n))$$y$$f(x,i)$$i$$y$$O(\log n)$$x$$y$

$O(\log n)$$y$$O(\log n)$$0$

$k$$n$$n/2$$k\leq{n-1\choose n/2}$$k$$(n-1)$$n/2$$n-1$$k-{n-1\choose n/2}$$(n-1)$$n/2-1$