Package org.cicirello.permutations.distance

Class BlockInterchangeDistance

  • All Implemented Interfaces:
    NormalizedPermutationDistanceMeasurer, NormalizedPermutationDistanceMeasurerDouble, PermutationDistanceMeasurer, PermutationDistanceMeasurerDouble
    public class BlockInterchangeDistance
extends Object
implements NormalizedPermutationDistanceMeasurer
    Block Interchange Distance:

    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 Detail

      • BlockInterchangeDistance

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