Timeline for Minimum number of transpositions to make two multiset permutations equal
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 15 at 9:04 | comment | added | caduk | I added an answer requiring only basic reasoning on permutations | |
| Jan 14 at 12:53 | history | edited | Luc Guyot | CC BY-SA 4.0 |
Fix typos
|
| Jan 14 at 12:20 | history | edited | Luc Guyot | CC BY-SA 4.0 |
Simplifies the proof of Claim 2 and fixes a couple of typos while doing it
|
| Jan 14 at 11:32 | comment | added | Luc Guyot | @caduk Many thanks for your interest and for sharing your thoughts. A proof that $w(m, n) \ge m(n - 1)$ still eludes me. If you have a simple argument in mind, you may create your own answer. I'll be very glad to read it. | |
| Jan 12 at 14:11 | comment | added | caduk | The minimal number of transpositions is in a decomposition is $n-s$ where is the number of cycle. If we apply a circular shift of $m$ element to the permutation $11...122...2...nn...n$, we easily see that no matter how we partition the permutation in $m$ sets of $n$ distinct elements, the corresponding permutation will have $m$ disjoint cycles, hence requiring $mn-m$ transpositions | |
| Jan 4 at 18:49 | history | edited | Luc Guyot | CC BY-SA 4.0 |
Adds credits for Kenji Mano, author of the original problem and of the first contribution
|
| Jan 4 at 1:42 | history | edited | Luc Guyot | CC BY-SA 4.0 |
One more typo
|
| Jan 4 at 1:34 | history | answered | Luc Guyot | CC BY-SA 4.0 |