Edytuj odległość między dwiema partycjami

Mam dwie partycje $[1 \ldots n]$ i szukam odległości edycji między nimi.

W ten sposób chcę znaleźć minimalną liczbę pojedynczych przejść węzła do innej grupy, które są niezbędne do przejścia z partycji A na partycję B.

Na przykład odległość od {0 1} {2 3} {4}do {0} {1} {2 3 4}wynosi dwa

Po przeszukaniu natknąłem się na ten artykuł, ale a) nie jestem pewien, czy uwzględniają kolejność grup (coś, co mnie nie obchodzi) w ich odległości, b) nie jestem pewien, jak to działa, c) Brak referencji.

Każda pomoc doceniona

Problem ten można przekształcić w problem przypisania , znany również jako problem maksymalnego ważenia dwustronnego dopasowania.

Zauważ najpierw, że odległość edycji jest równa liczbie elementów, które należy zmienić z jednego zestawu na inny. Jest to równa całkowitej liczbie elementów minus liczba elementów, których nie trzeba zmieniać. Znalezienie minimalnej liczby elementów, które się nie zmieniają, jest równoważne znalezieniu maksymalnej liczby wierzchołków, które się nie zmieniają.

Niech a B = { B 1 , B 2 , . . . , B l } się partycje [ 1 , 2 , . . . , n ] . Również bez utraty ogólności niech k ≥ l (dozwolone, ponieważ e d i $A = \{ A_1, A_2, ..., A_k \}$$B = \{ B_1, B_2, ..., B_l \}$$[1, 2, ..., n]$$k \ge l$ ). Pozwól B l + 1 , B l + 2 , ..., B k wszyscy być zbiorem pustym. Zatem maksymalna liczba wierzchołków, które się nie zmieniają to:$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)} |$

gdzie jest permutacją [ 1 , 2 , . . . , k ] .$f$$[1, 2, ..., k]$

To jest właśnie problem przypisania gdzie wierzchołki są 1 , ..., k , B 1 , ..., B k a krawędzie są pary ( I , B j ) o masie | A i ∩ B j | . Można to rozwiązać za pomocą czasu 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|)$

Spójrz na plik PDF tego artykułu

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

Sądzę, że definicja odległości edycji jest dokładnie tym, czego potrzebujesz. Partycja „referencyjna” byłaby (dowolną) jedną z twoich dwóch partycji, druga byłaby po prostu drugą. Zawiera również odpowiednie cytaty.

Najlepiej, Rob

Zepsuty pomysł na niedzielny poranek, który może, ale nie musi być poprawny:

Wlog, niech będzie partycją z większą liczbą zestawów, P 2 drugą. Najpierw przypisz parami różne nazwy n 1 ( S ) ∈ Σ do swoich zestawów P 1 . Następnie znajdź najlepszą nazwę n 2 ( S ) dla zestawów P 2 według następujących zasad:$P_1$$P_2$$n_1(S) \in \Sigma$$P_1$$n_2(S)$$P_2$

• do S ∈ P 2 z S ∩ S " ilość wśród wszystkich S ' ∈ P 1 ; wybierz ten, który powoduje najmniej konfliktów, jeśli możliwych jest wiele wyborów.$n_2(S) := n_1(S')$$S \in P_2$$S \cap S'$$S' \in P_1$
• Jeśli teraz dla niektórych S ≠ S ′ , przypisz ten, który dzieli mniej elementów z S ″ , n 1 ( S ″ ) = n 2 ( S ) , nazwa zestawu w P 1 dzieli ten drugi co do wielkości element, tzn. konkuruje o nazwę tego zestawu.$n_2(S) = n_2(S')$$S \neq S'$$S'', n_1(S'') = n_2(S)$$P_1$
• Jeśli poprzedniej reguły nie można zastosować, sprawdź oba zestawy, czy mogą konkurować o nazwy innych zestawów, z którymi dzieli mniej elementów (mogą nadal mieć więcej elementów z niektórych niż zestawy, którym przypisano jej nazwę !). Jeśli tak, przypisz tę nazwę do S , S ′, który dzieli więcej elementów z odpowiednim zestawem, o którego nazwę mogą konkurować; drugi zachowuje wcześniej sprzeczną nazwę.$S'' \in P_1$$S, S'$
• Powtarzaj tę procedurę, aż wszystkie konflikty zostaną rozwiązane. Ponieważ nie ma mniej zestawów niż P 2 , jest wystarczająco dużo nazw.$P_1$$P_2$

Teraz możesz wziąć pod uwagę ciągi bitowe elementów piszących na partycjach, tj. i w 2 = n 2 ( 1 ) ⋅ ⋯ ⋅ n 2 ( n ) ( z n j ( i ) = n j ( S ) , i ∈ S ∈ P $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$ ). Następnie pożądana ilość to$d_H(w_1, w_2)$