2
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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?) $\endgroup$
    – Raphael
    Sep 6, 2016 at 23:24
  • $\begingroup$ 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. $\endgroup$
    – Kota Mori
    Sep 7, 2016 at 0:51
  • 3
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Sep 7, 2016 at 6:02

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.