Kompleksitas menerapkan permutasi di tempat

27

Yang mengejutkan saya, saya tidak dapat menemukan makalah tentang ini - mungkin mencari kata kunci yang salah.

Jadi, kita punya array apa saja, dan fungsi pada indeksnya; adalah permutasi. $f$ $f$

Bagaimana kita menyusun ulang susunan menurut $f$ dengan memori dan runtime sedekat mungkin dengan $O(1)$ dan $O(n)$ ?

Adakah kondisi tambahan saat tugas ini menjadi lebih mudah? Misal ketika kita secara eksplisit mengetahui fungsi $g$ adalah kebalikan dari $f$ ?

Saya tahu suatu algoritma yang mengikuti siklus dan melintasi siklus untuk setiap indeks untuk memeriksa apakah itu yang paling sedikit dalam siklusnya, tetapi sekali lagi, ia memiliki waktu proses terburuk $O(n^2)$ , meskipun rata-rata tampaknya berperilaku lebih baik. ...

ds.algorithms co.combinatorics permutations Jkff
sumber

Pengamatan yang mudah: Jika tidak hanya array item tetapi juga array yang berisi fungsi f dapat ditulis, maka mudah untuk melakukan tugas dalam waktu O (n) menggunakan O (1) register integer (masing-masing panjang O ( log n) bit) dan ruang tambahan untuk satu item dengan hanya mengikuti setiap siklus. Tetapi ini tidak berfungsi jika fungsi f diberikan pada penyimpanan read-only (atau f diberikan hanya sebagai oracle), yang menurut saya merupakan asumsi dalam pertanyaan ini.

Tsuyoshi Ito

23

Fich et al. 1995 :

O (n \log n)

$O(n \log n)$ waktu,

O (\log n)

$O(\log n)$ spasi. Ini juga membahas beberapa kasus khusus.

Jukka Suomela

Ya, saya berasumsi kita memiliki f sebagai oracle.

jkff

3

@JukkaSuomela, Anda harus membuatnya menjadi jawaban. Juga, mengingat bahwa

f

$f$ adalah permutasi acak, argumen entropi sederhana menghasilkan

O (n \log n)

$O( n \log n)$ ruang dan / atau waktu, jadi saya akan terkejut jika Anda bisa melakukan lebih baik daripada

O (n \log n)

$O(n \log n)$ dalam ruang dan waktu .

user834

4

Opsi 0: Permuting In Place (1995) oleh Faith E. Fich, J. Ian Munro, Patricio V. Poblete waktu spasi. $O(n \log n)$ $O( \log^{2} n )$

Opsi 1: Cheat dengan mengompresi permutasi Anda ke struktur data yang ringkas, lihat Munro http://www.itu.dk/people/ssrao/icalp03-a.pdf .

Opsi 2: Gunakan dekomposisi siklus utama untuk menyimpan perm secara ringkas dan gunakan ruang ekstra itu untuk menipu http://oeis.org/A186202

Opsi 3: Melacak indeks terbesar dari setiap siklus yang dimanipulasi. Untuk setiap iterasi, gunakan indeks tak terlihat terbesar untuk memindahkan segala sesuatu dalam siklusnya satu per satu. Jika itu menyentuh indeks terlihat membatalkan semua yang berhasil karena siklus telah dimanipulasi. waktu, spasi. $O(n^2)$ $O(\#\text{cycles} * \log n)$

Opsi 4: Melacak indeks terbesar dari setiap siklus yang dimanipulasi, tetapi hanya melakukannya dalam kumpulan panjang siklus yang berbeda. Untuk setiap iterasi, gunakan indeks tak terlihat terbesar untuk memindahkan semua yang ada dalam siklusnya satu per satu. Jika itu menyentuh indeks terlihat membatalkan semua yang berhasil karena siklus sudah dimanipulasi. waktu, spasi. $O(n^2 * \text{distinct}\_\text{cycle}\_\text{lengths})$ $O((\#\text{cycles}\_\text{with}\_\text{same}\_\text{size}) * \log n)$

Opsi 5: Dari makalah yang sama oleh Munro sebagai Opsi 0, Untuk putar siklus jika adalah indeks terbesar dalam siklus itu. waktu dan ruang. $i = 1 .. n$ $p(i)$ $i$ $O(n^2)$ $O(\log n)$

Chad Brewbaker
sumber

metode kompresi mungkin tidak menghemat ruang secara umum: ruang kasus terburuk untuk menyimpan permutasi adalah . 3, 4, dan 5 tampaknya secara umum sama buruknya dengan solusi yang sudah diketahui OP, atau solusi oleh Fich, Munro, dan Poblete. Dan solusi itu sudah ditunjukkan oleh @Jukka

n \log n

$n\log n$

Sasho Nikolov

# 5 menggunakan lebih sedikit ruang daripada # 0 oleh faktor log (n).

Chad Brewbaker

1

Jika Anda menggunakan representasi siklus permutasi, Anda memerlukan 1 elemen array tambahan untuk menyimpan item yang sedang diijinkan dan Anda dapat menjalankan siklus di operasi O (N) yang lebih buruk.

Phil
sumber

2

jkff sudah mengatakan dia tahu algoritma mengikuti siklus, jadi dia jelas ingin permutasi itu sendiri diperlakukan sebagai (dekat dengan) kotak hitam. Seperti yang ia tunjukkan dalam pertanyaan, mengubah dari (hampir) kotak hitam ke representasi siklus bisa memakan waktu O (n ^ 2) waktu.

Joshua Grochow

Kotak hitam p (i) baik-baik saja. Anda hanya berputar-putar sampai Anda kembali ke i. Masalahnya adalah salah satu kompleksitas Kolomogorov untuk menyimpan daftar item yang telah diperbarui sehingga Anda tidak menggilirnya berulang kali. Munro punya batasan untuk itu. itu.dk/people/ssrao/icalp03-a.pdf

Chad Brewbaker

-2

Setiap permutasi dari item N dapat dikonversi ke permutasi lainnya menggunakan N-1 atau lebih sedikit pertukaran. Kasus terburuk untuk metode ini dapat memerlukan panggilan O (n ^ 2) ke oracle Anda, F (). Mulai dari posisi paling tidak. Biarkan x menjadi posisi yang saat ini kami tukar.

Jika F (x)> = x maka tukar posisi x dan F (x). Selain itu, kita harus menemukan di mana item yang berada di posisi F (x) saat ini ada dalam daftar. Kita bisa melakukan ini dengan iterasi berikut. Biarkan y = F (x). Lakukan sampai y> = x: y = F (y): End Do. Sekarang tukar posisi x dan y.

Russell Easterly
sumber

3

OP sudah mengatakan dia tahu bagaimana melakukannya dalam waktu .

O (n^{2})

$O(n^2)$

Jukka Suomela

Maaf. Saya baru di grup ini. Saya suka metode ini karena kesederhanaannya. Terkadang saya menemukan kesederhanaan lebih cepat daripada efisiensi. Saya tahu metode lain yang membutuhkan langkah-langkah O (n), tetapi ruang O (nlogn).

Russell Easterly

1

Russell, bahkan mengalokasikan dan memusatkan O (n log n) ruang sudah O (n log n), maksud Anda ke arah lain?

jkff

Anda tidak benar-benar memiliki alokasi dan nol ruang. Ide dasarnya adalah ketika F (x)> x kita perlu mengingat di mana kita meletakkan item pada posisi x. Untuk n yang sangat besar, saya akan menggunakan database dan hanya menyimpan catatan di mana item x dipindahkan. Catatan dapat dihapus ketika x sampai ke lokasi akhirnya.

Russell Easterly

1

Tetapi mengapa Anda kemudian mengatakan bahwa itu membutuhkan ruang O (n log n)?

jkff

-2

Metode ini menggunakan kebalikan dari F dan membutuhkan n bit penyimpanan. Jika x adalah posisi item dalam array asli, misalkan G (x) menjadi posisi item dalam array yang diurutkan. Biarkan B menjadi array n bit. Setel semua n bit B ke 0.

UNTUK x = 1 hingga n-1: JIKA B (x) == 0 KEMUDIAN: y = G (x): LAKUKAN SAMPAI x == y: Tukar posisi x dan y: B (y) = 1: y = G ( y): LOOP: ENDIF: BERIKUTNYA X

Metode ini terus menukar item saat ini di posisi x ke posisi akhir item. Loop dalam berakhir ketika item yang benar ditukar ke posisi x. Karena setiap swap memindahkan setidaknya satu item ke posisi akhir item, loop Do dalam tidak dapat mengeluarkan lebih dari n-1 kali selama menjalankan. Saya pikir metode ini adalah O (n) waktu dan ruang.

Russell Easterly
sumber

2

Apakah Anda sudah melihat kertasnya? Dua algoritma yang Anda daftarkan di sini adalah dua yang "jelas". Makalah ini memiliki yang kurang jelas dengan pertukaran ruang-waktu yang berbeda, khususnya jauh lebih sedikit ruang.

Yuval Filmus

Kompleksitas menerapkan permutasi di tempat

Jawaban: