<p>I have a number of string arrays. The string in every array are ordered the same way, according the same criteria. However, some string may be missing from some arrays, and there may be no array that has a complete set of strings. Moreover, the criteria used to compare the strings is not available to me: outside of the context of the array, I cannot tell which string should precede another.</p>

<p>I need a way to produce a complete set of strings, properly ordered. Or fail when the arrays do not have enough information for me to do so.</p>

<p>Is anyone familiar with this kind of problem? What is the proper algorithm?</p>

<p>Examples:</p>

<pre><code>A B D
A C D
</code></pre>

<p>Can't order correctly, can't decide the order of B and C </p>

<pre><code>A B D
A B C
A C D
</code></pre>

<p>This has enough information to order ABCD correctly.</p>

How many sets will you have? Something that might work if they aren't too sparse is:
Iterate over the first element of
all arrays counting how common each
string is.
Whichever element is the most common
is selected.
Check each element of all
arrays for said string.
If it exists in any element other than the first of an array, the first element of
its parent array is selected and goto step 3.
Remove the selected element from the
first element of all arrays/trees
and add it to the end of your output
list.
Goto 1 until all elements are
removed.
If you dumped the arrays into
b-trees
the element search could be pretty fast. You may also be able to further speed up step 3 by playing with the order of the arrays. I'm still thinking about that.
If the arrays are very sparse the only thing I can think of is to use some kind of supervised machine learning to try to determine the proper method for ordering.