Редактировать расстояние между двумя перегородками

У меня есть два раздела $[1 \ldots n]$ и я ищу расстояние редактирования между ними.

Этим я хочу найти минимальное количество отдельных переходов узла в другую группу, которые необходимы для перехода из раздела A в раздел B.

Например, расстояние от {0 1} {2 3} {4}в {0} {1} {2 3 4}будет два

После поиска я наткнулся на эту статью, но а) я не уверен, принимают ли они во внимание порядок групп (что меня не интересует) на расстоянии б) я не уверен, как это работает и в) Там нет ссылок.

Любая помощь приветствуется

Эта проблема может быть преобразована в задачу назначения , также известную как проблема максимального взвешенного двудольного соответствия.

Во-первых, обратите внимание, что расстояние редактирования равно количеству элементов, которые необходимо изменить из одного набора в другой. Это равно общему количеству элементов минус количество элементов, которые не нужно менять. Поэтому нахождение минимального количества элементов, которые не меняются, эквивалентно нахождению максимального количества вершин, которые не меняются.

Пусть и В = { B 1 , B 2 , . , , , Б л } разбиения числа [ 1 , 2 , . , , , п ] . Также, без ограничения общности, пусть k ≥ l (допускается, потому что e d i $A = \{ A_1, A_2, ..., A_k \}$$B = \{ B_1, B_2, ..., B_l \}$$[1, 2, ..., n]$$k \ge l$ ). Тогда пусть B l + 1 , B l + 2 , ..., B k все будут пустым множеством. Тогда максимальное количество вершин, которые не меняются:$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)} |$

где является перестановкой [ 1 , 2 , . , , , к ] .$f$$[1, 2, ..., k]$

Это именно та задача присваивания, где вершинами являются , ..., A k , B 1 , ..., B k, а ребра - пары ( A i , B j ) с весом | A i ∩ B j | , Это можно решить за 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|)$

Посмотрите на PDF этой статьи

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

Я думаю, что определение расстояния редактирования там именно то, что вам нужно. Раздел 'reference' будет (произвольным) одним из двух ваших разделов, другой просто будет другим. Также содержит соответствующие цитаты.

Лучше всего, Роб

Капризная идея воскресного утра, которая может быть, а может и не быть правильной:

Wlog, пусть будет разделом с большим количеством множеств, P 2 другой. Сначала назначим попарно разные имена n 1 ( S ) ∈ Σ вашим множествам P 1 . Затем найдите наилучшее наименование n 2 ( S ) для множеств P 2 по следующим правилам:$P_1$$P_2$$n_1(S) \in \Sigma$$P_1$$n_2(S)$$P_2$

• для S ∈ P 2 смаксимальным S ∩ S ′ среди всех S ′ ∈ P 1 ; выберите тот, который создает наименьшее количество конфликтов, если возможны несколько вариантов.$n_2(S) := n_1(S')$$S \in P_2$$S \cap S'$$S' \in P_1$
• $n_2(S) = n_2(S')$$S \neq S'$$S'', n_1(S'') = n_2(S)$$P_1$ он разделяет вторые по величине элементы, то есть, конкурирует ли он за имя этого набора.
• $S'' \in P_1$$S, S'$ that shares more elements with the respective set whose name they can compete for; the other keeps the formerly conflicting name.
• Iterate this procedure until all conflicts are resolved. Since $P_1$ does not have less sets than $P_2$, there are enough names.

Now, you can consider the bit strings of your elements wrt either partition, i.e. $w_1 = n_1(1) \cdot \dots \cdot n_1(n)$ and $w_2 = n_2(1) \cdot \dots \cdot n_2(n)$ (with $n_j(i) = n_j(S), i \in S \in P_j$). Then, the desired quantity is $d_H(w_1, w_2)$, i.e. the Hamming distance between the bit strings.