How to get from string to anagram in fewest number of swaps?
I'm using Python for the backend of this project. I have a string
l1 that is 19 characters long. I have a string l2 that is an anagram of l1 (l2 has the same characters as l1 but shuffled). I want to get from l1 to l2 in the fewest number of steps, the only move allowed is to swap any two letters (they don't have to be adjacent). l1 can have repeated letters. I'm trying to create a function that outputs the swaps the user needs to make to achieve the least possible number, represented as tuples with the indices of the letters the user needs to swap. For example,
I've tried BFS, but I couldn't figure out a way to make it work with repeated letters. It seems quite straightforward, but I can't figure out a way to ensure minimum swaps. Any help would be appreciated.9 Replies
sorry but how is this backend related question?
seems like a DSA one
Search "minimum edit distance".
can there be 2 places that have the same mistake?
for example, you swapped "a" and "c" on 0
can there be more places where "a" and "c" are swapped in the same way?
Yes. The strings can have any combination of letters in any order, the only condition is that they’re anagrams of each other
that's a much harder problem then
I've looked at lots of edit distance algorithms but none of them were close enough to this that a small modification could solve the problem. However, I did figure out a way of handling it using the fact that each permutation of a group can be uniquely converted into transpositions. It's rather inefficient since I have to try all permutations of repeated letters but hey, it works.
Either way, thanks for suggestions everyone
question: why do you even need this?
I'm making a solver for https://wafflegame.net
I'm done with the solver itself, but I want it to tell the user the least number of swaps to win, and how to do the swaps