title: How to compute the absolute minimum amount of changes to convert one sortorder into another?
body: <p><strong>Goal</strong></p>
  
  <p>How to encode the data that describes how to re-order a static list from a one order to another order using the minimum amount of data possible?</p>
  
  <p>I have a feeling there is an algorithm or computer science term that will help me but right now I'm too stuck on the problem to figure out other ways of looking at it.</p>
  
  <p><strong>Background Motivation</strong></p>
  
  <p>I'm have a program that is deployed to a remote location where all communication is via an intermittent incredibly expensive satellite connection.  It's a slight exaggeration, but data costs are close to a dollar per kilobyte and can only happen a few times per day.</p>
  
  <p>At the start of the day the users are given a list of items, they go out in the field and do stuff but the end result is more or less the same list of items sorted in a different order.  There's other data but it's not important to this problem.</p>
  
  <p>Right now I'm sending back a record of all the moves that occur and playing them back in order.  As users get comfortable with the system the list of move records is starting to approach the size of just sending back all the items themselves, and often some combination of moves results in undoing previous ones.</p>
  
  <p><strong>Assumptions</strong></p>
  
  <ul>
  <li>The starting list and ending list is composed of the exact same set of items</li>
  <li>Each item has a unique id (32 bit integer)</li>
  <li>Each item has a unique sort oder  (32 bit integer)</li>
  <li>User will have a list of several hundreds to a thousand or more items</li>
  <li>User will generally re-order about 100 of those items in a day</li>
  <li>Changes to the order can be detected moving an item to a new position in the list</li>
  <li>Some "moves" may undo previous ones</li>
  <li>Computation resources for figuring optimal solutions is cheap / unlimited</li>
  <li>Transmission time is expensive</li>
  <li>Sending back the change data is cheaper than sending the back the whole list</li>
  </ul>
  
  <p><strong>Simplest Data Structure</strong></p>
  
  <p>For the purposes of solving this problem assume the following data structures are available.</p>
  
  <ul>
  <li>ListItem
  
  <ul>
  <li>item_id</li>
  <li>sort_order</li>
  </ul></li>
  <li>MoveRecord
  
  <ul>
  <li>item_a_id</li>
  <li>new_a_position</li>
  </ul></li>
  </ul>
  
  <p>Here is an example list.  The items in each list are the same.  Notice that even though only a few of the items have changed, every single item id has a new sort order so you can't just send back new item_id/sort_order_id pairs.</p>
  
  <pre><code>**List 1: Original List**    **List 2: Re-ordered List**    
  order - id                    order - id
       1. 10                         1. 90
       2. 20                         2. 30
       3. 30                         3. 40
       4. 40                         4. 50
       5. 50                         5. 60
       6. 60                         6. 10
       7. 70                         7. 80
       8. 80                         8. 70
       9. 90                         9. 20
  </code></pre>
  
  <p>How do I encode the changes required to convert the order of List 1, into the order of List 2 using the minimum amount of data possible?</p>
  
  <p>As a curiosity is it possible to <em>prove</em> that there is a solution is optimal?</p>
  
  <p><strong>Update</strong></p>
  
  <p>A co-worker pointed out that "swap" may not be correct way to think of it.  You can also send an item to the top or bottom of the list which is more of a move than a swap.  A swap then becomes a combination of two moves.</p>
  
  <p>Thanks for the pointers.  So far I don't see a guaranteed optimal solution.  Plus the problem just changed a little.</p>
  
  <p>If I can't prove any single method produces the best result then I'll figure out a solution using every method and send back that solution with a small header indicating the method used.  Keep suggesting solutions though and I'll update this question with my research.</p>
  
  <p>Thanks everyone!</p>