1

Assume we have a list of objects: (A B C D)

Also, that we can perform operations on this list. There could be any number defined (insert, delete, move, swap, etc), but only insert and delete are required to transform any list into any other.

For example, the operations:

(insert 1 "X"), (insert 1 "Y"), (delete 0)

would transform the above list into:

(Y X B C D)

Now, my question is, is there some kind of math that these transformations can be turned into so that we can simplify a list of operations. For example, these operations can be simplified to nothing:

(insert 1 "X"), (delete 1)

since after they run, the list will not have changed. My problem is that I can't imagine how you could generalize this to simplify any list of operations.

Phil Kulak
  • 111
  • 1
  • You could compute the Levenshtein Distance of the original list and the transformed list. If it is shorter than the number of proposed operations, you can replace them by the steps found by the Levenshtein dynamic programming search. – Axel Kemper Jul 21 '17 at 17:07
  • Nice idea. You could even run the operations on a temp list exactly as long as the bounds of the operations. I don't think you'd even need the original list. – Phil Kulak Jul 21 '17 at 17:17

0 Answers0