Package org.cicirello.permutations.distance

Class RTypeDistance

  • All Implemented Interfaces:
    NormalizedPermutationDistanceMeasurer, NormalizedPermutationDistanceMeasurerDouble, PermutationDistanceMeasurer, PermutationDistanceMeasurerDouble
    public final class RTypeDistance
extends Object
    RType Distance:

    RType distance treats the permutations as if they represent sets of directed edges, and counts the number of edges that differ.

    Consider the example permutation: [1, 5, 2, 4, 0, 3]. RType distance treats this as equivalent to the set of directed 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 3. Why? Well, the first permutation has the directed edges: {(1,5), (5,2), (2,4), (4,0), (0,3)}. The second has 2 of these (4,0), and (0,3), but does not include 3 of the edges: (1,5), (5,2), (2,4)

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

    RType distance was introduced in:
    V. Campos, M. Laguna, and R. Marti, "Context-independent scatter and tabu search for permutation problems," INFORMS Journal on Computing, vol. 17, no. 1, pp. 111–122, 2005.

    • Constructor Detail

      • RTypeDistance

        public RTypeDistance()
        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.