Вычисление четности перестановки потоковым способом

Я ищу однопроходный алгоритм, который вычисляет четность перестановки. Я предполагаю, что входная перестановка задается потоком . Выходными данными должно быть соотношение перестановок. Вопрос, который меня интересует, сколько памяти должен использовать детерминированный алгоритм. Есть ли какой-либо рандомизированный алгоритм для задачи? $\pi[1], \pi[2], \cdots, \pi[n]$

Я знаю, что для вычисления числа инверсий за один проход используется память . Верхняя граница может быть легко получена с помощью любого BST. Нижняя граница представлена здесь: http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622 $\Theta(n)$

Увы, доказательство нижней границы в статье не может быть распространено на случай четности (или это не так очевидно для меня).

Также я знаю, что вычисление четности в небольшом пространстве с произвольным доступом к перестановке может быть выполнено за времени и памяти детерминированным алгоритмом или за время и памяти случайным образом. См. 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)$

Основная идея состоит в том, что четность перестановки может быть вычислена по формуле , где - число циклов, а - размер. Авторы делают цикл разложения перестановки. Таким образом, можно легко вычислить количество циклов. $sgn(\pi) = (-1)^{n - c}$ $c$ $n$

Кто-нибудь знает эффективный алгоритм или нижнюю границу памяти для вычисления четности в потоковой модели? Рандомизированные алгоритмы лучше случайной монеты мне тоже интересны.

ds.algorithms permutations streaming-algorithms Всеволод Опарин
источник

Это интересно. Не могли бы вы набросать доказательство или назвать проблему, которую вы сводите к паритету?

Всеволод Опарин

@ András: Алгоритм пространства O (n) не работает, просто отслеживая, какие элементы уже были видны (скажем, в битовом векторе), а затем для каждого нового элемента x добавляя четность # числа пока-что- видели элементы меньше х?

Ласло Козма

@laszlo ваша верхняя граница теперь кажется мне более убедительной, чем мой аргумент в пользу большей нижней границы.

O (n)

$O(n)$

Андрас Саламон

Один отрицательный результат для нижней границы. Авторы первой статьи предусматривает перестановки на основе двух множеств и . Они используют его, чтобы вычислить, пересекаются ли иВычисление четности перестановки занимает всего 3 бита односторонней связи. Это может быть легко получено путем вычисления ранга соответствующей матрицы.

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

Всеволод Опарин

Связанный: stackoverflow.com/questions/20702782/...

domotorp

Ответы:

Я хотел бы попросить всех не высказывать это, так как это не ответ, а расширенный комментарий, в котором я хотел бы обсудить, почему на этот вопрос не было получено никаких ответов. Главное, что нижняя граница сложности общения не будет работать. Под этим я подразумеваю, что независимо от того, как мы разделим входные данные на две части и дадим их двум игрокам, A и B, A может передать один бит в B, из которого он может вычислить четность перестановки. (Это следует просто из рассмотрения инверсий.)

Доказательства, использующие другую границу, сложны. См. Этот комментарий здесь от Ноама Нисана (для недетерминированной версии): Ограничения по размеру самого маленького NFA для L_k-отчетливого ,

На этот связанный вопрос я сам ответил Германом Грубером, который показывает, что нижняя граница сложности общения может быть очень далека от истины (опять же в недетерминированной версии) Нижняя граница для NFA, принимающего трехбуквенный язык .

Также связано с тем, что решить, является ли перестановка одним циклом, кажется трудным, см. Этот документ FOCS Ран Раза и Бориса Шпикера: http://www.computer.org/csdl/proceedings/focs/1993/4370/00 /0366870-abs.html .

Поэтому мне также очень интересно узнать ответ на этот вопрос.

domotorp
источник

Когда вы говорите, что «независимо от того, как мы разрезаем входные данные на две части», ваш аргумент также исключает сокращения, когда перестановка делится на более чем две части? Например , в связанном документе о подсчете числа инверсий, происходит уменьшение от множества дизъюнктности, где Алиса и Боб имеют входы

, и они образуют перестановки

. Индекс 0 или 1 относится к преобразованиям

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: В этой задаче действительно не имеет значения, как вы сокращаете ввод, если вы даете его только двум игрокам, так как четность перестановки определяется количеством циклов (поэтому она отличается от числа инверсий).

domotorp

Легко ли увидеть, как А может вычислить немного из ее входных данных, используя которые В может вычислить четность? Я вижу, как и A, и B знают количество циклов «внутри их частей». Но как они находят соотношение числа «пересекающихся» циклов?

Ласло Козьма

@laszlo: Предположим, что ввод A что-то вроде 1-> 7, 2-> 5, 3-> 8, 4-> 6. Это имеет то же количество инверсий, что и 1-> 5, 2-> 6, 3-> 8, 4-> 7. В более общем смысле, B знает, в какие числа отображаются числа A. Используя четное число инверсий, 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)$