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

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