Szybkie kodowanie wektorów zrównoważonych

Łatwo zauważyć, że dla dowolnego istnieje odwzorowanie 1-1 z {0,1} na {0,1} takie, że dla dowolnego wektor jest „zbalansowany”, tzn. ma równą liczbę 1 i 0. Czy jest możliwe zdefiniowanie takiego , aby przy danym można było skutecznie obliczyć ? $n$ $F$ $^n$ $^{n+O(\log n)}$ $x$ $F(x)$ $F$ $x$ $F(x)$

Dzięki.

ds.algorithms ds.data-structures encoding

— Piotr
źródło

Zakładam, że przez „sprawny” rozumiesz O (n) lub inne, wykluczając argument „powtarzane próby losowe”?

— Suresh Venkat

@Suresh, czy byłbyś w stanie naszkicować argument „powtarzane losowe próby”?

— Emil

jednym ze sposobów udowodnienia, że mapowanie istnieje, jest metoda probabilistyczna: wybierz F losowo, a następnie mapowanie działa z pewnym prawdopodobieństwem. o to mi chodziło.

— Suresh Venkat

Pytanie jest doskonale dobrze zdefiniowane, ale moim zdaniem tytuł wprowadza w błąd. Nie nazwałbym F odwzorowaniem spełniającym podany warunek „kodowaniem wektorów zrównoważonych”, chyba że F jest bijective. To bardziej przypomina kodowanie ciągu n-bitowego przez zrównoważony wektor.

— Tsuyoshi Ito

Mam na myśli „perfekcyjnie dobrze zdefiniowane”, a nawet różne interpretacje „efektywnie”. Ale nie o to chodzi w moim poprzednim komentarzu.

— Tsuyoshi Ito

Odpowiedzi:

Rozważmy bitowe łańcuchy . Definicje: $n$ $x$

$f(x,i)$ = ciąg bitów z uzupełnieniem ostatnich bitów. $x$ $i$
$b(x)$ = "nierównowaga" od : liczba od 1 s w liczbę 0 s w . $x$ $x$ $-$ $x$

Teraz napraw ciąg . Rozważ funkcję . Obserwacje: $x$ $g(i) = b(f(x,i))$

$g(0) = b(x)$ .
$g(n) = -g(0)$ .
$|g(i) - g(i+1)| = 2$ dla wszystkich . Usuwamy jedno 0 i dodajemy jedno 1 lub odwrotnie. $i$

Wynika z tego, że istnieje taki, że . $i$ $-1 \le g(i) \le +1$

Stąd możemy skonstruować -bitowy ciąg w następujący sposób: konkatenować i binarne kodowanie indeksu . Bezwzględna wartość niezbilansowania wynosi . Co więcej, możemy odzyskać biorąc pod uwagę ; mapowanie jest bolesne. $(n+O(\log n))$ $y$ $f(x,i)$ $i$ $y$ $O(\log n)$ $x$ $y$

Na koniec możesz dodać bity pozorne które zmniejszają nierównowagę z do . $O(\log n)$ $y$ $O(\log n)$ $0$

— Jukka Suomela
źródło

b (x) w 3. linii powinno być b (y).

— Emil

Myślę, że musisz ewentualnie dodać kolejny bit do łańcucha x, aby upewnić się, że ma on równą długość (abyś mógł być pewien, że g (i) wynosi zero dla niektórych i).

— Emil

g (i)

$g(i)$

i

$i$

g (i)

$g(i)$

i

$i$

1

$1$

i

$i$

@Jukka: Ach tak, rozumiem.

— 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
źródło

A jeśli ponownie użyjesz wartości współczynnika dwumianowego do obliczenia następnego wymaganego współczynnika dwumianowego, cały algorytm działa w czasie O (n).

— Tsuyoshi Ito

Dzięki! To ma sens. Wydaje mi się, że czas działania zależy od modelu obliczeniowego. Jeśli możesz wykonywać operacje na liczbach n-bitowych w jednostkowym czasie, implementacja przez Tsuyoshi Ito będzie działać w czasie O (n). Z drugiej strony, jeśli policzysz operacje bitowe, czas będzie wynosił O (n ^ 2).

— Piotr