I think this problem should have a known solution, but I wasn't able to find any reference.
Consider a multiset of size $n \cdot m$: it has $n$ elements, and all element multiplicities equal to $m$.
What is the maximum number of transpositions (swaps) needed to make two permutations of the multiset equal, in the worst case?
When $m = 1$ the result is well known and is $n-1$, but what about $m \ge 2$?
The minimum number of transposition in a product decomposition is $n-s$ where $s$ is the number of cycles in the permutation. Lets call it the transposition number.
The problem here is equivalent to finding the smallest number of transpositions to transform a permutation of the multiset to the canonical one, which we will define as $11...122...2...nn...n$.
Lets call a valid labeling a labeling of a permutation using labels $1_1, 1_2, ..., 1_m, 2_1, ..., 2_m,...n_1,...n_m$, so that a $k$ can only get a label $k_i, 1\leq i\leq n$
Our problem becomes equivalent to finding the minimum transposition number over all valid labelings of our permutation where the identity is labeled $\sigma_0 = 1_11_2...1_m2_12_2...2_m...n_1n_2...n_m$.
We do it greedily: Let $\sigma = a_1a_2...a_{nm}$ be the multiset permutation. let $\sigma(a_i)$ be the first valid label not attributed (${a_i}_1$ if no label $a_i$ attributed, then ${a_i}_2$, etc.)
We compute the sequence $u_1 = a_1$, $u_n$ is the element of $\sigma$ at index $\sigma(u_{n-1})$ in $\sigma_0$ until we reach a cycle (that will happen when we meet a value for the second times.
For each element on the cycle only, we set the corresponding label. We iterate until all labels are attributed.
We repeat from an element with no label until every element has a label. At the end, we get a valid labeling. All the cycles find have length less than $n$, so there is more than $m$ cycle, hence transposition number is lower than $mn-m = m(n-1)$
Example: If $\sigma = a_1...a_6 = 323121$ We get the sequence $a_1, a_5, a_3, a_5...$ so we set the labels only for $a_3$ and $a_5$, so we get: $323_112_11$
We start again, from $a_1$ since it still does not have a label yet. We get the sequence $a_1, a_6, a_1, ...$. We set the labels for $a_1$ and $a_6$, so we get: $\sigma = a_1...a_6 = 3_223_112_11_1$
Continuing the process we then get $a_1...a_6 = 3_22_23_11_22_11_1$. We have $3$ cycles so the transposition number is $nm-3 \leq m(n-1)$
We easily verify that any valid labeling of $\sigma = 22...2...nn...n11...1$ induces less than $m$ cycles, so the transposition number will always be $mn-m$.
Example: $2_12_22_31_21_11_3$ induces 2 cycles, and $2_12_22_31_11_21_3$ indices 3 cycles (the maximum)
The question relates to the numbers $H(n, m)$ of the Anand–Dumir–Gupta conjectures solved by Richard Stanley, see e.g. [1] (this MO post set me on this track).
Indeed, we have:
Claim 1. Let $M = \{m \cdot a_1, \dots, m \cdot a_n\}$ be a multiset of size $mn$ consisting of $n$ elements $a_1, \dots, a_n$, each with multiplicity $m$. Let $X = (x_s)_{1 \le s \le mn}$ with $x_s \in \{a_1, \dots, a_n\}$ be a permutation of $M$ and let $\mu = (\mu_{i, j})_{1 \le i, j \le n} \in \mathbb{Z}_{\ge 0}^{n \times n}$ be the matrix defined by $$\mu_{i, j} = \#\left\{s \, \vert \, x_s = a_j,\, im + 1 \le s \le (i + 1)m\right\}.$$ Then the sum of every row and every column of $\mu$ is $m$.
Proof. A straightforward verification.
Note. The integer $H(n, m)$ of the Anand–Dumir–Gupta conjectures is the number of matrices in $\mathbb{Z}_{\ge 0}^{n \times n}$ with constant row and column sums equal to $m$, see [1]. The original distribution problem that motivated [2] is due to Kenji Mano; it was first investigated in [3].
We shall establish the following simple fact:
Claim 2. Let $M$ be a multiset as in Claim 1. Any two permutations of $M$ can be related by means of at most $m(n - 1)$ swaps.
Notation. Let $w(X, Y)$ be the minimum number of swaps required to turn $X$ into $Y$, for $X$ and $Y$ two permutations of $M$ and $M$ as in Claim 1. Let $w(m, n) = \max_{X, Y} w(X, Y)$. Then Claim 2 states that $$w(m, n) \le m(n - 1).$$
Our proof relies on the following straightforward lemma:
Lemma. Let $M$ be as in Claim 1 and let $X$ and $Y$ be two permutations of $M$. Then we have $$w(X \sigma, Y \sigma) = w(X, Y)$$ for every $\sigma \in \text{Sym}(mn)$.
Proof. The key fact is that conjugating a product of $k$ transpositions in $\text{Sym}(mn)$ results in a product of $k$ transpositions.
Proof of Claim 2. Let $X$ be a permutation of $M$. For each $i \in \{1, \dots, n - 1\}$, we need at most $m$ swaps to move the $m$ elements of $X$ equal to $a_i$ so that they occupy the positions from $(i - 1)m + 1$ to $im$. Thus it suffices to apply $m(n - 1)$ swaps to $X$ to turn it into the permutation $$(a_1 \cdots a_1 a_2 \cdots a_2 \cdots a_{n - 1} \cdots a_{n - 1} a_n \cdots a_n).$$ Since $\text{Sym}(mn)$ acts transitively on the permutations of $M$, the result now follows from the above lemma.
It seems now natural to ask:
Question. Is the upper bound of Claim 2 a tight bound? More specifically, does $w(m,n) \ge m(n - 1)$ hold?
In my initial answer, I thought that the following results could be useful. (As of now, it's unclear to me how they could help).
Lemma 1 (Birkhoff-von Neumann Theorem, see [1, Theorem 1.1]). Let $\mu \in \mathbb{Z}_{\ge 0}^{n \times n}$ be a matrix such that the sum of every of its rows and of every of its columns is $m$. Then $\mu$ is a sum of $m$ permutation matrices.
Our strategy is rather naive. It consists in showing that a permutation of $M$ decomposes as a union of $m$ intertwined permutations of $\{a_1, \dots, a_n\}$. This is explained in the next lemma.
Lemma 2. Let $M$ and $X$ be as in Claim 1. Then there are pairwise distinct indices $i_{k, l} \in \{1, \dots, mn\}$ with $k \in \{1, \dots, m\}$ and $l \in \{1, \dots, n \}$ such that
- $i_{k, l} \in [(l - 1)m + 1, lm]$ for every $k$ and every $l$,
- $\{x_{i_{k,l}} \, \vert \, 1 \le l \le n\} = \{a_1, \dots, a_n\}$ for every $k$, i.e., the map $\sigma_k$ defined by $$\sigma_k(a_l) = x_{i_{k, l}}$$ is a permutation of the set $\{a_1, \dots, a_n\}$ for every $k$.
Proof. Apply Claim 1 and Lemma 1: the matrix $\mu = \mu(X)$ is a sum of $m$ permutation matrices. The corresponding permutations are the desired permutations $\sigma_k$. Alternatively, one may resort to Hall's marriage theorem and exhibit the sequences $(i_{k, l})$ directly through induction.
[1] W. Bruns, "Commutative Algebra Arising from the Anand–Dumir–Gupta Conjectures", 2007.
[2] H. Anand, V. Dumir, H. Gupta, "A combinatorial distribution problem", 1966.
[3] M. Kenji, "On the formula ${}_{n!}H_r$", 1961.
