JavaPermutationTools: A Java Library of Permutation Distance Metrics
Vincent A. Cicirello
Journal of Open Source Software, 3(31), Article 950, . doi:10.21105/joss.00950
[PDF] [BIB] [DOI] [CODE]
Permutations can represent a wide variety of ordered data. For example, a permutation may represent an individual’s preferences (or ranking) of a collection of products such as books or music. Or perhaps a permutation may represent a route for delivering a set of packages. Permutations can also represent one-to-one mappings between sets (e.g., instructors to courses at a fixed time). There are applications where measuring the distance between a pair of permutations is necessary. For example, a recommender system may assess the similarity of two individuals’ preferences for music to make song recommendations. Depending upon the application, the permutation features most important to distance calculation may be the absolute positions of the elements (e.g., one-to-one mappings), the adjacency of elements (e.g., the routing example), or general precedence of pairs of elements (e.g., music preferences). Thus, it is no surprise that there are many permutation metrics in the research literature.
The motivation and origin of this library is our research on fitness landscape analysis for permutation optimization. In a permutation optimization problem, solutions are represented by permutations of some set, and the objective is to maximize or minimize some function. For example, a solution to a traveling salesperson problem is the permutation of the set of cities that corresponds to the minimal cost tour. During our research, we developed a Java library of permutation distance metrics. Most of the distance metrics in the literature are described mathematically with no source code available. Thus, our library offers convenient access to efficient implementations of a variety of metrics with a common programmatic interface. The library also provides metrics on sequences (strings and arrays of various types); where unlike a permutation, a sequence may contain multiple copies of the same element.
The source repository (https://github.com/cicirello/JavaPermutationTools) contains source code of the library, programs that provide example usage of key functionality, as well as programs that reproduce results from papers that have used the library. API documentation is hosted on the web (https://jpt.cicirello.org/).