I tried an algorithm that uses some best step estimation, or scores with one step forward evaluation. Let me explain:
Every inversion can be described as relative displacement plus starting position:
Inversion # of positions within 10 fields
[-1, 1] 9
[-2, 0, 2] 8
[-3, -1, 1, 3] 7
[-4, -2, 0, 2, 4] 6
[-5, -3, -1, 1, 3, 5] 5
[-6, -4, -2, 0, 2, 4, 6] 4
[-7, -5, -3, -1, 1, 3, 5, 7] 3
[-8, -6, -4, -2, 0, 2, 4, 6, 8] 2
[-9, -7, -5, -3, -1, 1, 3, 5, 7, 9] 1
Hence, you have 1+2+3+4+5+6+7+8+9 = 45 combinations to find best score.
Comparing to 1x2x3x4xx5x6x7x8x9= 9! = 362 880 if you want to check all possible combinations.
Instead, I tried 2-step approach for scoring, which requires 45*45=2025. As a result, this code is acceptable fast and max execution time is not very case dependent. Some examples below.
As I already mentioned, I used also a code which is finding all substring combinations, plus random generation of strings. What I found is:
Maximum number of steps for 10 digits is 8 (based on 110 samples). The result is the same in both directions (from to = to from). Execution time on my laptop using Python 3.9 are from milliseconds up to minutes for a single case. Some examples:
Case
3817964250 0123456789 steps 8, exec=371 sec, my result steps 7, exec=0.06 sec
2935740816 0123456789 steps 7 exec=328 sec , my result steps 7, exec= 0.06 sec
3851796420 0123456789 steps 7 exec=298 sec, my result steps 7, exec=0.06 sec
4258910673 0123456789 steps 6 exec=45 sec, my result steps 6, exec=0.04 sec
1032547698 0123456789 steps 5 exec=4 sec, my result steps 5, exec==0.04 sec
4368792105 0123456789 steps 4 exec=1 sec, my result steps 5, exec==0.04 sec
9126543780 0123456789 steps 3 exec=0.05 sec, my result steps 3, exec==0.02 sec
9423108765 0123456789 steps 3 exec=0.03 sec, my result steps 3, exec==0.03 sec
9123456780 0123456789 steps 2 exec=0.002 sec, my result steps 2, exec==0.01 sec
Too good to be true. There are cases when my code fails:
8967452301 0123456789 steps 5 exec=5 sec, my result steps 6, exec=0.05 sec (try find yourself what are these 5 steps and you will understand why my code failed)
Next:
4536091728 0123456789 steps 6 exec=46 sec, my result steps 7, exec=0.05 sec however after exchanging from-to direction:
0123456789 4536091728 steps 6 exec=83 sec, my result steps 6, exec=0.04 sec so ok, but the cost of checking in both directions to select lower number of steps is 2x, and do not help in each case like:
5293014768 6012349758 steps 5 exec=15sec, my result steps 6 (both directions) exec=0.04 sec
Cases which seem trivial:
1357902468 0123456789 steps 7 exec=161sec, my result steps 7 exec=0.05 sec
3456012789 0123456789 steps 3, exec=0.01sec, my result steps 3 exec=0.02 sec
Summarizing: my code is fast, but in some case may overestimate steps, however, by just one step.
So depending on the application, it may be acceptable or not. I case of this “old fashioned jukebox” I would prefer not to wait minutes or even seconds to save just one step!
BTW: I have not submitted this code, since probably I would get WA if just one case failed.
I am not Python geek, nor programming expert, and cannot find better solution.