Return to Question

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$, $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$?

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$?

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$, $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$?

Now crossposted at math.stackexchange.

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$, $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$?

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$, $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$?

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$, $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$?

Now crossposted at math.stackexchange.