Package org.cicirello.permutations.distance

Class AcyclicEdgeDistance

  • All Implemented Interfaces:
    NormalizedPermutationDistanceMeasurer, NormalizedPermutationDistanceMeasurerDouble, PermutationDistanceMeasurer, PermutationDistanceMeasurerDouble
    public final class AcyclicEdgeDistance
extends Object
    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.

    • Method Detail

      • distance

        public int distance​(Permutation p1,
                    Permutation p2)
        Measures the distance between two permutations.
        Parameters:
        p1 - first permutation
        p2 - second permutation
        Returns:
        distance between p1 and p2
        Throws:
        IllegalArgumentException - if p1.length() is not equal to p2.length().

      • max

        public int max​(int length)
        Description copied from interface: NormalizedPermutationDistanceMeasurer
        Computes the maximum possible distance between permutations of a specified length.
        Parameters:
        length - Permutation length.
        Returns:
        the maximum distance between a pair of permutations of the specified length.