Obliczanie parzystości permutacji w sposób strumieniowy

Szukam algorytmu jednoprzebiegowego, który oblicza parzystość permutacji. Zakładam, że permutacja wejściowa jest podawana przez strumień . Wyjście powinno być parzystością permutacji. Pytanie mnie interesuje, ile pamięci powinien użyć algorytm deterministyczny. Czy istnieje jakiś losowy algorytm dotyczący problemu? $\pi[1], \pi[2], \cdots, \pi[n]$

Wiem, że obliczanie liczby inwersji w jednym przebiegu wykorzystuje pamięć . Górną granicę można łatwo uzyskać za pomocą dowolnego BST. Dolna granica jest przedstawiona tutaj: http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622 $\Theta(n)$

Niestety dowodu dolnej granicy w dokumencie nie można rozszerzyć na przypadek parzystości (lub nie jest to dla mnie tak oczywiste).

Wiem również, że obliczanie parzystości w niewielkiej przestrzeni z losowym dostępem do permutacji można wykonać w czasie i pamięci pomocą algorytmu deterministycznego lub w czasie i pamięć losowa. Zobacz http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.2256 $O(n \log n)$ $O(\log^2 n)$ $O(n \log n)$ $O(\log n)$

Główną ideą jest to, że parzystość permutacji można obliczyć za pomocą wzoru , gdzie jest liczbą cykli, a jest rozmiarem. Autorzy dokonują rozkładu cyklu permutacji. Można więc łatwo obliczyć liczbę cykli. $sgn(\pi) = (-1)^{n - c}$ $c$ $n$

Czy ktoś zna skuteczny algorytm lub dolną granicę pamięci do obliczania parzystości w modelu przesyłania strumieniowego? Interesujące są również algorytmy randomizowane lepiej niż losowe monety.

ds.algorithms permutations streaming-algorithms Wsiewołod Oparin
źródło

To interesujące. Czy możesz naszkicować dowód lub nazwać problem, który sprowadzasz do parzystości?

Vsevolod Oparin

@ András: Czy algorytm kosmiczny O (n) nie działa po prostu przez śledzenie, które elementy zostały już wyświetlone (powiedzmy w bitvector), a następnie dla każdego nowego elementu x dodanie parzystości liczby # jeszcze-do- widoczne elementy mniejsze niż x?

László Kozma,

@laszlo twoja górna granica

wydaje mi się teraz bardziej przekonująca niż mój argument za większą dolną granicą.

O (n)

$O(n)$

András Salamon,

Jeden wynik ujemny dla dolnej granicy. Autorzy pierwszego papieru zapewnia permutacji

oparty na dwóch zestawów

. Używają go do obliczania, czy przecinają się

Obliczenie parzystości permutacji zajmuje tylko 3 bity jednokierunkowej komunikacji. Można to łatwo uzyskać poprzez obliczenie rangi odpowiedniej macierzy.

π = \bar{A_{0}} B_{1} A_{0} \bar{B_{1}}

$\pi = \bar{A_0}B_1A_0\bar{B_1}$

A

$A$

B

$B$

A

$A$

B

$B$

Vsevolod Oparin,

Powiązane: stackoverflow.com/questions/20702782/...

domotorp

Odpowiedzi:

Chciałbym prosić wszystkich, aby nie głosowali za tym, ponieważ nie jest to odpowiedź, ale obszerny komentarz, w którym chciałbym spierać się, dlaczego na to pytanie nie otrzymano żadnych odpowiedzi. Chodzi mi przede wszystkim o to, że dolna granica złożoności komunikacji nie będzie działać. Rozumiem przez to, że bez względu na to, jak podzielimy dane wejściowe na dwie części i przekażemy je dwóm graczom, A i B, A może przenieść pojedynczy bit do B, z którego może obliczyć parzystość permutacji. (Wynika to po prostu z rozważenia inwersji).

Dowody, które używają innej granicy są trudne. Zobacz ten komentarz Noama Nisana (dla wersji niedeterministycznej): Ogranicza wielkość najmniejszego NFA dla L_k-odrębnego ,

na to pokrewne pytanie, na które odpowiedziałem Hermann Gruber, który pokazuje, że dolna granica złożoności komunikacji może być bardzo daleka od prawdy (ponownie w wersji niedeterministycznej) Dolna granica dla NFA akceptującego język 3-literowy .

Również związane z tym, aby zdecydować, czy permutacja jest pojedynczym cyklem, wydaje się trudne, patrz ten artykuł FOCS autorstwa Ran Raz i Borisa Spiekera: http://www.computer.org/csdl/proceedings/focs/1993/4370/00 /0366870-abs.html .

Dlatego też jestem bardzo zainteresowany uzyskaniem odpowiedzi na to pytanie.

domotorp
źródło

A, B \subseteq [n]

$A, B \subseteq [n]$

\bar{A_{0}} B_{1} A_{0} \bar{B_{1}}

$\bar{A_0} B_1 A_0 \bar{B_1}$

\bar{A_{1}} B_{0} A_{1} \bar{B_{0}}

$\bar{A_1} B_0 A_1 \bar{B_0}$

2 x

$2x$

2 x + 1

$2x+1$

@laszlo: W tym problemie tak naprawdę nie ma znaczenia, w jaki sposób obcinasz dane wejściowe, pod warunkiem, że podajesz je tylko dwóm graczom, ponieważ parzystość permutacji zależy od liczby jej cykli (dlatego różni się od liczby inwersji).

domotorp

Czy łatwo jest zobaczyć, w jaki sposób A może obliczyć trochę na podstawie danych wejściowych, za pomocą którego B może obliczyć parzystość? Widzę, jak zarówno A, jak i B znają liczbę cykli „w swoich częściach”. Ale jak znajdują parytet liczby cykli „przekraczania”?

László Kozma

@laszlo: Załóżmy, że dane wejściowe A to coś w rodzaju 1-> 7, 2-> 5, 3-> 8, 4-> 6. Ma taką samą liczbę inwersji jak 1-> 5, 2-> 6, 3-> 8, 4-> 7. Mówiąc bardziej ogólnie, B wie, na jakie liczby są mapowane liczby A. Używając parzystej liczby inwersji, A może zezwolić na te liczby w rosnącym porządku, z wyjątkiem ewentualnie dwóch ostatnich. Relacja tych dwóch ostatnich liczb to jeden bit, który wysyła.

domotorp

a_{1}, \dots, a_{n}

$a_1, \dots, a_n$

a_{n + 1}, \dots, a_{2 n}

$a_{n+1}, \dots, a_{2n}$

a_{2 n + 1}, \dots, a_{3 n}

$a_{2n+1}, \dots, a_{3n}$

a

$a$

[3 n]

$[3n]$

o (n)

$o(n)$