World's most popular travel blog for travel bloggers.

# Algorithm for recovering paired lists when elements are broken

, ,
Problem Detail:

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?

###### Asked By : Kota Mori

Look at the literature on algorithms for the shotgun sequencing and shortest common supersequence problems. It appears that your problem might not be exactly identical to them, but researchers have developed sophisticated algorithmic techniques for handling this kind of problem. Therefore, I suspect you might be able to use the same techniques for your problem, or adapt them to work well for your situation.