Class BlockInterchangeDistance

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

public class BlockInterchangeDistance extends Object implements NormalizedPermutationDistanceMeasurer
Block Interchange Distance is the minimum number of block interchanges necessary to transform one permutation into the other. A block interchange is an edit operation that takes two non-overlapping blocks (i.e., subsequence) and exchanges their locations in the permutation. For example, the permutation p1 = [0, 1, 2, 3, 4, 5, 6, 7] and p2 = [5, 6, 3, 4, 0, 1, 2, 7] is a block interchange distance of 1 since you can transform p2 into p1 by exchanging the blocks [5, 6] and [0, 1, 2] within p2.

Interchange distance is computed efficiently using the algorithm described in the article: D.A. Christie, "Sorting permutations by block-interchanges," Information Processing Letters, vol 60, pages 165-169, 1996.

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

  • Constructor Details

    • BlockInterchangeDistance

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