Edit jarak antara dua partisi

Saya memiliki dua partisi $[1 \ldots n]$ dan saya mencari jarak sunting di antara mereka.

Dengan ini, saya ingin menemukan jumlah minimal satu transisi dari sebuah node ke grup yang berbeda yang perlu beralih dari partisi A ke partisi B.

Misalnya jarak dari {0 1} {2 3} {4}ke {0} {1} {2 3 4}dua

Setelah mencari saya menemukan makalah ini , tetapi a) Saya tidak yakin apakah mereka mempertimbangkan urutan kelompok (sesuatu yang saya tidak pedulikan) dalam jarak mereka b) Saya tidak yakin bagaimana cara kerjanya dan c) Tidak ada referensi.

Setiap bantuan dihargai

Masalah ini dapat diubah menjadi masalah penugasan , juga dikenal sebagai masalah pencocokan bipartit tertimbang maksimum.

Perhatikan terlebih dahulu bahwa jarak edit sama dengan jumlah elemen yang perlu diubah dari satu set ke set lainnya. Ini sama dengan jumlah total elemen dikurangi jumlah elemen yang tidak perlu diubah. Jadi, menemukan jumlah minimum elemen yang tidak berubah sama dengan menemukan jumlah maksimum simpul yang tidak berubah.

Mari dan B = { B 1 , B 2 , . . . , B l } menjadi partisi dari [ 1 , 2 , . . . , n ] . Juga, tanpa kehilangan keumuman, misalkan k ≥ l (diizinkan karena e d i $A = \{ A_1, A_2, ..., A_k \}$$B = \{ B_1, B_2, ..., B_l \}$$[1, 2, ..., n]$$k \ge l$ ). Lalu biarkan B l + 1 , B l + 2 , ..., B k semua menjadi set kosong. Maka jumlah maksimum simpul yang tidak berubah adalah:$edit(A, B) = edit(B, A)$$B_{l+1}$$B_{l+2}$$B_k$

$\max_f \sum_{i=1}^k |A_i \cap B_{f(i)} |$

di mana adalah permutasi dari [ 1 , 2 , . . . , k ] .$f$$[1, 2, ..., k]$

Ini persis masalah penugasan di mana simpul adalah , ..., A k , B 1 , ..., B k dan ujung-ujungnya berpasangan ( A i , B j ) dengan bobot | A i ∩ B j | . Ini dapat diselesaikan dalam waktu O ( | V | 2 log | V | + | V | | E | ) .$A_1$$A_k$$B_1$$B_k$$(A_i, B_j)$$|A_i \cap B_j|$$O(|V|^2 \log |V| + |V||E|)$

Lihatlah PDF tulisan ini

http://www.ploscompbiol.org/article/info:doi/10.1371/journal.pcbi.0030160

Definisi jarak edit di sana adalah persis apa yang Anda butuhkan saya pikir. Partisi 'referensi' akan (sewenang-wenang) salah satu dari dua partisi Anda, yang lain hanya akan menjadi yang lain. Juga mengandung kutipan yang relevan.

Terbaik, Rob

Gagasan Minggu pagi Cranky yang mungkin atau mungkin tidak benar:

Wlog, misalkan menjadi partisi dengan lebih banyak set, P 2 lainnya. Pertama, tetapkan nama berbeda berpasangan n 1 ( S ) ∈ Σ ke set Anda P 1 . Kemudian, cari penamaan terbaik n 2 ( S ) untuk set P 2 dengan aturan berikut:$P_1$$P_2$$n_1(S) \in \Sigma$$P_1$$n_2(S)$$P_2$

• untuk S ∈ P 2 dengan S ∩ S ′ maksimal di antara semua S ′ ∈ P 1 ; pilih satu yang menciptakan konflik paling sedikit jika beberapa pilihan dimungkinkan.$n_2(S) := n_1(S')$$S \in P_2$$S \cap S'$$S' \in P_1$
• Jika sekarang untuk beberapa S ≠ S ′ , tetapkan elemen yang berbagi lebih sedikit elemen dengan S ″ , n 1 ( S ″ ) = n 2 ( S ) , nama himpunan dalam P 1 ia berbagi elemen terbanyak kedua, yaitu bersaing untuk nama set itu.$n_2(S) = n_2(S')$$S \neq S'$$S'', n_1(S'') = n_2(S)$$P_1$
• Jika aturan sebelumnya tidak dapat diterapkan, periksa kedua set apakah mereka dapat bersaing untuk nama set lain yang mereka miliki elemen lebih sedikit (mereka mungkin masih memiliki lebih banyak elemen dari beberapa daripada set yang mendapat namanya. !). Jika demikian, tetapkan nama itu ke salah satu dari S , S ′ yang membagikan lebih banyak elemen dengan set masing-masing yang namanya dapat mereka lawan; yang lain menyimpan nama yang sebelumnya saling bertentangan.$S'' \in P_1$$S, S'$
• Iterasi prosedur ini sampai semua konflik diselesaikan. Karena tidak memiliki set kurang dari P 2 , ada cukup nama.$P_1$$P_2$

Sekarang, Anda dapat mempertimbangkan string bit elemen Anda dengan partisi mana pun, yaitu dan w 2 = $w_1 = n_1(1) \cdot \dots \cdot n_1(n)$$w_2 = n_2(1) \cdot \dots \cdot n_2(n)$$n_j(i) = n_j(S), i \in S \in P_j$$d_H(w_1, w_2)$