Menemukan anagram yang menarik

Katakan bahwa dan adalah dua string dengan panjang yang sama. Sebuah anagramming dari dua string adalah pemetaan bijektif sehingga untuk setiap .b 1 b 2 ... b n p : [ 1 ... n ] → [ 1 ... n ] a i = b p ( i )$a_1a_2\ldots a_n$$b_1b_2\ldots b_n$$p:[1\ldots n]\to[1\ldots n]$$a_i = b_{p(i)}$$i$

Mungkin ada lebih dari satu anagram untuk pasangan string yang sama. Misalnya, jika `abcab` dan kami memiliki dan , antara lain.b = p 1 [ 1 , 2 , 3 , 4 , 5 ] → [ 4 , 5 , 1 , 2 , 3 ] p 2 [ 1 , 2 , 3 , 4 , 5 ] → [ 2 , 5 , 1 , 4 , 3 $a=$$b=$cabab$p_1[1,2,3,4,5]\to[4,5,1,2,3]$$p_2[1,2,3,4,5] \to [2,5,1,4,3]$

Kita akan mengatakan bahwa bobot dari anagram adalah jumlah potongan yang harus dibuat dalam string pertama untuk mendapatkan potongan yang dapat disusun ulang untuk mendapatkan string kedua. Secara formal, ini jumlah nilai yang . Artinya, itu adalah jumlah titik di mana tidak tidak meningkat persis 1.Untuk contoh, dan , karena pemotongan sekali, ke dalam potongan dan , dan pemotongan empat kali, menjadi lima bongkahan.p i ∈ [ 1 … n - 1 ] p ( i ) + 1 ≠ p ( i + 1 ) $w(p)$$p$$i\in[1\ldots n-1]$$p(i)+1\ne p(i+1)$$p$w ( p 2 ) = 4 p 1 p $w(p_1) = 1$$w(p_2) = 4$$p_1$1234512345$p_2$12345

Misalkan ada anagram untuk dua string dan . Maka setidaknya satu anagram harus memiliki bobot paling sedikit. Katakanlah ini yang paling ringan . (Mungkin ada beberapa anagram yang paling ringan; saya tidak peduli karena saya hanya tertarik pada bobotnya.)$a$$b$

Pertanyaan

Saya menginginkan algoritma yang, mengingat dua string yang ada anagram, efisien menghasilkan berat yang tepat dari anagram yang paling ringan dari dua string. Tidak apa-apa jika algoritme juga menghasilkan anagram paling ringan, tetapi tidak perlu.

Ini adalah masalah yang cukup sederhana untuk menghasilkan semua anagram dan menimbangnya, tetapi mungkin ada banyak, jadi saya lebih suka metode yang menemukan anagram cahaya secara langsung.

Motivasi

Alasan masalah ini menarik adalah sebagai berikut. Sangat mudah untuk membuat komputer mencari kamus dan menemukan anagram, pasangan kata yang berisi huruf yang persis sama. Tetapi banyak dari anagram yang dihasilkan tidak menarik. Misalnya, contoh terpanjang yang dapat ditemukan dalam Kamus Internasional Kedua Webster adalah:

cholecystoduodenostomy
duodenocholecystostomy

Masalahnya harus jelas: ini tidak menarik karena mereka mengakui anagramming sangat ringan yang hanya pertukaran tersebut cholecysto, duedenodan stomybagian, untuk berat 2. Di sisi lain, contoh yang lebih pendek ini jauh lebih mengejutkan dan menarik:

penampang garis pantai

Di sini anagram yang paling ringan memiliki bobot 8.

Saya memiliki program yang menggunakan metode ini untuk menemukan anagram yang menarik, yaitu yang memiliki semua anagram berat. Tetapi ia melakukan ini dengan menghasilkan dan menimbang semua kemungkinan anagram, yang lambat.

Masalah ini dikenal sebagai "masalah partisi string umum minimum." (Lebih tepatnya, jawaban dalam masalah partisi string umum minimum sama dengan jawaban dalam masalah Anda ditambah 1.) Sayangnya, ini adalah NP-hard, bahkan dengan batasan yang setiap huruf muncul paling banyak dua kali di setiap string input, seperti yang dibuktikan oleh Goldstein, Kilman, dan Zheng [GKZ05]. Ini berarti bahwa tidak ada algoritma waktu polinomial yang ada kecuali P = NP. (Tentu saja, jika setiap huruf muncul paling banyak satu kali, maka masalahnya sepele karena hanya ada satu anagram.)

Di sisi positif, penulis yang sama [GKZ05] memberikan algoritma perkiraan polinomial waktu 1,1037 di bawah batasan yang sama. ("Algoritma aproksimasi 1.1037- " berarti suatu algoritma yang tidak dapat menampilkan jawaban yang benar A tetapi dijamin menghasilkan nilai B sehingga A ≤ B ≤ 1,1037 A. ) Mereka juga memberikan algoritma aproksimasi 4 waktu linier di bawah pembatasan yang lebih lemah bahwa setiap huruf muncul paling banyak tiga kali di setiap string input.

[GKZ05] Avraham Goldstein, Petr Kolman, dan Jie Zheng. Masalah partisi string umum minimum: Kekerasan dan perkiraan. Jurnal Elektronik Kombinatorik , 12, artikel R50, 2005. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50

Ini adalah kelanjutan dari jawaban Tsuyoshi Ito di atas , merangkum bagian paling relevan dari makalah GKZ05 yang dikutipnya.

Makalah ini membuktikan pengurangan masalah Maximal Independent Set ( MIS ). Buatlah grafik yang simpul adalah pasangan ( i , j ) sehingga a i = b j dan sebuah i + 1 = b j + 1 . Hubungkan simpul ( i , j ) dan ( k , ℓ ) (di mana saya ≤ k ) dengan tepi setiap kali tidak mungkin bahwa anagram dapat memetakan semua $G$$(i, j)$$a_i = b_j$$a_{i+1} = b_{j+1}$$(i, j)$$(k, \ell)$$i≤k$ dan i + 1 ↦ j + 1 dan k ↦ ℓ dan k + 1 ↦ ℓ + 1 . Ini mudah dideteksi; pemetaan seperti itu tidak mungkin terjadi jika salah satu dari yang berikut ini berlaku:$i\mapsto j$$i+1\mapsto j+1$$k\mapsto\ell$$k+1\mapsto\ell+1$

1. dan j ≠ $i=k$$j\ne\ell$
2. dan j + 1 ≠ $i+1=k$$j+1\ne\ell$
3. dan { j , j + 1 } terpisah dari { ℓ , ℓ + 1 $i+1<k$$\{j, j+1\}$$\{\ell, \ell+1\}$

Mengatakan grafik yang dihasilkan memiliki seperangkat independen maksimal ukuran s . Maka berat anagram minimum adalah n - s - 1 , di mana n adalah panjang string a dan b . (Kebalikannya berlaku juga: anagram berat rendah diterjemahkan langsung ke MIS besar untuk G. Untuk detailnya, lihat hal. 4–5 dari makalah.)$G$$s$$n-s-1$$n$$a$$b$$G$

yttrioustouristyouriououriri$s=2$y|t|t|ri|ou|st|ou|ri|s|t|y

Di sisi lain, pertimbangkan deraterdan treader. Kali ini grafik memiliki tiga simpul:

1. DErater + treaDEr
2. dERater + treadER
3. deratER + treadER

$s=2$der|a|t|e|rt|r|e|a|der

Itu tidak mencakup algoritma yang tepat yang ada dalam pikiran Anda (yang dijawab oleh Tsuyoshi Ito ), tetapi mencoba untuk mendapatkan masalah mendasar dalam menemukan anagram "menarik" ...

Pikiran pertama saya adalah untuk menggunakan beberapa variasi pada jarak sunting, di mana perubahan atom tertimbang menurut "ketertarikan" mereka daripada bobot "kesulitan" atau "kebingungan" yang biasa. Tentu saja, tampaknya tidak mungkin bahwa Anda dapat secara efisien menyandikan transformasi yang sangat menarik dengan cara ini, karena mereka cenderung non-lokal dan karenanya mengalami masalah MIS lengkap NP, dll.

Jadi, pemikiran kedua adalah membangun keberpihakan huruf-ke-huruf di antara kata-kata (à la machine translation alignment), dan kemudian untuk menilai keberpihakan itu sendiri untuk "ketertarikan" (misalnya, menghitung keberpihakan yang mengambil huruf yang berdekatan dengan non- huruf-huruf yang berdekatan, atau berapa banyak keberpihakan yang dilewati oleh setiap penyelarasan, dll; dan kemudian gabungkan semuanya melalui model loglinear atau semacamnya).

Gagasan ketiga adalah sepenuhnya mengabaikan melihat struktur anagram itu sendiri, dan sebaliknya melihat semantik kata-kata itu. Seringkali yang membuat anagram "menarik" adalah ketidaksesuaian antara makna kata-kata yang terlibat. Jadi cobalah sesuatu seperti menghitung jarak mereka di WordNet, atau yang serupa.

Masalahnya dapat diutarakan dalam hal kelompok permutasi .

Sekarang grup permutasi berisi semua "anagram move", baik primitif (menukar dua huruf) dan gabungan dari urutan gerakan primitif. Tampaknya Anda hanya tertarik pada sebagian dari permutasi yang mungkin. Saya akan mencoba untuk mendefinisikan ini.

Pertama, ingatkan notasi untuk permutasi, yaitu, yang disebut notasi siklus :

• $()$
• $(1)$
• $(12)$
• $(123)$
• dan jadi satu

'Siklus' sederhana ini disusun untuk menggambarkan permutasi yang lebih kompleks.

$n$

• $(12)$
• $(a\ b)(a+1\ b+1)$$a>0$$b<a+1$$b+1\le n$
• ...
• $(a\ b)(a+1\ b+1)\cdots(a+i-1\ b+i-1)$$a>0$$a+i-1\le b$$b+i-1\le n$

Bergerak ini membentuk dasar untuk algoritma Anda. Yang Anda minati adalah menemukan urutan terkecil dari gerakan ini untuk berpindah dari satu kata ke kata berikutnya.

Saya tidak tahu algoritma apa pun untuk menghitung ini, selain dari pencarian brute force, tapi setidaknya sekarang ada deskripsi yang lebih jelas (saya harap) tentang apa gerakan primitif itu. (Dan mungkin beberapa teori grup di antara kita dapat menunjuk ke algoritma yang sesuai.)

Untuk cholecystoduodenostomy / duodenocholecystostome, saya perhatikan bahwa jika Anda menetapkan angka untuk setiap karakter yang menggambarkan berapa banyak itu dipindahkan sebagai delta, Anda akan memiliki beberapa hal seperti 7 7, lalu 8 -7, lalu 6 0. Itu tidak benar karena beberapa karakter mungkin telah diulang (yang kedua c hanya bergerak maju 2, tidak mundur 7) dll tetapi masih sangat "run length encodable" karena Anda melihat delta yang sama secara berurutan.

Bandingkan dengan garis pantai / bagian, di mana Anda melihat sesuatu seperti (+2) (+5) (+5) (- 3) (- 1) (+ 3) .... apalagi "run length encodable".

Mungkin keacakan dari delta bisa memberi Anda "skor" seberapa menarik anagram itu?