[Tutor] Generate list-of-transforms

[Alan Gauld]

On 05/12/13 03:56, R. Alan Monroe wrote:
> Given two lists, before and after a sort:
>           0 1 2 3 4
>           ---------
> before:  3 1 2 5 4
> after:   1 2 3 4 5
>
> Is there a well-known algorithm that can give me the
> list-of-transforms that got me from before to after?

No.
The reason being that it depends on the sorting algorithm
used, and there are many. It might be possible to reverse
engineer an algorithm to show what you want for a
given sorting algorithm, but it's not possible in
the general case.

I doubt if the detail is available for the standard Python
sort since recording those moves would slow things down and
the sort is optimised for speed. The easiest way is probably
to rewrite the standard sort (since we have the code for
that)  including logging as it goes.

-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.flickr.com/photos/alangauldphotos