Test Problems for Partial Digest

TEST_PARTIAL_DIGEST, a C++ code which can generate example cases of the partial digest problem.

In the partial digest problem, we assume that there are N objects arranged along a line. We denote the position of object I by X(I). The positions of the objects are unknown. Instead, we have a list of the distances between every distinct pair of objects. Note that the distances are not "tagged"; that is, if there is a 175 on the list of distances, we don't know which two objects are separated by that distance. In the partial digest problem, we start with the (N*(N-1))/2 distances D, and must come up with at least one linear arrangement of N objects that corresponds to the distances.

To use this library, the user specifies a number of objects N, and a maximum separation DMAX. The library will generate N object locations in an array called LOCATE, and the corresponding list of distances D.


The computer code and data files made available on this web page are distributed under the GNU LGPL license.


TEST_PARTIAL_DIGEST is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Software and Data:

SUBSET, a C++ library which carries out various combinatorial computations.



  1. Pavel Pevzner,
    Computational Molecular Biology,
    MIT Press, 2000,
    ISBN: 0-262-16197-4,
    LC: QH506.P47.

Source Code:

Last revised on 24 April 2020.