test_partial_digest

test_partial_digest, an Octave code which generates 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.

• N must be at least 2.
• DMAX must be at least N - 1.
• The entries in LOCATE will be distinct integers in ascending order.
• LOCATE(1) = 0 and LOCATE(N) = DMAX.

Licensing:

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

Languages:

test_partial_digest is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.

Related Software and Data:

test_partial_digest_test

subset, an Octave code which carries out various combinatorial computations.

Reference:

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

Source Code:

• i4_uniform_ab.m, returns a pseudorandom I4 between A and B;
• i4vec_distances.m, computes pairwise distances between I4VEC elements.
• i4vec_print.m, prints an I4VEC;
• ksub_random.m, selects a random subset of size K from a set of size N.
• test_partial_digest.m, returns an example of the partial digest problem.