Package org.cicirello.permutations.distance

Class AcyclicEdgeDistance

  • All Implemented Interfaces:
    NormalizedPermutationDistanceMeasurer, NormalizedPermutationDistanceMeasurerDouble, PermutationDistanceMeasurer, PermutationDistanceMeasurerDouble
    public final class AcyclicEdgeDistance
extends Object
implements NormalizedPermutationDistanceMeasurer
    Acyclic Edge Distance:

    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 Detail

      • AcyclicEdgeDistance

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