Szybkie kodowanie wektorów zrównoważonych

10

Ł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ć ?F n n + O ( log n ) x F ( x ) F x F ( x )nFnn+O(logn)xF(x)FxF(x)

Dzięki.

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
1
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:

12

Rozważmy bitowe łańcuchy . Definicje:xnx

  • x if(x,i) = ciąg bitów z uzupełnieniem ostatnich bitów.xi
  • x x - xb(x) = "nierównowaga" od : liczba od 1 s w liczbę 0 s w .xx x

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

  • g(0)=b(x) .
  • g(n)=g(0) .
  • i|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 .- 1 g ( i ) + 1i1g(i)+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.y f ( x , i ) i y O ( log n ) x y(n+O(logn))yf(x,i)iyO(logn)xy

Na koniec możesz dodać bity pozorne które zmniejszają nierównowagę z do .y O ( log n ) 0O(logn)yO(logn)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)ig(i)i1i
@Jukka: Ach tak, rozumiem.
Emil
1
g(i)ii01102log(n)
9

knn/2k(n-1)n/2n-1k-(n-1)k(n1n/2)k(n1)n/2n1(n-1)n/2-1k(n1n/2)(n1)n/21

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