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

Class KCycleDistance

java.lang.Object
org.cicirello.permutations.distance.KCycleDistance
All Implemented Interfaces:
NormalizedPermutationDistanceMeasurer, NormalizedPermutationDistanceMeasurerDouble, PermutationDistanceMeasurer, PermutationDistanceMeasurerDouble
public final class KCycleDistance extends Object implements NormalizedPermutationDistanceMeasurer
K-Cycle distance is the count of the number of non-singleton permutation cycles of length at most K. Specifically, each non-singleton cycle contributes to the total distance the number of cycles of length at most K necessary to transform the cycle to all fixed points. K-cycle distance is a metric provided that K ≤ 4. However, if K > 4, it is only a semi-metric because it fails to satisfy the triangle inequality when K ≥ 5.

K-Cycle distance was introduced in the following article:

Vincent A. Cicirello. 2022. Cycle Mutation: Evolving Permutations via Cycle Induction, Applied Sciences, 12(11), Article 5506 (June 2022). doi:10.3390/app12115506

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

  • Constructor Details

    • KCycleDistance

      public KCycleDistance(int k)
      Constructs the distance measurer as specified in the class documentation.
      Parameters:
      k - The maximum length cycle that is considered an atomic edit operation, such that k is greater than or equal to 2.
      Throws:
      IllegalArgumentException - if k is less than 2

  • Method Details