Module org.cicirello.jpt
Package org.cicirello.permutations.distance

Class AcyclicEdgeDistance

java.lang.Object
org.cicirello.permutations.distance.AcyclicEdgeDistance
All Implemented Interfaces:
NormalizedPermutationDistanceMeasurer, NormalizedPermutationDistanceMeasurerDouble, PermutationDistanceMeasurer, PermutationDistanceMeasurerDouble
public final class AcyclicEdgeDistance extends Object implements NormalizedPermutationDistanceMeasurer
Acyclic edge distance treats the permutations as if they represent sets of edges, and counts the number of edges that differ.

Consider the example permutation: [1, 5, 2, 4, 0, 3]. Acyclic edge distance treats this as equivalent to the set of undirected edges: {(1,5), (5,2), (2,4), (4,0), (0,3)}.

E.g., distance between [1, 5, 2, 4, 0, 3] and [ 5, 1, 4, 0, 3, 2] is 2. Why? Well, the first permutation has the edges: {(1,5), (5,2), (2,4), (4,0), (0,3)}. The second has three of these (5,1), which is the same as (1,5) since they are undirected edges, (4,0), and (0,3), but does not include two of the edges: (5,2), (2,4)

Runtime: O(n), where n is the permutation length.

Acyclic edge distance was first described in:
S. Ronald, "Distance functions for order-based encodings," in Proc. IEEE CEC. IEEE Press, 1997, pp. 49–54.

  • Constructor Details

    • AcyclicEdgeDistance

      public AcyclicEdgeDistance()
      Constructs the distance measurer as specified in the class documentation.

  • Method Details