java.lang.Object
org.cicirello.permutations.distance.RTypeDistance
- All Implemented Interfaces:
NormalizedPermutationDistanceMeasurer
,NormalizedPermutationDistanceMeasurerDouble
,PermutationDistanceMeasurer
,PermutationDistanceMeasurerDouble
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 Summary
ConstructorsConstructorDescriptionConstructs the distance measurer as specified in the class documentation. -
Method Summary
Modifier and TypeMethodDescriptionint
distance
(Permutation p1, Permutation p2) Measures the distance between two permutations.int
max
(int length) Computes the maximum possible distance between permutations of a specified length.Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface org.cicirello.permutations.distance.NormalizedPermutationDistanceMeasurer
maxf, normalizedDistance
Methods inherited from interface org.cicirello.permutations.distance.PermutationDistanceMeasurer
distancef
-
Constructor Details
-
RTypeDistance
public RTypeDistance()Constructs the distance measurer as specified in the class documentation.
-
-
Method Details
-
distance
Measures the distance between two permutations.- Specified by:
distance
in interfacePermutationDistanceMeasurer
- Parameters:
p1
- first permutationp2
- 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.- Specified by:
max
in interfaceNormalizedPermutationDistanceMeasurer
- Parameters:
length
- Permutation length.- Returns:
- the maximum distance between a pair of permutations of the specified length.
-