Encodage rapide de vecteurs équilibrés

Il est facile de voir que pour tout $n$ il existe un mappage 1-1 $F$ de {0,1} à {0,1} telle sorte que pour tout le vecteur est " équilibré ", c'est-à-dire qu'il a un nombre égal de 1 et de 0. Est-il possible de définir un tel pour que, étant donné nous pouvons calculer efficacement? $^n$ $^{n+O(\log n)}$ $x$ $F(x)$ $F$ $x$ $F(x)$

Merci.

ds.algorithms ds.data-structures encoding Piotr
la source

Je suppose que par «efficace» vous voulez dire O (n) ou à peu près, excluant l'argument des «essais aléatoires répétés»?

Suresh Venkat

@Suresh, seriez-vous capable d'esquisser l'argument des "essais aléatoires répétés"?

Emil

une façon de prouver que la cartographie existe est par la méthode probabiliste: choisir F au hasard, puis la cartographie fonctionne avec une certaine probabilité. c'est ce que je voulais dire.

Suresh Venkat

La question est parfaitement bien définie mais, à mon avis, le titre est trompeur. Je n'appellerais pas un mappage F satisfaisant à la condition énoncée un «codage de vecteurs équilibrés» à moins que F ne soit bijectif. Cela ressemble plus à un codage d'une chaîne de n bits par un vecteur équilibré.

Tsuyoshi Ito du

«Parfaitement bien défini» jusqu'à des interprétations éventuellement différentes de «efficacement», je veux dire. Mais ce n'est pas le point de mon commentaire précédent.

Tsuyoshi Ito du

Réponses:

$n$ $x$

$f(x,i)$ $x$ $i$
$b(x)$ $x$ $x$ $-$ $x$

$x$ $g(i) = b(f(x,i))$

$g(0) = b(x)$
$g(n) = -g(0)$
$|g(i) - g(i+1)| = 2$ $i$

$i$ $-1 \le g(i) \le +1$

$(n+O(\log n))$ $y$ $f(x,i)$ $i$ $y$ $O(\log n)$ $x$ $y$

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

Jukka Suomela
la source

b (x) dans la 3e ligne doit être b (y).

Emil

Je pense que vous devez éventuellement ajouter un autre bit à la chaîne x pour vous assurer qu'il a une longueur égale (afin que vous puissiez être sûr que g (i) est nul pour certains i).

Emil

g (i)

$g(i)$

i

$i$

g (i)

$g(i)$

i

$i$

1

$1$

i

$i$

@Jukka: Ah oui je vois.

Emil

g (i)

$g(i)$

i

$i$

i

$i$

01

$01$

10

$10$

2 \log (n)

$2\log(n)$

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

Zeyu
la source

Et si vous réutilisez la valeur d'un coefficient binomial pour calculer le prochain coefficient binomial requis, l'algorithme entier s'exécute en temps O (n).

Tsuyoshi Ito du

Merci! C'est logique. Je suppose que le temps d'exécution dépendra du modèle de calcul. Si vous pouvez effectuer des opérations sur des nombres à n bits en temps unitaire, l'implémentation par Tsuyoshi Ito s'exécutera en temps O (n). D'un autre côté, si vous comptez les opérations sur les bits, le temps sera O (n ^ 2), je pense.

Piotr