1
$\begingroup$

(This is crosslisted in math since I'm not sure how hard the problem is. https://math.stackexchange.com/questions/4663912/reproducing-an-ordered-list-of-numbers-from-partial-sums)

Given a list of (not necessarily distinct) positive integers, $a=(a_1,...,a_n)$, can one reproduce the list (up to reversing the order, i.e. reproduce $(a_1,...,a_n)$ or $(a_n,...,a_1)$) from the underlying multiset, $\{a_1,a_2,...,a_n\}$ and the unordered pairs, $$\left\{\left\{\sum_{i=1}^k a_i,\sum_{i=k+1}^n a_i\right\}\right\}_{k\in [n]}, \quad \left\{\left\{\sum_{i=1}^k (a_i+1),\sum_{i=k+1}^n (a_i+1)\right\}\right\}_{k\in [n]}?$$

If not, how about with the information of any number of `cuts' i.e.

$$\left\{\left\{\sum_{i=1}^{k_1} a_i,\sum_{i=k_1+1}^{k_2} a_i, ..., \sum_{i=k_{l}+1}^n a_i\right\}\right\}_{k\in [n],l\in\mathbb{N}}, \quad \left\{\left\{\sum_{i=1}^{k_1} (a_i+1),\sum_{i=k_1+1}^{k_2} (a_i+1), ..., \sum_{i=k_{l}+1}^n (a_i+1)\right\}\right\}_{k\in [n],l\in\mathbb{N}}?$$

I know that if you don't also consider the collection of terms with $a_i+1$, you can't distinguish $(1,2,1,3,2)$ and $(1,3,2,1,2)$. (For more information about the cases which can't be distinguished, see https://personal.math.ubc.ca/~steph/papers/elsarticle-weightedchrom.pdf)

As an example, if the list was $(1,2,1,3,2)$ I would be given the multisets $\{1,1,2,2,3\}$, $\{\{1,8\},\{2,7\},\{3,6\},\{4,5\}\}$, and $\{\{2,12\},\{3,11\},\{5,9\},\{7,7\}\}$. (You can distinguish which set you are looking at by looking at the sum of the terms, or the minimal elements.)

In the crosslisting, Sil mentioned that the lists $(1,2,1,3,1,2)$ and $(1,2,3,1,1,2)$ aren't distinguished by the single cuts.

$\endgroup$

1 Answer 1

1
$\begingroup$

This problem is considered and solved in the course of sequencing peptides - e.g. see algorithms described in Chapter 4. How Do We Sequence Antibiotics?. In reality they solve even harder problem obscured by missing data and small variations in $a_i$ (see Chapter 11 in the same textbook).

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.