COMPBUILDER

COMPBUILDER is designed to reconstruct compositions from their subcompositions. It is described in and was a great help in the writing of "Reconstructing compositions."

COMPBUILDER has been tested with Maple 9.

Download the package:

• plain text Maple source (version of October 4, 2006)

Example:

Download the package, run Maple, and load the package by typing

> read COMPBUILDER;

Maple will then say

COMPBUILDER: A Maple package to reconstruct compositions from their
sets of subcompositions.
Written by Vince Vatter (http://turnbull.mcs.st-and.ac.uk/~vince/)
This version: October 4, 2006
Main procedures: rand_test, thorough_test, subcomps,
        reconstruct, tear_down_and_reconstruct

For help with a procedure, call it with no arguments, e.g.,
        thorough_test();

To see if the composition 2211121211 is reconstructible from its 4-deletions, first we compute them:

> S := deletions(4, [2, 2, 1, 1, 1, 2, 1, 2, 1, 1]);
S := {[1, 1, 1, 2, 1, 2, 1, 1], [1, 1, 1, 1, 1, 1, 2, 1, 1],

    [1, 1, 1, 1, 2, 2, 1, 1], [1, 1, 1, 1, 2, 1, 1, 1, 1],

    [1, 1, 1, 1, 2, 1, 2, 1], [2, 1, 2, 1, 2, 1, 1], [2, 1, 1, 1, 1, 2, 1, 1],

    [2, 1, 1, 2, 2, 1, 1], [2, 1, 1, 2, 1, 1, 1, 1], [2, 1, 1, 2, 1, 2, 1],

    [2, 1, 1, 1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 2, 1],

    [2, 1, 1, 1, 2, 1, 1, 1], [2, 1, 1, 1, 2, 2, 1], [2, 1, 1, 1, 2, 1, 2],

    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 2, 1],

    [1, 1, 1, 1, 1, 2, 1, 1, 1], [1, 1, 1, 1, 1, 2, 2, 1],

    [1, 1, 1, 1, 1, 2, 1, 2], [1, 2, 2, 1, 2, 1, 1], [1, 2, 1, 1, 1, 2, 1, 1],

    [1, 2, 1, 2, 2, 1, 1], [1, 2, 1, 2, 1, 1, 1, 1], [1, 2, 1, 2, 1, 2, 1],

    [1, 2, 1, 1, 1, 1, 1, 1, 1], [1, 2, 1, 1, 1, 1, 2, 1],

    [1, 2, 1, 1, 2, 1, 1, 1], [1, 2, 1, 1, 2, 2, 1], [1, 2, 1, 1, 2, 1, 2],

    [1, 2, 1, 1, 1, 1, 1, 2], [1, 2, 1, 1, 1, 2, 2], [2, 1, 1, 1, 1, 1, 1, 2],

    [2, 1, 1, 1, 1, 2, 2], [2, 2, 1, 1, 2, 1, 1], [2, 2, 2, 2, 1, 1],

    [2, 2, 2, 1, 1, 1, 1], [2, 2, 2, 1, 2, 1], [2, 2, 1, 1, 1, 1, 1, 1],

    [2, 2, 1, 1, 1, 2, 1], [2, 2, 1, 2, 1, 1, 1], [2, 2, 1, 2, 2, 1],

    [2, 2, 1, 2, 1, 2], [2, 2, 1, 1, 1, 1, 2], [2, 2, 1, 1, 2, 2]}

Now we need to pass these to the reconstruct procedure. I'll also pass the verbose setting so we can see what it is doing:

> reconstruct(4, S, verbose);

Because [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] (1 repeated n-k times)
is a k-deletion of w, w has at most k exceedences and thus at least k 1's.
Furthermore, since all of w's k-deletions have at least one 1, w has at
least k+1 1's.
To find the >1 entries of w, we need only consider one of the shortest
k-deletions, e.g., [2, 2, 2, 2, 1, 1].
This k-deletion shows that the >1 entries of w are (in the correct order)
  [2, 2, 2, 2].
It remains to measure the runs of 1's in w.  Write w as
  (z[1] 1's), 2, (z[2] 1's), 2, ..., (z[4] 1's), 2, (z[5] 1's)
We then get:
  Since [1, 2, 2, 2, 2] is not contained in a k-deletion,
    z[1] = 0.
  Since [2, 1, 2, 2, 2] is not contained in a k-deletion,
    z[2] = 0.
  Since [2, 2, 1, 1, 2, 2] is contained in a k-deletion,
    z[3] >= 2.
  Since [2, 2, 2, 1, 2] is contained in a k-deletion,
    but [2, 2, 2, 1, 1, 2] is not,
    z[4] = 1.
  Since [2, 2, 2, 2, 1, 1] is contained in a k-deletion,
    z[5] >= 2.
Thus
  z >= [0, 0, 2, 1, 2].
Now we have to determine where the other 1 1's in w lie.
To do this we utilise the positions where u is 0.
  Since [1, 1, 1, 1, 1, 2, 2] is contained in a k-deletion,
    but [1, 1, 1, 1, 1, 1, 2, 2] is not,
    z[3] = 3.
  Since [1, 1, 2, 2, 1, 1, 1] is not contained in a k-deletion,
    z[5] = 2.
We now have that w contains
  [2, 2, 1, 1, 1, 2, 1, 2, 1, 1],
and since this is a composition of the desired integer (14), we are done.
                        [2, 2, 1, 1, 1, 2, 1, 2, 1, 1]

To save you time, the tear_down_and_reconstruct procedure does all these things at once.

For more information on any of the procedures run them without arguments, e.g.,

> tear_down_and_reconstruct();
tear_down_and_reconstruct(w): Given a composition w, computes the largest k for
        which w can surely be reconstructed from its k-deletions, i.e.,
        floor((n-1)/3) if w is a composition of n, and then passes this set
        of k-deletions to reconstruct();  Has a verbose mode (see 2nd example).
Examples:
        tear_down_and_reconstruct([5,1,2,2]);
        tear_down_and_reconstruct([5,1,2,2], verbose);

< back to homepage