Zij $$A = (0, a_1, \ldots, a_{n-1})$$ een tuple van $$n$$ punten op een lijnsegment in stijgende volgorde ($$0 <  a_1 < \cdots < a_{n-1}$$). Door $$\Delta A$$ noteren we de collectie van alle paarsgewijze afstanden tussen punten in $$A$$. Bijvoorbeeld, als \[A = (0, 2, 4, 7)\] dan \[ \Delta A = (7, 5, 4, 3, 2, 2, 0, 0, 0, 0, 2, 2, 3, 4, 5, 7) \] Het turnpike problem vraagt ons om $$A$$ te reconstrueren uit $$\Delta A$$.

Opdracht

Schrijf een functie turnpike die een collectie (een list of een tuple) van integers $$L$$ als parameter krijgt. De functie moet een set teruggeven die alle tuples van integers $$A = (0, a_1, \ldots, a_{n-1})$$ met $$0 <  a_1 < \cdots < a_{n-1}$$ bevat zodanig dat $$\Delta A = L$$.

Voorbeeld

>>> turnpike((-10, -8, -7, -6, -5, -4, -3, -3, -2, -2, 0, 0, 0, 0, 0, 2, 2, 3, 3, 4, 5, 6, 7, 8, 10))
{(0, 2, 4, 7, 10), (0, 3, 6, 8, 10)}

Referenties

• Dakic T (2000). On the turnpike problem. Simon Fraser University, BC, Canada.

• Lemke P, Skiena SS, Smith WD (2003). Reconstructing sets from interpoint distances. In Discrete and computational geometry (Springer, Berlin, Heidelberg), 597–631.

• Lenstra AK, Lenstra HW, Lovász L (1982). Factoring polynomials with rational coefficients. Mathematische Annalen 261(4), 515–534.

• Rosenblatt J, Seymour PD (1982). The structure of homometric sets. SIAM Journal on Algebraic Discrete Methods 3(3), 343–350.

• Zhang Z (1994). An exponential example for a partial digest mapping algorithm. Journal of computational biology 1(3), 235–239.