How to compute the absolute minimum amount of changes to convert one sortorder into another?

Question

Goal

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?

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.

Background Motivation

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.

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.

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.

Assumptions

• The starting list and ending list is composed of the exact same set of items
• Each item has a unique id (32 bit integer)
• Each item has a unique sort oder (32 bit integer)
• User will have a list of several hundreds to a thousand or more items
• User will generally re-order about 100 of those items in a day
• Changes to the order can be detected moving an item to a new position in the list
• Some "moves" may undo previous ones
• Computation resources for figuring optimal solutions is cheap / unlimited
• Transmission time is expensive
• Sending back the change data is cheaper than sending the back the whole list

Simplest Data Structure

For the purposes of solving this problem assume the following data structures are available.

• ListItem
  • item_id
  • sort_order
• MoveRecord
  • item_a_id
  • new_a_position

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.

**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

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?

As a curiosity is it possible to prove that there is a solution is optimal?

Update

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.

Thanks for the pointers. So far I don't see a guaranteed optimal solution. Plus the problem just changed a little.

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.

Thanks everyone!

Answer 1

Algo part:

A reordering of a list is called permutation. Each permutation can be split into a set of loops, with each loop of N elements requiring (N - 1) swaps. For example

1, 2, 3, 4, 5, 6 --> 3, 2, 4, 1, 6, 5

This can be split into 1 - 4 - 3 (requires 2 swaps) 2 - 2 (0 swaps) 5 - 6 (1 swap)

To find a solution you can just pick any element at a wrong position and put it on its place.

Details part:

Of course, you can use smaller data types, RLE or some other encoding algorithms and so on.

Very theoretical but non-practical part.

All permutations of a sequence of N numbers can be lexicographically ordered, and one number from 0 to (N! - 1) is enough to represent the sequence. So, theoretically best answer is: compute the index of the permutation, transfer it, recreate the permutation by that index.

Answer 2

What you want is the permutation required to sort the list. You can get this by constructing a list of indices from 0 to n, then sorting that list with a custom comparison function that compares the items at the corresponding indices. For example, in Python:

perm = sorted(range(len(l)), key=lambda x:l[x])

You can then send 'perm' over the connection, and use it to get the sorted list:

for x in perm:
  print perm[x]

As a further optimization, if most elements remain unchanged, the permutation will be highly compressible - either by using regular compression or by using transforms like difference (eg, store each element as the difference from the previous element, rather than its absolute value), move to front and run length encoding.