2

My data structure is a path represented by a list of cities. If, for example, the cities are 

A, B, C, D

A possible configuration could be: A, B, D, C or D, C, A, B.

I need two compare two paths in order to find the differences between these two, in such a way that the output of this procedure returns the set of swapping operations necessary to transform the second path into the first one.

For example, given the following paths:

X = {A, B, D, C}
Y = {D, C, A, B}
indexes = {0, 1, 2, 3}

A possible way to transform the path Y into X would be the set of the following swaps: {0-2, 1-3}.

{D, C, A, B} --> [0-2] --> {A, C, D, B} --> [1-3] --> {A, B, D, C}

Is there any known (and fast) algorithm that allows to compute this set?

gliderkite
  • 8,828
  • 6
  • 44
  • 80
  • How long is the path? BFS (or A* search algorithm) can do it, but it will take exponential time. – amit Jan 25 '16 at 20:17
  • @amit the order of magnitude is 2, thus less than 1000 elements. – gliderkite Jan 25 '16 at 20:19
  • if the result exists, it's possible to solve (fast) using sorting algorithm with custom key function. – SashaMN Jan 25 '16 at 20:35
  • @SashaMN would be best defining this algorithm or showing an example – gliderkite Jan 25 '16 at 20:37
  • @gliderkite it can be done in O(N) also, using counting sort like algorithm) It's not so hard, I only give you an idea. – SashaMN Jan 25 '16 at 20:42
  • @SashaMN Sorting (counting or general purpose) is not guaranteed to provide the shortest series of swaps needed to convert one list to the other, if I understand it correctly. – amit Jan 25 '16 at 20:45
  • @amit My second approach guaranteed, no matter, Edgar Rokyan gave the answer. – SashaMN Jan 25 '16 at 20:54
  • 1
    @SashaMN your second approach is a well known sorting algorithm that does not return the swap operations that I need. – gliderkite Jan 25 '16 at 20:57

1 Answers1

3

Your problem looks like a problem of counting the minimal number of swaps to transform one permutation to another.

In fact it's a well known problem. The key idea is to create new permutation P such that P[i] is the index of X[i] city in the Y. Then you just calculate the total number of cycles C in the P. The answer is the len(X) - C, where len(X) is the size of X.

In your case P looks like: 3, 4, 1, 2. It has two cycles: 3, 1 and 4, 2. So the answer is 4 - 2 = 2.

Total complexity is linear.

For more details see this answer. It explains this algorithm in more details.

EDIT

Okay, but how we can get swaps, and not only their number? Note, that in this solution we reorder each cycle independently doing N - 1 swaps if the length of cycle is N. So, if you have cycle v(0), v(1), ..., v(N - 1), v(N) you just need to swap v(N), v(N - 1), v(N - 1), v(N - 2), ..., v(1), v(0). So you swap cycle elements in reverse order.

Also, if you have C cycles with lengths L(1), L(2), ..., L(C) the number of swaps is L(1) - 1 + L(2) - 1 + ... + L(C) - 1 = L(1) + L(2) + ... + L(C) - C = LEN - C where LEN is the length of permutation.

Community
  • 1
  • 1
Edgar Rokjān
  • 17,245
  • 4
  • 40
  • 67
  • I thought, not only the number of swap operations, but the swap operations themselves should be the result? I doubt, that this will be possible in linear time complexity. – Ctx Jan 25 '16 at 20:53
  • @Ctx the algorithm is trivial, if you understand, that you need exactly N - 1 swaps to transform one cycle with length N. – SashaMN Jan 25 '16 at 20:58
  • 2
    @SashaMN If it's so trivial, be so kind and write an answer with the actual algorithm for the OPs problem which has O(n) worst-case time complexity. I doubt you (indeed anyone) will succeed. – Ctx Jan 25 '16 at 21:00
  • @EdgarRokyan I still do not see how this should work in O(n). Not even the first step (P[i] is the index of X[i] city in Y) is doable in O(n). Or how would you achieve that? – Ctx Jan 25 '16 at 21:24
  • You can iterate over `Y` and set for `Y[i]` `T[Y[i]] = i`. Then iterate over `X` and set `P[i]=T[X[i]]`. Something like this. You can adopt it in any suitable way. – Edgar Rokjān Jan 25 '16 at 21:34
  • Ah, I misunderstood that. Ok, this indeed might be working, thanks for explaining ;) – Ctx Jan 25 '16 at 21:41
  • @Ctx Nice! It should works. Unfortunately I don't know a strict mathematical proof... But you can try to google Cayley distance and it's connection to permutations as it's mentioned in the answer from the link I posted. As I remember I solved similar problem on Timus online judge a few years ago and this algorithm was accepted. – Edgar Rokjān Jan 25 '16 at 21:53
  • What is the name of the algorithm? Where can I find any reference? – gliderkite Jan 26 '16 at 19:24
  • @gliderkite I doubt that It has a name. May be I just don't know... There're many discussions on SO and other resources concerning this problem. For example this one: http://stackoverflow.com/questions/2987605/minimum-number-of-swaps-needed-to-change-array-1-to-array-2 – Edgar Rokjān Jan 26 '16 at 19:36