Class CycleEditDistance

java.lang.Object
org.cicirello.permutations.distance.CycleEditDistance
All Implemented Interfaces:
NormalizedPermutationDistanceMeasurer, NormalizedPermutationDistanceMeasurerDouble, PermutationDistanceMeasurer, PermutationDistanceMeasurerDouble

public final class CycleEditDistance extends Object implements NormalizedPermutationDistanceMeasurer
Cycle edit distance is the minimum number of non-singleton permutation cycles necessary to transform permutation p1 into p2. If p1 equals p2, then this distance is 0. If p1 and p2 have a single permutation cycle, then this distance is clearly 1 since the inverse of that cycle will produce n fixed points. Otherwise, this distance is equal to 2 since it can be shown that at most 2 permutation cycle operations are necessary to transform any permutation of length n into any other. Cycle edit distance satisfies all of the metric properties.

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

    • CycleEditDistance

      public CycleEditDistance()
      Constructs the distance measurer as specified in the class documentation.
  • Method Details