Berechnen der Parität einer Permutation auf Streaming-Weise

Ich suche nach einem One-Pass-Algorithmus, der die Parität einer Permutation berechnet. Ich gehe davon aus, dass eine Eingabepermutation durch stream . Die Ausgabe sollte die Parität der Permutation sein. Die Frage, die mich interessiert, wie viel Speicher ein deterministischer Algorithmus verwenden sollte. Gibt es einen zufälligen Algorithmus für das Problem? $\pi[1], \pi[2], \cdots, \pi[n]$

Ich weiß, dass die Berechnung der Anzahl der Inversionen in einem Durchgang -Speicher verwendet. Die Obergrenze kann leicht mit jedem BST erhalten werden. Die Untergrenze wird hier dargestellt: http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622 $\Theta(n)$

Leider kann der Nachweis der Untergrenze im Papier nicht auf den Paritätsfall ausgedehnt werden (oder es ist für mich nicht so offensichtlich).

Ich weiß auch, dass die Berechnung der Parität auf kleinem Raum mit wahlfreiem Zugriff auf eine Permutation in Zeit und Speicher durch deterministischen Algorithmus oder in Zeit und Speicher nach dem Zufallsprinzip. Siehe 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)$

Die Hauptidee ist, dass die Parität einer Permutation durch die Formel berechnet werden kann , wobei die Anzahl der Zyklen und die Größe ist. Die Autoren machen die Zykluszerlegung einer Permutation. So kann man leicht die Anzahl der Zyklen berechnen. $sgn(\pi) = (-1)^{n - c}$ $c$ $n$

Kennt jemand einen effektiven Algorithmus oder eine niedrigere Speichergrenze für die Berechnung der Parität im Streaming-Modell? Randomisierte Algorithmen, die besser sind als zufällige Münzen, interessieren mich auch.

ds.algorithms permutations streaming-algorithms Vsevolod Oparin
quelle

Es ist interessant. Können Sie einen Beweis skizzieren oder ein Problem benennen, das Sie auf Parität reduzieren?

Vsevolod Oparin

@ András: Funktioniert ein O (n) -Raum-Algorithmus nicht einfach, indem verfolgt wird, welche Elemente bereits gesehen wurden (z. B. in einem Bitvektor), und dann für jedes neue Element x die Parität des # der noch zu- gesehen werden Elemente kleiner als x?

László Kozma

@laszlo Ihre -Obergrenze scheint mir jetzt überzeugender zu sein als mein Argument für eine größere Untergrenze.

O (n)

$O(n)$

András Salamon

Ein negatives Ergebnis für die Untergrenze. Die Autoren des ersten die Permutation basierend auf zwei Mengen und . Sie berechnen damit, ob sich und überschneiden. Die Berechnung der Parität der Permutation erfordert nur 3 Bits für die Einwegkommunikation. Es kann leicht erhalten werden, indem der Rang der entsprechenden Matrix berechnet wird.

π = \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

Related: stackoverflow.com/questions/20702782/…

domotorp

Antworten:

Ich möchte alle bitten, dies nicht zu befürworten, da dies keine Antwort, sondern ein ausführlicher Kommentar ist, in dem ich darlegen möchte, warum diese Frage keine Antworten erhalten hat. Mein Hauptpunkt ist, dass eine untere Grenze der Kommunikationskomplexität nicht funktioniert. Damit meine ich, dass, egal wie wir die Eingabe in zwei Teile teilen und an zwei Spieler, A und B, weitergeben, A ein einzelnes Bit nach B übertragen kann, aus dem er die Parität der Permutation berechnen kann. (Dies folgt einfach durch Berücksichtigung von Inversionen.)

Beweise, die eine andere Grenze verwenden, sind schwer. Siehe diesen Kommentar hier von Noam Nisan (für die nicht deterministische Version): Schranke der Größe der kleinsten NFA für L_k-distinct ,

diese Frage im Zusammenhang von mir beantwortet von Hermann Gruber , die zeigt , dass die Kommunikationskomplexität geringer kann sehr weit von der Wahrheit (in der nicht-deterministischen Version wieder) gebunden seine Untere Grenze Sprache für NFA akzeptieren 3 Buchstaben .

Auch darauf bezogen, dass die Entscheidung, ob die Permutation ein einzelner Zyklus ist, schwierig zu sein scheint, siehe dieses FOCS-Papier von Ran Raz und Boris Spieker: http://www.computer.org/csdl/proceedings/focs/1993/4370/00 /0366870-abs.html .

Daher bin ich auch sehr daran interessiert, die Antwort auf diese Frage zu erfahren.

domotorp
quelle

Wenn Sie sagen, dass "egal wie wir die Eingabe in zwei Teile schneiden", schließt Ihr Argument auch Verringerungen aus, wenn die Permutation in mehr als zwei Teile aufgeteilt wird? In dem verlinkten Artikel zum Zählen der Anzahl der Inversionen gibt es beispielsweise eine Reduzierung der eingestellten Disjunktheit, bei der Alice und Bob die Eingaben haben und Permutationen und . Der Index 0 oder 1 bezieht sich auf die Transformationen und , und der Balken bezieht sich auf die Ergänzung. Was ist mit anderen Worten, wenn die Kommunikation mehrere Runden dauern kann?

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$

László Kozma

@laszlo: In diesem Problem ist es wirklich egal, wie Sie die Eingabe schneiden, solange Sie sie nur zwei Spielern geben, da die Parität der Permutation durch die Anzahl ihrer Zyklen bestimmt wird (aus diesem Grund unterscheidet sie sich von der Anzahl) von Inversionen).

Domotorp

Ist es leicht zu sehen, wie A aus ihrer Eingabe ein bisschen berechnen kann, mit welcher B die Parität berechnen kann? Ich sehe, wie sowohl A als auch B die Anzahl der Zyklen "in ihren Teilen" kennen. Aber wie finden sie die Parität der Anzahl der "kreuzenden" Zyklen?

László Kozma

@laszlo: Angenommen, die Eingabe von A ist etwa 1-> 7, 2-> 5, 3-> 8, 4-> 6. Dies hat die gleiche Anzahl von Inversionen wie 1-> 5, 2-> 6, 3-> 8, 4-> 7. Im Allgemeinen weiß B, in welche Zahlen die Zahlen von A abgebildet werden. Mit einer geraden Anzahl von Inversionen kann A diese Zahlen in aufsteigender Reihenfolge permutieren, mit Ausnahme der letzten beiden. Die Relation dieser letzten beiden Zahlen ist das eine Bit, das sie sendet.

Domotorp

@ domotor: Folgefrage - Wenn A , B , C bekommt bei einer Permutation von die Parität mit Kommunikationsbits herstellen?

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

László Kozma