# Algorithm for recovering paired lists when elements are broken

I am trying to solve an algorithmic problem. I came from http://math.stackexchange.com upon an advise that this forum would be a better place to ask this.

I would like to hear your advice on where to search for hints. If my problem has got a name, I would like to know what it is called in the field, and what I should learn to solve it. Any partial suggestion would be welcome. Also if there is another forum that fits my question better than here, I would be happy to hear that too.

A description of my problem is as follows. Suppose you have a number of pairs of objects. Let $X$ be the first list of objects and $Y$ be the second list. Assume $X = Y$ in a sense they share the same list of objects.

Now, objects in both lists are "broken" into pieces; Each element $x \in X$ is decomposed to $x_1, x_2,...$. The same happens for $Y$. As a result, what you have is two sets $X', Y'$, which contain the broken pieces of the original objects.
The task is to recover the original objects in $X$ and $Y$ from $X'$ and $Y'$.

Here is an example where objects are strings.
Suppose $X = Y = [apple, banana]$, and the strings are decomposed as: $X' = [ban, le, ana, app]$ and $Y' = [na, ple, ap, na, ba]$. I would like to recover $banana$ and $apple$ from information $X'$ and $Y'$.

Does this problem have a name? Or, what do you think the good things to learn for me to study this type of problem?

• Looks very similar to shotgun sequencing to me. Without further restrictions there is not necessarily a unique answer; are you satisfied with any answer? Which words are allowed outputs? (Consider the pathologic example of X=Y -- what should be the result?) Sep 6, 2016 at 23:24
• Hi, @Rapahel. Yes, I recognize that the answer is not unique, and I would prefer an answer with the longest list. In the (banana, apple) example above, there are three answers (banana and apple) (bananaapply) and (applebanana). Among them, the first one is preferred because it is longer than the others. If there are two or more answers with the same list lengths, then I would be good with any of them. Sep 7, 2016 at 0:51
• Also posted on Math.SE. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Sep 7, 2016 at 6:02