Let's say you have a list of values that are:

  1. a
  2. b
  3. c
  4. d
  5. e

The order on the list might be changed.

  1. a
  2. c
  3. d
  4. b
  5. e

How would you detect this change? We needed something like this when we were building a revision history page for our online form building tool. We found a quick and dirty solution, but I am looking for a more elegant solution for this. Here is what the revision descriptions look like:

jotform revisions page

Here is the tough part: Elements can be removed/added from/to anywhere on the list. So, the algorithm should be able to ignore those changes.

  • 3
    What is the difference between a change in the order of elements and a sequence of remove/add actions? Jan 31 '14 at 10:16
  • Bart: Let's say "b" is removed from the list. The location of "c" is now moved to second place. We don't want to say "c has been moved" when that happens. It should only capture real moves those that were made intentionally.
    – Aytekin
    Jan 31 '14 at 12:02
  • 2
    Lets say that "b" is removed from the list and then a new "b" is added at position 4. Is that a move of "b"? Does it make a difference if there is an intermediary revision where "b" does not exist in the list? Jan 31 '14 at 13:29
  • Can't you just track this via whatever method you use to re-order the list in the first place? Log the moves made in a move up/down in list event handler for example.
    – Evicatos
    Feb 1 '14 at 0:17

There are two approaches:

  1. Try to find a way to apply the diff algorithm to your model. This gets easier when there is a underlying textual representation (e.g. HTML source or another DSL).
  2. Don't have your form builder emit complete states, only have it emit differences which you can easily log. Instead of having the before and after lists, you'd log the “move field from x to y” operation.

Create a double linked list for records. In your example:

for the first list:

a: {prev: -1, next: b}
b: {prev: a, next: c}
c: {prev: b, next: d}
d: {prev: c, next: e}
e: {prev: d, next: -1}

and for the second list

a: {prev: -1, next: c}
c: {prev: a, next: d}
d: {prev: c, next: b}
b: {prev: d, next: e}
e: {prev: b, next: -1}

Now when you compare the both list only order change matters should be "b", because it's both previous and next value changed. Only previous or only next value modified records should not be taken into account since they slide because of order change of "b"


I will treat this as an algorithm question. It may not be what was intended.

  1. Go through the first list, creating an lookup from key->index. In your example, a->1, b->2, c->3, d->4 and so on.
  2. Go through the second list, looking up each element and comparing its index to its neighbour's index. In your case b->2 appears after d->4, which is out of order.

Each of the out of order elements by this criterion is one that has moved. Inserted elements have no index, and deleted elements will not be examined.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.