Calcul de la parité d'une permutation à la manière d'un streaming

Je recherche un algorithme à un passage qui calcule la parité d'une permutation. Je suppose qu'une permutation d'entrée est donnée par le flux $\pi[1], \pi[2], \cdots, \pi[n]$ . La sortie doit être la parité de la permutation. La question qui m'intéresse est la quantité de mémoire qu'un algorithme déterministe devrait utiliser. Existe-t-il un algorithme aléatoire pour le problème?

Je sais que le calcul du nombre d'inversions en un seul passage utilise la mémoire $\Theta(n)$ . La limite supérieure peut être facilement obtenue avec n'importe quel BST. La limite inférieure est présentée ici: http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622

Hélas, la preuve de la borne inférieure dans le papier ne peut pas être étendue au cas de parité (ou ce n'est pas si évident pour moi).

Je sais aussi que le calcul de la parité dans un petit espace avec un accès aléatoire à une permutation peut se faire en temps $O(n \log n)$ et en mémoire $O(\log^2 n)$ par un algorithme déterministe ou en temps $O(n \log n)$ et $O(\log n)$ mémoire par randomisé. Voir http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.2256

L'idée principale est que la parité d'une permutation peut être calculée par la formule , où est le nombre de cycles et est la taille. Les auteurs font la décomposition en cycle d'une permutation. On peut donc facilement calculer le nombre de cycles. $sgn(\pi) = (-1)^{n - c}$ $c$ $n$

Quelqu'un connaît-il un algorithme efficace ou une limite inférieure sur la mémoire pour calculer la parité dans le modèle de streaming? Les algorithmes randomisés mieux que la pièce aléatoire m'intéressent aussi.

ds.algorithms permutations streaming-algorithms Vsevolod Oparin
la source

C'est intéressant. Pourriez-vous esquisser une preuve ou nommer un problème que vous réduisez à la parité?

Vsevolod Oparin,

@ András: Un algorithme d'espace O (n) ne fonctionne-t-il pas simplement en gardant une trace des éléments qui ont déjà été vus (disons dans un bitvector), puis pour chaque nouvel élément x en ajoutant la parité du # de encore-à- des éléments visibles inférieurs à x?

László Kozma

@laszlo votre limite supérieure

me semble maintenant plus convaincante que mon argument en faveur d'une limite inférieure plus grande.

O (n)

$O(n)$

András Salamon

Un résultat négatif pour la borne inférieure. Les auteurs du premier document fournit permutation

sur la base de deux ensembles

. Ils l'utilisent pour calculer si

croisent. Le calcul de la parité de la permutation ne prend que 3 bits de communication unidirectionnelle. Il peut être facilement obtenu en calculant le rang de la matrice correspondante.

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

Connexe: stackoverflow.com/questions/20702782/…

domotorp

Réponses:

Je voudrais demander à tout le monde de ne pas voter positivement, car ce n'est pas une réponse, mais un commentaire étendu, dans lequel je voudrais expliquer pourquoi cette question n'a reçu aucune réponse. Mon point principal est qu'une complexité de communication inférieure ne fonctionnera pas. Par cela, je veux dire que peu importe la façon dont nous coupons l'entrée en deux parties et la donnons à deux joueurs, A et B, A peut transférer un seul bit vers B à partir duquel il peut calculer la parité de la permutation. (Cela suit simplement en considérant les inversions.)

Les preuves qui utilisent une autre borne sont difficiles. Voir ce commentaire ici de Noam Nisan (pour la version non déterministe): Limites sur la taille du plus petit NFA pour L_k-distinct ,

Hermann Gruber a moi-même répondu à cette question connexe qui montre que la limite inférieure de la complexité de la communication peut être très loin de la vérité (encore une fois dans la version non déterministe) Limite inférieure pour NFA acceptant le langage à 3 lettres .

Il semble également difficile de décider si la permutation est un cycle unique, voir ce document FOCS de Ran Raz et Boris Spieker: http://www.computer.org/csdl/proceedings/focs/1993/4370/00 /0366870-abs.html .

Donc, je suis également très intéressé par la réponse à cette question.

domotorp
la source

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: Dans ce problème, la façon dont vous coupez l'entrée n'a pas d'importance tant que vous ne la donnez qu'à deux joueurs car la parité de la permutation est déterminée par le nombre de ses cycles (c'est pourquoi elle diffère du nombre des inversions).

domotorp

Est-il facile de voir comment A peut calculer un peu à partir de son entrée en utilisant lequel B peut calculer la parité? Je vois comment A et B connaissent le nombre de cycles "dans leurs parties". Mais comment trouvent-ils la parité du nombre de cycles «croisés»?

László Kozma

@laszlo: Supposons que l'entrée de A soit quelque chose comme 1-> 7, 2-> 5, 3-> 8, 4-> 6. Cela a le même nombre d'inversions que 1-> 5, 2-> 6, 3-> 8, 4-> 7. Plus généralement, B sait dans quels nombres les nombres de A sont mappés. En utilisant un nombre pair d'inversions, A peut permuter ces nombres dans un ordre croissant, sauf éventuellement pour les deux derniers. La relation de ces deux derniers nombres est le seul bit qu'elle envoie.

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