Module org.cicirello.jpt
Class WeightedKendallTauDistance
java.lang.Object
org.cicirello.permutations.distance.WeightedKendallTauDistance
 All Implemented Interfaces:
NormalizedPermutationDistanceMeasurerDouble
,PermutationDistanceMeasurerDouble
public final class WeightedKendallTauDistance
extends Object
implements NormalizedPermutationDistanceMeasurerDouble
This class implements the weighted Kendall tau distance. In the original Kendall tau distance,
each inverted pair of elements (i.e., such that element x appears someplace before y in
Permutation p1, but someplace after y in Permutation p2) contributes 1 to the distance. Thus,
since there are n(n1)/2 pairs of elements, the maximum of Kendall tau distance is n(n1)/2 where
n is the permutation length. In this weighted Kendall tau distance, each element x of the
permutation has an associated weight w(x), and each inverted pair x, y (where x appears before
sometime prior to y in p1, but sometime after y in p2) contributes w(x) * w(y) to the weighted
Kendall tau distance.
The weighted Kendall tau distance was first described in:
"Failure proximity: a fault localizationbased approach" (Liu and Han, SIGSOFT 2006, pages
4656).
The runtime of JPT's implementation is O(n lg n), where n is the permutation length. This runtime is achieved using a modified version of mergesort to sum the weighted inversions.

Constructor Summary
ConstructorDescriptionWeightedKendallTauDistance
(double[] weights) Constructs an instance of the WeightedKendallTauDistance. 
Method Summary
Modifier and TypeMethodDescriptiondouble
distancef
(Permutation p1, Permutation p2) Measures the distance between two permutationsdouble
maxf
(int length) Computes the maximum possible distance between permutations of a specified length.int
Gets the length of permutations supported by this instance of WeightedKendallTauDistance, which is equal to the length of the array of weights passed to the constructor.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.NormalizedPermutationDistanceMeasurerDouble
normalizedDistance

Constructor Details

WeightedKendallTauDistance
public WeightedKendallTauDistance(double[] weights) Constructs an instance of the WeightedKendallTauDistance. Parameters:
weights
 An array of weights, such that weights[e] is the weight of element e.


Method Details

supportedLength
public int supportedLength()Gets the length of permutations supported by this instance of WeightedKendallTauDistance, which is equal to the length of the array of weights passed to the constructor. Returns:
 The length of supported Permutations.

distancef
Measures the distance between two permutations Specified by:
distancef
in interfacePermutationDistanceMeasurerDouble
 Parameters:
p1
 first permutationp2
 second permutation Returns:
 distance between p1 and p2
 Throws:
IllegalArgumentException
 if p1.length() is not equal to supportedLength(), or if p2.length() is not equal to supportedLength().

maxf
public double maxf(int length) Computes the maximum possible distance between permutations of a specified length.This implementation ignores the length parameter since this distance is configured for one specific length based upon the weights passed during construction.
 Specified by:
maxf
in interfaceNormalizedPermutationDistanceMeasurerDouble
 Parameters:
length
 Permutation length. Returns:
 the maximum distance between a pair of permutations of the specified length.
