<p>Look at this paper's PDF</p>

<p><a href="http://www.ploscompbiol.org/article/info:doi/10.1371/journal.pcbi.0030160" rel="nofollow">http://www.ploscompbiol.org/article/info:doi/10.1371/journal.pcbi.0030160</a></p>

<p>The definition of edit distance in there is exactly what you need I think. The 'reference' partition would be (an arbitrary) one of your two partitions, the other would simply be the other one. Also contains relevant citations.</p>

<p>Best,
Rob</p>

CC BY-SA 3.0
2011-08-31T12:58:04.007Z
Thanks Rob.  However, unless I am missing something, this is an edit distance defined in terms of split-merge moves.  These are well studied and as the paper points out, the variation of information is a information theoretic measure of this.  I am interested however, in single element move transitions.
zenna
CC BY-SA 3.0
2011-08-30T08:55:51.790Z
2011-08-30T08:55:51.790Z
Rob
<p>Cranky Sunday morning idea that might or might not be correct: </p>

<p>Wlog, let $P_1$ be the partition with more sets, $P_2$ the other. First, assign pairwise different names $n_1(S) \in \Sigma$ to your sets $P_1$. Then, find a best naming $n_2(S)$ for the sets $P_2$ by the following rules:</p>

<ul>
<li>$n_2(S) := n_1(S&#39;)$ for $S \in P_2$ with $S \cap S&#39;$ maximal amongst all $S&#39; \in P_1$; pick the one creating the least conflicts if multiple choices are possible.</li>
<li>If now $n_2(S) = n_2(S&#39;)$ for some $S \neq S&#39;$, assign the one that shares less elements with $S&#39;&#39;, n_1(S&#39;&#39;) = n_2(S)$, the name of the set in $P_1$ it shares the second most elements with, i.e. have it compete for that set's name.</li>
<li>If the former rule can not be applied, check for both sets wether they can compete for the name of other sets they share less elements with (they might still have more elements from some $S&#39;&#39; \in P_1$ than the sets that got assigned its name!). If so, assign that name to the one of $S, S&#39;$ that shares more elements with the respective set whose name they can compete for; the other keeps the formerly conflicting name.</li>
<li>Iterate this procedure until all conflicts are resolved. Since $P_1$ does not have less sets than $P_2$, there are enough names.</li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2011-05-15T09:59:52.007Z
2011-05-15T09:59:52.007Z
Raphael
<p>This problem can be transformed into the <a href="http://en.wikipedia.org/wiki/Assignment_problem">assignment problem</a>, also known as maximum weighted bipartite matching problem.</p>

<p>Note first that the edit distance equals the number of elements which need to change from one set to another.  This equals the total number of elements minus the number of elements which do not need to change.  So finding the minimum number of elements which do not change is equivalent to finding the maximum number of vertices that do not change.</p>

<p>Let $A = \{ A_1, A_2, ..., A_k \}$ and $B = \{ B_1, B_2, ..., B_l \}$ be partitions of $[1, 2, ..., n]$.  Also, without loss of generality, let $k \ge l$ (allowed because $edit(A, B) = edit(B, A)$).  Then let $B_{l+1}$, $B_{l+2}$, ..., $B_k$ all be the empty set.  Then the maximum number of vertices that do not change is:</p>

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

<p>where $f$ is a permutation of $[1, 2, ..., k]$.</p>

<p>This is exactly the assignment problem where the vertices are $A_1$, ..., $A_k$, $B_1$, ..., $B_k$ and the edges are pairs $(A_i, B_j)$ with weight $|A_i \cap B_j|$.  This can be solved in $O(|V|^2 \log |V| + |V||E|)$ time.</p>

CC BY-SA 3.0
2011-05-16T03:01:33.223Z
Could you name the algorithm, which gives this time complexity please?
D-503
CC BY-SA 4.0
2019-07-19T16:02:59.777Z
I believe @bbejot is referring to the successive shortest path algorithm (with subroutine Dijkstra's implemented using fibonacci heaps).
Wei
CC BY-SA 4.0
2019-11-12T11:51:28.383Z
It took me a long time to parse this because I'm not a math person, but thank you. I spent a long time searching and this was the only thing I could find that showed how to convert the partition distance problem to the assignment problem -- or to any algorithm that I could call from some a Python library. (The hard part for me has been figuring out how to use scipy.optimize.linear_sum_assignment and then to set up the matrices based on these instructions.)
Sigfried
CC BY-SA 4.0
2019-11-12T18:00:20.860Z
I needed to make the weights negative. Otherwise scipy.optimize.linear_sum_assignment gives me 0 for everything.
Sigfried
CC BY-SA 4.0
2020-08-04T19:27:01.387Z
In case anyone is still looking, I believe the Hungarian algorithm is the best in terms of complexity for the bipartite matching problem. It's what scipy.optimize.linear_sum_assignment uses. https://en.wikipedia.org/wiki/Hungarian_algorithm
gdavtor
CC BY-SA 3.0
2011-05-15T04:05:27.257Z
2011-05-15T04:05:27.257Z
bbejot
<p>I have two partitions of $[1 \ldots n]$ and am looking for the edit distance between them. </p>

<p>By this, I want to find the minimal number of single transitions of a node into a different group that are necessary to go from partition A to partition B.</p>

<p>For example the distance from <code>{0 1} {2 3} {4}</code> into <code>{0} {1} {2 3 4}</code> would be two</p>

<p>After searching I came across <a href="http://www.cs.washington.edu/research/edtech/publications/daa05-cardsort.pdf">this</a> paper, but a) I am not sure if they are taking into account the ordering of the groups (something I don't care about) in their distance b) I am not sure how it works and c) There are no references.</p>

<p>Any help appreciated</p>

CC BY-SA 3.0
2011-05-14T05:18:34.160Z
What would you consider the distance to be between {0 1 2 3} and {0 1} {2 3} ? Would it be 2 ? Secondly, I don't see why "graphs" come into the picture at all. It sounds like you have two partitions of [n] and want to compute a distance between them.
Suresh Venkat
CC BY-SA 3.0
2011-05-14T11:36:33.313Z
Yes, it would be two.  Indeed these are set partitions on the nodes of a graph (i.e. a graph partition).  This is likely not important to the solution, but this is the problem I am trying to solve, hence why I mentioned it.
zenna
CC BY-SA 3.0
2011-05-14T20:57:16.760Z
If the graph is irrelevant, please remove all references to "graphs" and "nodes" from your question; it does not help, it distracts.
Jukka Suomela
CC BY-SA 3.0
2011-05-17T17:26:47.783Z
Can't the edit distance be defined in terms of the distance on the partition lattice?
Tegiri Nenashi
CC BY-SA 3.0
2011-08-31T10:16:13.767Z
@Tegiri - It is indeed the geodesic distance on the lattice of partititons.  Unfortunately computing that lattice for any set of cardinality much greater than 10 is intractable.
zenna
<ds.algorithms><edit-distance><lattice>
Edit distance between two partitions
zenna
# Edit distance between two partitions

(Asked by: username_0 on 2011-05-13)

I have two partitions of $[1 \ldots n]$ and am looking for the edit distance between them.

By this, I want to find the minimal number of single transitions of a node into a different group that are necessary to go from partition A to partition B.

For example the distance from `{0 1} {2 3} {4}` into `{0} {1} {2 3 4}` would be two

After searching I came across [this](http://www.cs.washington.edu/research/edtech/publications/daa05-cardsort.pdf) paper, but a) I am not sure if they are taking into account the ordering of the groups (something I don't care about) in their distance b) I am not sure how it works and c) There are no references.

Any help appreciated

**Tags:** ds.algorithms, edit-distance, lattice
> **Comments:**
> **username_1**: What would you consider the distance to be between {0 1 2 3} and {0 1} {2 3} ? Would it be 2 ? Secondly, I don't see why "graphs" come into the picture at all. It sounds like you have two partitions of [n] and want to compute a distance between them.  
> **username_0**: Yes, it would be two.  Indeed these are set partitions on the nodes of a graph (i.e. a graph partition).  This is likely not important to the solution, but this is the problem I am trying to solve, hence why I mentioned it.  
> **username_2**: If the graph is irrelevant, please remove all references to "graphs" and "nodes" from your question; it does not help, it distracts.  
> **username_3**: Can't the edit distance be defined in terms of the distance on the partition lattice?  
> **username_0**: @Tegiri - It is indeed the geodesic distance on the lattice of partititons.  Unfortunately computing that lattice for any set of cardinality much greater than 10 is intractable.  

---

## 3 answers

### Answer by username_6 on 2011-05-15. Score: 21 | Accepted answer

This problem can be transformed into the [assignment problem](http://en.wikipedia.org/wiki/Assignment_problem), also known as maximum weighted bipartite matching problem.

Note first that the edit distance equals the number of elements which need to change from one set to another. This equals the total number of elements minus the number of elements which do not need to change. So finding the minimum number of elements which do not change is equivalent to finding the maximum number of vertices that do not change.

Let $A = \{ A\_1, A\_2, ..., A\_k \}$ and $B = \{ B\_1, B\_2, ..., B\_l \}$ be partitions of $[1, 2, ..., n]$. Also, without loss of generality, let $k \ge l$ (allowed because $edit(A, B) = edit(B, A)$). Then let $B\_{l+1}$, $B\_{l+2}$, ..., $B\_k$ all be the empty set. Then the maximum number of vertices that do not change is:

$\max\_f \sum\_{i=1}^k |A\_i \cap B\_{f(i)} |$

where $f$ is a permutation of $[1, 2, ..., k]$.

This is exactly the assignment problem where the vertices are $A\_1$, ..., $A\_k$, $B\_1$, ..., $B\_k$ and the edges are pairs $(A\_i, B\_j)$ with weight $|A\_i \cap B\_j|$. This can be solved in $O(|V|^2 \log |V| + |V||E|)$ time.

> **Comments:**
> **username_7**: Could you name the algorithm, which gives this time complexity please?  
> **username_8**: I believe @bbejot is referring to the successive shortest path algorithm (with subroutine Dijkstra's implemented using fibonacci heaps).  
> **username_9**: It took me a long time to parse this because I'm not a math person, but thank you. I spent a long time searching and this was the only thing I could find that showed how to convert the partition distance problem to the assignment problem -- or to any algorithm that I could call from some a Python library. (The hard part for me has been figuring out how to use scipy.optimize.linear_sum_assignment and then to set up the matrices based on these instructions.)  
> **username_9**: I needed to make the weights negative. Otherwise scipy.optimize.linear_sum_assignment gives me 0 for everything.  
> **username_10**: In case anyone is still looking, I believe the Hungarian algorithm is the best in terms of complexity for the bipartite matching problem. It's what scipy.optimize.linear_sum_assignment uses. https://en.wikipedia.org/wiki/Hungarian_algorithm  

---

### Answer by username_4 on 2011-08-30. Score: 2

Look at this paper's PDF

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

The definition of edit distance in there is exactly what you need I think. The 'reference' partition would be (an arbitrary) one of your two partitions, the other would simply be the other one. Also contains relevant citations.

Best,
Rob

> **Comments:**
> **username_0**: Thanks Rob.  However, unless I am missing something, this is an edit distance defined in terms of split-merge moves.  These are well studied and as the paper points out, the variation of information is a information theoretic measure of this.  I am interested however, in single element move transitions.  

---

### Answer by username_5 on 2011-05-15. Score: 1

Cranky Sunday morning idea that might or might not be correct:

Wlog, let $P\_1$ be the partition with more sets, $P\_2$ the other. First, assign pairwise different names $n\_1(S) \in \Sigma$ to your sets $P\_1$. Then, find a best naming $n\_2(S)$ for the sets $P\_2$ by the following rules:

* $n\_2(S) := n\_1(S')$ for $S \in P\_2$ with $S \cap S'$ maximal amongst all $S' \in P\_1$; pick the one creating the least conflicts if multiple choices are possible.
* If now $n\_2(S) = n\_2(S')$ for some $S \neq S'$, assign the one that shares less elements with $S'', n\_1(S'') = n\_2(S)$, the name of the set in $P\_1$ it shares the second most elements with, i.e. have it compete for that set's name.
* If the former rule can not be applied, check for both sets wether they can compete for the name of other sets they share less elements with (they might still have more elements from some $S'' \in P\_1$ than the sets that got assigned its name!). If so, assign that name to the one of $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.


---

