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

l1

that is 19 characters long. I have a string

l2

l2

that is an anagram of

l1

l1

(

l2

l2

has the same characters as

l1

l1

but shuffled). I want to get from

l1

l1

l2

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

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,

l1 = "abc123456789abcdefg"
l2 = "cca123456789bbadefg"

# f(l1, l2) should return:
# [(0, 14), (1, 12), (1, 3)]

l1 = "abc123456789abcdefg"
l2 = "cca123456789bbadefg"

# f(l1, l2) should return:
# [(0, 14), (1, 12), (1, 3)]

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.

Chief•12/26/24, 8:32 AM

sorry but how is this backend related question?

Chief•12/26/24, 8:32 AM

seems like a DSA one

BBlanwhit I'm using Python for the backend of this project. I have a string `l1` that is 1...

dys 🐙•12/26/24, 1:23 PM

Search "minimum edit distance".

Ἔ

ἔρως•12/26/24, 5:42 PM

can there be 2 places that have the same mistake?

Ἔ

ἔρως•12/26/24, 5:43 PM

for example, you swapped "a" and "c" on 0

Ἔ

ἔρως•12/26/24, 5:43 PM

can there be more places where "a" and "c" are swapped in the same way?

Ἔἔρως can there be more places where "a" and "c" are swapped in the same way?

BlanwhitOP•12/26/24, 9:55 PM

Yes. The strings can have any combination of letters in any order, the only condition is that they’re anagrams of each other

Ἔ

ἔρως•12/26/24, 9:56 PM

that's a much harder problem then

BlanwhitOP•12/27/24, 3:02 PM

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.

BlanwhitOP•12/27/24, 3:03 PM

Either way, thanks for suggestions everyone

Ἔ

ἔρως•12/27/24, 3:41 PM

question: why do you even need this?

BlanwhitOP•12/27/24, 8:17 PM

I'm making a solver for https://wafflegame.net

Waffle

The waffle-shaped daily word game.

BlanwhitOP•12/27/24, 8:17 PM

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