2

Is there a way to compute quantitatively the distance between two permutations?

Suppose we have the following two sequences of elements:

A = {0, 1, 2, 3}
B = {0, 3, 2, 1}

I could say that the permutation B differs from A because:

  • I would require 1 swap operation in order to transform B to A
  • There are 2 elements within B that have an index that is different for the same elements in A

Are there other ways to compare and describe the difference between those two?

The main goal is to define an algorithm that is able to approach the second permutation B to the first one A, such that if all the steps of this procedure are applied the outcome would be the permutation A itself. But in order to to that I think it should be best to define first a sensible procedure that describes how much B differs from A.

Is there any known algorithm that allows to approach on permutation to another?

Nick
  • 10,309
  • 21
  • 97
  • 201
  • How do you define the transformation operation? is it just a сircular shift? – neshkeev Jan 27 '16 at 16:43
  • @zaratustra The transformation is the set of swaps between two elements of the permutation. – Nick Jan 27 '16 at 16:45
  • Could the [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) be related to your problem ? – kebs Jan 27 '16 at 16:49
  • @kebs Could be Hamming distance, could be [Levenshtein distance](https://en.wikipedia.org/wiki/Levenshtein_distance), the OP could even be looking for [permutation matrices](https://en.wikipedia.org/wiki/Permutation_matrix). The requirements are unclear. – beaker Jan 27 '16 at 16:51
  • This can help also: http://math.stackexchange.com/questions/1410088/how-to-determine-a-kind-of-distance-between-two-permutations – haccks Jan 27 '16 at 17:21

2 Answers2

3

There are a few different ways to define the difference between two sequences. To name a few:

Hamming distance: the number of positions at which elements differ.

hamming(A, B)
  B[1] is different than A[1] and B[3] is different than A[3]
=> 2

Levenshtein distance: the minimum number of modifications necessary to get from one sequence to another.

levenshtein(A, B)
  replace B[1] with A[1] and replace B[3] with A[3]
=> 2

Damerau–Levenshtein distance: an extension of the former that takes into account transpositions.

damerau_levenshtein(A, B)
  transpose B[3] with B[1]
=> 1

Based upon your given example, you are interested in tracking transpositions and therefore Damerau–Levenshtein distance is your best bet.

Brandon
  • 487
  • 3
  • 10
1

Distance between permutations can be distance between lexicographic indexes of the permutations.

How to find lexicographic index is described here.

Community
  • 1
  • 1
serhiyb
  • 4,753
  • 2
  • 15
  • 24