Recursive solution for minimum number of adjacent swaps to convert a string into its given anagram

Question

Is there any recursive way to implement minimum number of adjacent swaps to convert a string into its given anagram in particular this solution?

I have written a solution in Python but I don't know how to implement it using recursion.

def min_adjacent_swaps(r1, r2):
    s1 = list(r1)
    s2 = list(r2)
    i = 0
    j = 0
    result = 0
    while i < len(s2):
        j = i
        while s1[j] != s2[i]:
            j += 1
        while i < j:
            temp = s1[j]
            s1[j] = s1[j - 1]
            s1[j - 1] = temp
            j -= 1
            result += 1
        i += 1
    return result

>>> print(min_adjacent_swaps("abcd", "badc"))
2

Why do you want to use recursion? In Python, iteration is basically always preferred for linear algorithms like loops that count from 0...len. Have you tried anything yet? — ggorlen, Jul 21 '21 at 15:54
@ggorlen, I know, just as a curiosity I want to strengthen my implementation power because the problem seems to be fit in a good recursion procedure, no? — Alex, Jul 21 '21 at 16:27
I'd say it's a poor fit for recursion for reasons explained by me [here](https://stackoverflow.com/a/66846438/6243352) and by others in [this bigger thread](https://stackoverflow.com/questions/67988828), among other threads linked in my explanation. If you want to implement things recursively out of curiosity, that's great, but keep in mind that many algorithms (generally linear ones) are simply worse off recursively by almost every metric (readability, efficiency, ease of writing, safety, etc), at least in CPython. — ggorlen, Jul 21 '21 at 16:32

score 0 · Accepted Answer · answered Jul 22 '21 at 03:30

My aproach to this problem would be turn while i < len(s2) into if i < len(s2) and then figure out how to use the original function to finish the solution. I.e we've solved for the first character, now recurse for the rest. Doing that, optimizing the result, and throwing some Python at it, I get something like:

def min_adjacent_swaps(r1, r2):
    # r1 and r2 can be str or list

    swaps = 0

    if r1 and r2:
        s1 = list(r1)  # make mutable

        j = s1.index(r2[0])

        while j > 0:
            s1[j-1], s1[j] = s1[j], s1[j-1]  # swap
            swaps += 1
            j -= 1

        return swaps + min_adjacent_swaps(s1[1:], r2[1:])

    return swaps

print(min_adjacent_swaps("abcd", "dcba"))
print(min_adjacent_swaps("abcd", "badc"))

Looking at your original, and my rewrite, I can't say whether either returns the minimum number of steps. But this was really about how to convert an iterative solution to a recursive one.

Thank you. assuming the input strings are of the same length n, is the running time complexity O(n^2)? — Alex, Jul 23 '21 at 00:19

Recursive solution for minimum number of adjacent swaps to convert a string into its given anagram

1 Answers1