Menghitung paritas permutasi dengan cara streaming-mode

Saya mencari algoritma satu-pass yang menghitung paritas permutasi. Saya berasumsi bahwa permutasi input diberikan oleh stream . Outputnya harus paritas permutasi. Pertanyaan saya tertarik pada berapa banyak memori yang harus digunakan oleh algoritma deterministik. Apakah ada algoritma acak untuk masalah ini? $\pi[1], \pi[2], \cdots, \pi[n]$

Saya tahu bahwa menghitung jumlah inversi dalam satu pass menggunakan memori. Batas atas dapat dengan mudah diperoleh dengan BST apa pun. Batas bawah disajikan di sini: http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622 $\Theta(n)$

Sayangnya, bukti batas bawah di koran tidak dapat diperluas ke kasus paritas (atau tidak begitu jelas bagi saya).

Saya juga tahu bahwa menghitung paritas dalam ruang kecil dengan akses acak ke permutasi dapat dilakukan dalam waktu dan memori dengan algoritma deterministik atau dalam waktu dan memori secara acak. Lihat 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)$

Gagasan utamanya adalah bahwa paritas permutasi dapat dihitung dengan rumus , di mana adalah jumlah siklus dan adalah ukuran. Penulis membuat siklus dekomposisi permutasi. Jadi seseorang dapat dengan mudah menghitung jumlah siklus. $sgn(\pi) = (-1)^{n - c}$ $c$ $n$

Adakah yang tahu algoritma efektif atau batas bawah pada memori untuk menghitung paritas dalam model streaming? Algoritma acak lebih baik daripada koin acak juga menarik bagi saya.

ds.algorithms permutations streaming-algorithms Vsevolod Oparin
sumber

Ini menarik. Bisakah Anda membuat sketsa bukti atau nama masalah, yang Anda kurangi menjadi paritas?

Vsevolod Oparin

@ András: Bukankah algoritme ruang O (n) bekerja hanya dengan melacak elemen mana yang sudah terlihat (katakanlah dalam bitvector), dan kemudian untuk setiap elemen baru x menambahkan paritas # dari yet-to- elemen yang terlihat lebih kecil dari x?

László Kozma

@laszlo

batas atas Anda sekarang tampaknya lebih meyakinkan bagi saya daripada argumen saya untuk batas bawah yang lebih besar.

O (n)

$O(n)$

András Salamon

Satu hasil negatif untuk batas bawah. Para penulis dari kertas pertama menyediakan permutasi

berdasarkan pada dua set

dan

. Mereka menggunakannya untuk menghitung apakah

dan

berpotongan. Komputasi paritas permutasi hanya membutuhkan 3 bit komunikasi satu arah. Ini dapat dengan mudah diperoleh dengan menghitung peringkat matriks yang sesuai.

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

Terkait: stackoverflow.com/questions/20702782/…

domotorp

Jawaban:

Saya ingin meminta semua orang untuk tidak membenarkan ini, karena ini bukan jawaban, tetapi komentar panjang, di mana saya ingin berdebat mengapa pertanyaan ini tidak menerima jawaban. Poin utama saya adalah, bahwa kompleksitas komunikasi batas bawah tidak akan berfungsi. Maksud saya, tidak masalah bagaimana kita memotong input menjadi dua bagian dan memberikannya kepada dua pemain, A dan B, A dapat mentransfer bit tunggal ke B yang darinya dia dapat menghitung paritas permutasi. (Ini hanya mengikuti dengan mempertimbangkan inversi.)

Bukti yang menggunakan ikatan lain sulit. Lihat komentar ini di sini oleh Noam Nisan (untuk versi non-deterministik): Batas pada ukuran NFA terkecil untuk L_k-berbeda ,

pertanyaan terkait ini saya jawab sendiri oleh Hermann Gruber yang menunjukkan bahwa kompleksitas komunikasi batas bawah bisa sangat jauh dari kebenaran (sekali lagi dalam versi non-deterministik) Batas bawah untuk NFA menerima bahasa 3 huruf .

Juga terkait bahwa untuk memutuskan apakah permutasi adalah satu siklus, tampaknya sulit, lihat makalah FOCS ini oleh Ran Raz dan Boris Spieker: http://www.computer.org/csdl/proceedings/focs/1993/4370/00 /0366870-abs.html .

Jadi, saya juga sangat tertarik untuk mempelajari jawaban atas pertanyaan ini.

domotorp
sumber

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

2 x + 1

$2x+1$

@laszlo: Dalam masalah ini benar-benar tidak masalah bagaimana Anda memotong input selama Anda memberikannya hanya kepada dua pemain karena paritas permutasi ditentukan oleh jumlah siklusnya (jadi inilah mengapa ia berbeda dari jumlah inversi).

domotorp

Apakah mudah untuk melihat bagaimana A dapat menghitung sedikit dari inputnya menggunakan B yang mana yang dapat menghitung paritas? Saya melihat bagaimana A dan B mengetahui jumlah siklus "di dalam bagian mereka". Tetapi bagaimana mereka menemukan paritas dari siklus "persimpangan"?

László Kozma

@laszlo: Misalkan input A adalah sesuatu seperti 1-> 7, 2-> 5, 3-> 8, 4-> 6. Ini memiliki jumlah inversi yang sama dengan 1-> 5, 2-> 6, 3-> 8, 4-> 7. Secara umum, B tahu nomor berapa yang dipetakan. Menggunakan jumlah inversi genap, A dapat mengubah angka-angka ini menjadi urutan yang meningkat, kecuali mungkin untuk dua yang terakhir. Hubungan dari dua angka terakhir ini adalah bit yang ia kirimkan.

domotorp

@ domotor: pertanyaan lanjutan - jika A mendapat

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

$a_1, \dots, a_n$ , B mendapat

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

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

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

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

a

$a$ dari

[3 n]

$[3n]$ , bisakah mereka membangun paritas dengan

o (n)

$o(n)$ potongan komunikasi?

László Kozma