Эту проблему можно решить с помощью алгоритма Topological Sort .
Если вы считаете, что каждая из ваших входных последовательностей представляет собой путь через ориентированный граф, топологическая сортировка упорядочит ваш набор узлов слева направо так, что каждый направленный край будет указывать вправо.
Страница Википедии по Топологическая сортировка включает этот алгоритм, впервые описанный Артуром Каном в 1962 году:
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
Этот алгоритм, как написано, на самом деле не дает сбоя, если находит неоднозначные последовательности, но его легко добавить, вставив проверку в начале цикла, например:
...
while S is non-empty do
if S contains more than 1 item
return error (inputs are ambiguous)
remove a node n from S
...
Я не знаю, на каком языке вы работаете, но я собрал эту реализацию PHP в качестве доказательства концепции:
function mergeSequences($sequences, $detectAmbiguity = false) {
// build a list of nodes, with each node recording a list of all incoming edges
$nodes = array();
foreach ($sequences as $seq) {
foreach ($seq as $i => $item) {
if (!isset($nodes[$item])) $nodes[$item] = array();
if ($i !== 0) {
$nodes[$item][] = $seq[$i-1];
}
}
}
// build a list of all nodes with no incoming edges
$avail = array();
foreach ($nodes as $item => $edges) {
if (count($edges) == 0) {
$avail[] = $item;
unset($nodes[$item]);
}
}
$sorted = array();
$curr = '(start)';
while (count($avail) > 0) {
// optional: check for ambiguous sequence
if ($detectAmbiguity && count($avail) > 1) {
throw new Exception("Ambiguous sequence: {$curr} can be followed by " . join(' or ', $avail));
}
// get the next item and add it to the sorted list
$curr = array_pop($avail);
$sorted[] = $curr;
// remove all edges from the currently selected items to all others
foreach ($nodes as $item => $edges) {
$nodes[$item] = array_diff($edges, array($curr));
if (count($nodes[$item]) == 0) {
$avail[] = $item;
unset($nodes[$item]);
}
}
}
if (count($nodes) > 0) {
throw new Exception('Sequences contain conflicting information. Cannot continue after: ' . join(', ', $sorted));
}
return $sorted;
}
Вы можете вызвать функцию следующим образом:
$input = array(
array('XS', 'M', 'L', 'XL'),
array('S', 'M', 'XXL'),
array('XXS', 'XS', 'S', 'L'),
);
echo(join(', ', mergeSequences($input)));
echo(join(', ', mergeSequences($input, true)));
Чтобы получить следующий вывод:
XXS, XS, S, M, XXL, L, XL
Uncaught exception 'Exception' with message 'Ambiguous sequence: M can be followed by L or XXL'