Package org.cicirello.permutations.distance

Class BlockInterchangeDistance

  • All Implemented Interfaces:
    NormalizedPermutationDistanceMeasurer, NormalizedPermutationDistanceMeasurerDouble, PermutationDistanceMeasurer, PermutationDistanceMeasurerDouble
    public class BlockInterchangeDistance
extends Object
    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.

    • Method Detail

      • distance

        public int distance​(Permutation p1,
                    Permutation p2)
        Measures the distance between two permutations.
        Parameters:
        p1 - first permutation
        p2 - second permutation
        Returns:
        distance between p1 and p2
        Throws:
        IllegalArgumentException - if p1.length() is not equal to p2.length().

      • max

        public int max​(int length)
        Description copied from interface: NormalizedPermutationDistanceMeasurer
        Computes the maximum possible distance between permutations of a specified length.
        Parameters:
        length - Permutation length.
        Returns:
        the maximum distance between a pair of permutations of the specified length.