Edit distance between two partitions 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 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
This problem can be transformed into the 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.