Edit Distance multi swap

Basic Problem: editdistance fnc does not want to do multiple swaps, even when it is the cheepest way.

Is it the expected behavior? Any known workaround (that are not necessarily assuming that only swaps are allowed, this is only for demonstration)?

editDistance('12534','12345','SwapCost',1,'InsertCost',inf,'DeleteCost',inf,'SubstituteCost',inf)

ans = Inf

% The only non-inf solution is to do multiple swaps in a row:
% 12534 -> (5<>3) -> 12354
% 12354 -> (5<>4) -> 12345 == 12345 Victory! 
% cost = 2 (5 started at pos 3, finished pos 5 - 5-3=2, expected)
% However instead we got inf :(

Note: it does allow for a single swap, but no more:

editDistance('12354','12345','SwapCost',1,'InsertCost',inf,'DeleteCost',inf,'SubstituteCost',inf)

ans = 1

[Steven Apsel]

I have the same problem.

Answer 1

[Rupesh]

Hi Lior,

I understand that the issue with the code is that it uses MATLAB “editdistance” function and you have set the values in such a way that it is forced to swap operations instead of deletion or insert. Although there is a limitation with this function my suggestion is to create an custom function in MATLAB based upon dynamic programming to resolve the issue.

The key idea behind using DP for this problem is to iteratively calculate the minimum number of swaps needed to make prefixes of the first string (str1) match with prefixes of the second string (str2). We consider each character in str1 and str2, and for each pair of characters, we determine whether a swap is needed based on their positions and then initialize dp[n+1][n+1] with infinity, where n is the length of str1 (and str2). Initialize dp[n+1][n+1] with infinity, where n is the length of str1 (and str2).You can consider below pseudo code for better understanding of approach.

for i from 1 to n:
    for j from 1 to n:
        if str1[i-1] == str2[j-1]:
            dp[i][j] = dp[i-1][j-1]  // No swap needed if characters match
        else:
            // Find the minimum swaps needed by considering all previous positions
            for k from 0 to i-1:
                if str1[k] == str2[j-1]:
                    dp[i][j] = min(dp[i][j], dp[k][j-1] + cost_of_swapping(k, i-1))
                    // Optionally handle the case where characters do not match and cannot be swapped directly
                    return dp[n][n]

you can also refer to below documents which consists of a lighter version for this problem where other than swap rest three operations are involved which will give you better idea about coding the above solution. https://in.mathworks.com/matlabcentral/fileexchange/39049-edit-distance-algorithm