Module org.cicirello.jpt
Package org.cicirello.permutations.distance

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(n-1)/2 pairs of elements, the maximum of Kendall tau distance is n(n-1)/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 localization-based approach" (Liu and Han, SIGSOFT 2006, pages 46-56).

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 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

      public double distancef(Permutation p1, Permutation p2)
      Measures the distance between two permutations
      Specified by:
      distancef in interface PermutationDistanceMeasurerDouble
      Parameters:
      p1 - first permutation
      p2 - 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 interface NormalizedPermutationDistanceMeasurerDouble
      Parameters:
      length - Permutation length.
      Returns:
      the maximum distance between a pair of permutations of the specified length.