Codificação rápida de vetores balanceados

10

É 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?nFnn+O(logn)xF(x)FxF(x)

Obrigado.

Piotr
fonte
Suponho que por 'eficiente' você queira dizer O (n) ou o que está por aí, descartando o argumento de "ensaios aleatórios repetidos"?
Suresh Venkat
@Suresh, você seria capaz de esboçar o argumento de "ensaios aleatórios repetidos"?
Emil
Uma maneira de provar que o mapeamento existe é pelo método probabilístico: escolha F aleatoriamente e, em seguida, o mapeamento funcionará com alguma probabilidade. foi isso que eu quis dizer.
Suresh Venkat
11
A questão está perfeitamente bem definida, mas, na minha opinião, o título é enganoso. Eu não chamaria um mapeamento F satisfazendo a condição declarada de "codificação de vetores balanceados", a menos que F seja bijetivo. É mais como uma codificação de uma sequência de n bits por um vetor balanceado.
Tsuyoshi Ito
“Perfeitamente bem definido”, até possíveis interpretações diferentes de “eficientemente”, quero dizer. Mas esse não é o objetivo do meu comentário anterior.
Tsuyoshi Ito

Respostas:

12

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

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

Agora corrija uma string . Considere a função g ( i ) = b ( f ( x , i ) ) . Observações:xg(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)|=2i

Agora segue-se que existe um tal que - 1 g ( i ) + 1 .i1g(i)+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(logn))yf(x,i)iyO(logn)xy

O(logn)yO(logn)0

Jukka Suomela
fonte
b (x) na terceira linha deve ser b (y).
Emil
Eu acho que é possível adicionar outro bit à string x para garantir que ela tenha comprimento uniforme (para que você possa ter certeza de que g (i) é zero para alguns i).
Emil
g(i)ig(i)i1i
@Jukka: Ah sim, eu vejo.
Emil
11
g(i)ii01102log(n)
9

knn/2k(n1n/2)k(n1)n/2n1k(n1n/2)(n1)n/21

Zeyu
fonte
11
E se você reutilizar o valor de um coeficiente binomial para calcular o próximo coeficiente binomial necessário, todo o algoritmo será executado no tempo O (n).
Tsuyoshi Ito
Obrigado! Isso faz sentido. Eu acho que o tempo de execução dependerá do modelo computacional. Se você pode executar operações em números de n bits em tempo unitário, a implementação por Tsuyoshi Ito será executada em O (n) tempo. Por outro lado, se você contar operações de bits, o tempo será O (n ^ 2), eu acho.
Piotr