StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POAlgorithms: Interesting diffing algorithm
text
Body
copied!<p>This came up in a real-world situation, and I thought I would share it, as it could lead to some interesting solutions. Essentially, the algorithm needs to diff two lists, but let me give you a more rigorous definition of the problem.</p> <h1>Mathematical Formulation</h1> <p>Suppose you have two lists, <code>L</code> and <code>R</code> each of which contain elements from some underlying alphabet <code>S</code>. Moreover, these lists have the property that the common elements that they have appear in order: that is to say, if <code>L[i] = R[i*]</code> and <code>L[j] = R[j*]</code>, and <code>i</code> < <code>j</code> then <code>i</code>* < <code>j</code>*. The lists need not have any common elements at all, and one or both may be empty. [<em>Clarification: You may assume no repetitions of elements.</em>]</p> <p>The problem is to produce a sort of "diff" of the lists, which may be viewed as new list of ordered pairs <code>(x,y)</code> where <code>x</code> is from <code>L</code> and <code>y</code> is from <code>R</code>, with the following properties:</p> <ol> <li>If <code>x</code> appears in both lists, then <code>(x,x)</code> appears in the result.</li> <li>If <code>x</code> appears in <code>L</code>, but not in <code>R</code>, then <code>(x,NULL)</code> appears in the result.</li> <li>If <code>y</code> appears in <code>R</code>, but not in <code>L</code>, then <code>(NULL,y)</code> appears in the result.</li> </ol> <p>and finally</p> <ul> <li>The result list has "the same" ordering as each of the input lists: it shares, roughly speaking, the same ordering property as above with each of the lists individually (see example).</li> </ul> <h1>Examples</h1> <pre><code>L = (d) R = (a,b,c) Result = ((NULL,d), (a,NULL), (b,NULL), (c,NULL)) L = (a,b,c,d,e) R = (b,q,c,d,g,e) Result = ((a,NULL), (b,b), (NULL,q), (c,c), (d,d), (NULL,g), (e,e)) </code></pre> <p>Does anyone have any good algorithms to solve this? What is the complexity?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload