Class EditDistance
 java.lang.Object

 org.cicirello.permutations.distance.EditDistance

 All Implemented Interfaces:
PermutationDistanceMeasurerDouble
public final class EditDistance extends Object implements PermutationDistanceMeasurerDouble
Edit Distance:This is an implementation of Wagner and Fischer's dynamic programming algorithm for computing string edit distance, but adapted to permutations rather than general strings.
Edit distance is the minimum cost to transform one permutation into the other, which is the sum of the costs of the edit operations necessary to do so. This edit distance considers 3 edit operations: Inserts which insert a new element into the permutation, Deletes which remove an element from the permutation, and Changes which replace an element with a different element.
The edit distance is parameterized by costs for the edit operations. We provide one constructor which enables you to specify 3 costs, 1 for each type of edit operation.
And we also provide a default constructor, which assigns a cost of 0.5 for insert, 0.5 for delete, and which assigns an infinite cost to changes, essentially disallowing that 3rd type of edit operation. We chose this as the default as it is equivalent to counting the number of reinsertion operations necessary to transform one permutation into the other, known as Reinsertion Distance. A reinsertion operation removes an element and reinserts it in a different position, and is treated as a single composite operation.
Runtime: O(n^{2}), where n is the permutation length.
Wagner and Fischer's String Edit Distance was introduced in:
R. A. Wagner and M. J. Fischer, "The stringtostring correction problem," Journal of the ACM, vol. 21, no. 1, pp. 168–173, January 1974.Its application as a means of computing Reinsertion Distance is first described in:
V. A. Cicirello and R. Cernera, "Profiling the distance characteristics of mutation operators for permutationbased genetic algorithms," in Proceedings of the 26th FLAIRS Conference. AAAI Press, May 2013, pp. 46–51.


Constructor Summary
Constructors Constructor Description EditDistance()
Default edit distance computes number of remove and reinsert operations to transform one permutation into the other.EditDistance(double insertCost, double deleteCost, double changeCost)
Constructs an EditDistance function.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description double
distancef(Permutation p1, Permutation p2)
Measures the distance between two permutations.



Constructor Detail

EditDistance
public EditDistance(double insertCost, double deleteCost, double changeCost)
Constructs an EditDistance function. Parameters:
insertCost
 Cost of an insertion operation.deleteCost
 Cost of a deletion operation.changeCost
 Cost of a change operation.

EditDistance
public EditDistance()
Default edit distance computes number of remove and reinsert operations to transform one permutation into the other. And does not use change operations.


Method Detail

distancef
public double distancef(Permutation p1, Permutation p2)
Measures the distance between two permutations. Specified by:
distancef
in interfacePermutationDistanceMeasurerDouble
 Parameters:
p1
 first permutationp2
 second permutation Returns:
 distance between p1 and p2

