Algorithm for expressing reordering, as minimum nu

This problem arises in synchronization of arrays (ordered sets) of objects.

Specifically, consider an array of items, synchronized to another computer. The user moves one or more objects, thus reordering the array, behind my back. When my program wakes up, I see the new order, and I know the old order. I must transmit the changes to the other computer, reproducing the new order there. Here's an example:

index         0    1    2
old order     A    B    C
new order     C    A    B

Define a move as moving a given object to a given new index. The problem is to express the reordering by transmitting a minimum number of moves across a communication link, such that the other end can infer the remaining moves by taking the unmoved objects in the old order and moving them into as-yet unused indexes in the new order, starting with the lowest index and going up. This method of transmission would be very efficient in cases where a small number of objects are moved within a large array, displacing a large number of objects.

Hang on. Let's continue the example. We have

CANDIDATE 1
Move A to index 1
Move B to index 2
Infer moving C to index 0  (the only place it can go)

Note that the first two moves are required to be transmitted. If we don't transmit Move B to index 2, B will be inferred to index 0, and we'll end up with B A C, which is wrong. We need to transmit two moves. Let's see if we can do better…

CANDIDATE 2
Move C to index 0
Infer moving A to index 1  (the first available index)
Infer moving B to index 2  (the next available index)

In this case, we get the correct answer, C A B, transmitting only one move, Move C to index 0. Candidate 2 is therefore better than Candidate 1. There are four more candidates, but since it's obvious that at least one move is needed to do anything, we can stop now and declare Candidate 2 to be the winner.

I think I can do this by brute forcibly trying all possible candidates, but for an array of N items there are N! (N factorial) possible candidates, and even if I am smart enough to truncate unnecessary searches as in the example, things might still get pretty costly in a typical array which may contain hundreds of objects.

The solution of just transmitting the whole order is not acceptable, because, for compatibility, I need to emulate the transmissions of another program.

If someone could just write down the answer that would be great, but advice to go read Chapter N of computer science textbook XXX would be quite acceptable. I don't know those books because, I'm, hey, only an electrical engineer.

Thanks!

Jerry Krinock

回答1:

I think that the problem is reducible to Longest common subsequence problem, just find this common subsequence and transmit the moves that are not belonging to it. There is no prove of optimality, just my intuition, so I might be wrong. Even if I'm wrong, that may be a good starting point to some more fancy algorithm.

回答2:

Information theory based approach

First, have a bit series such that 0 corresponds to 'regular order' and 11 corresponds to 'irregular entry'. Whenever there in irregular entry also add the original location of the entry that is next.

Eg. Assume original order of ABCDE for the following cases

ABDEC: 001 3 01 2

BCDEA: 1 1 0001 0

Now, if the probability of making a 'move' is p, this method requires roughly n + n*p*log(n) bits.

Note that if p is small the number of 0s is going to be high. You can further compress the result to:

n*(p*log(1/p) + (1-p)*log(1/(1-p))) + n*p*log(n) bits