2
$\begingroup$

I ave a a collection of lists of objects:

$a_1$ $a_2$ $a_3$...

$b_1$ $b_2$ $b_3$...

$c_1$ $c_2$ $c_3$..

I need to merge them into a minimal possible number of lists, each list must be as long as possible. The merge does as follows:

For every consequitve pair ($x_i$, $x_{i + 1}$) within the collection, if one or more subsequences ($x_i$, $y_j$, $y_{j + 1}$, ... $y_k$, $x_{i + 1}$) exists, substitute the pair with the longest said subsequence.

After all such substitutions are made, eliminate redundant lists as follows:

for every list $x_1$, $x_2$, ... $x_m$, if for each $j$ the subsequence ($x_j$, ... $x_{j + 1}$ exists in any other list, remove the whole list.

For example, this collection of two list of strings:

"a", "sheep", "grazing"
"a", "young", "white", "sheep"

Is to be merged into 

"a", "young", "white", "sheep", grazing"

This is because the subsequence in the second line

"a", "young", "white", "sheep"

can be squeezed between "a" and "sheep" of the first line, while

"sheep", "grazing", end-of-line of the first line can be squeezed between "sheep", end-of-line of the second line.

Likewise, if there is a list A1, ... AN in one of the lines, and another line starts with AN or ends with A1, the substitution is to occur.

However,

"a", "lonely", "sheep", "grazing"
"a", "young", "white", "sheep"

can't be merged into one list, because we don't know whether "lonely" should go before or after "young", before or after "white", etc.

So this case is to be partially merged into 

"a", "lonely", "sheep", "grazing"
"a", "young", "white", "sheep", "grazing"

Pseudocode welcome.

Improve this question
$\endgroup$
7
  • $\begingroup$ So you have a sequence of lists, each of the form $a_1, \dots, a_k$. You can merge $a_1, \dots, a_k$ with $b_1, \dots, b_\ell$ to give the list $a_1, \dots, a_i, b_2, \dots, b_{\ell-1} a_{i+1}\dots a_k$ if $a_i=b_1$ and $a_{i+1}=b_\ell$ (along with special cases to deal with $i=0$ and $i=k$ which I'll not list here). And your goal is to find the set of all sequences made by repeatedly merging from your initial set until no more merges are possible? It might be clearer to express the question in those sorts of terms, to avoid people thinking that the meaning of "sheep" might be significant. $\endgroup$ – David Richerby Jun 7 '16 at 14:58
  • 1
    $\begingroup$ Please edit the question to specify the exact criteria that the output must satisfy. It seems to me you are trying to specify by example ("if this situation arises, do this", where "this situation" might be something like " if there is a subsequence A1, A2, A3, .. AN in one of the lines, and a subsequence A1, AN in another"). The problem with this is that your list of examples/situations is not exhaustive, so it doesn't fully specify what should happen in all possible cases. Until you can precisely formulate the goal, it's premature to look for an algorithm to meet that goal. $\endgroup$ – D.W.♦ Jun 7 '16 at 15:03
  • $\begingroup$ This is a quite convoluted writeup. Is topological sort what you're after? $\endgroup$ – Raphael♦ Jun 7 '16 at 20:14
  • $\begingroup$ Yes it is.. that's why I tried with sheep :-) Can you hep me rephrase? $\endgroup$ – Ruby Jun 7 '16 at 21:52
  • $\begingroup$ topological sort might be one of the steps. $\endgroup$ – Ruby Jun 7 '16 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.