Timeline for Counting number of swaps to make two strings equal in linear time
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 22, 2021 at 12:54 | vote | accept | MeyCJey | ||
| Dec 21, 2021 at 11:24 | answer | added | pcpthm | timeline score: 1 | |
| Sep 9, 2021 at 9:40 | history | edited | xskxzr | CC BY-SA 4.0 |
added 33 characters in body
|
| Sep 8, 2021 at 16:02 | comment | added | Lieuwe Vinkhuijzen | The straightforward approach you propose seems to me correct, although I have no proof. ffiw: notice you may assume that the two strings differ on the first element, so you will definitely need to bring the first occurrence of $y[1]$ in $x$ all the way to the front. You might as well do those permutations first. Now we have two strings whose first character is equal, so we consider only $x[2\ldots n]$ and $y[2\ldots n]$. Iterate until $|x|=0$. But I have no proof of my claim that "we might as well do those permutations first". This allows you to both count and perform the permutations. | |
| Sep 8, 2021 at 6:22 | history | edited | MeyCJey | CC BY-SA 4.0 |
deleted 32 characters in body
|
| Aug 30, 2021 at 5:15 | comment | added | MeyCJey | @vonbrand Is "yes" a valid answer? I'm mainly interested in just counting the number of swaps in a string from a constant-sized, but not necessarily binary alphabet. That said, if the sequence of swaps can also be then reconstructed and/or there is some special trick that works only in the case of a binary alphabet and/or we can have an exact analysis that includes alphabet size, I'd be happy (and interested) to see those too :) | |
| Aug 30, 2021 at 1:14 | comment | added | vonbrand | Do yu want to compute the number of swaps or execute the swaps? Are you sure you can consider very small alphabets (like binary) or is the alphabet size just a parameter "left out"? | |
| Aug 29, 2021 at 11:47 | history | edited | MeyCJey | CC BY-SA 4.0 |
edited body
|
| Aug 29, 2021 at 8:44 | history | edited | MeyCJey | CC BY-SA 4.0 |
added 213 characters in body
|
| S Aug 29, 2021 at 8:34 | review | First questions | |||
| Aug 29, 2021 at 13:42 | |||||
| S Aug 29, 2021 at 8:34 | history | asked | MeyCJey | CC BY-SA 4.0 |