Điều này có thể được giải quyết bằng thuật toán Topological Sort.
Nếu bạn xem mỗi chuỗi đầu vào của bạn là một đường dẫn thông qua biểu đồ được chỉ dẫn, sắp xếp topo sẽ sắp xếp các nút của bạn từ trái sang phải theo cách mà mỗi cạnh được hướng sang phải. 
Các trang wikipedia trên Topological Sorting bao gồm thuật toán này, lần đầu tiên được mô tả bởi Arthur Kahn năm 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)
thuật toán này, như viết tay, không thực sự thất bại nếu nó tìm thấy chuỗi mơ hồ, nhưng đó là dễ dàng để thêm bằng cách chèn một dấu kiểm ở đầu vòng lặp, như sau:
...
while S is non-empty do
if S contains more than 1 item
return error (inputs are ambiguous)
remove a node n from S
...
Tôi không biết bạn đang làm việc với ngôn ngữ nào, nhưng tôi đã cùng nhau triển khai thực hiện PHP này của khái niệm:
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;
}
Bạn có thể gọi hàm như thế này:
$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)));
Để có được kết quả như sau:
XXS, XS, S, M, XXL, L, XL
Uncaught exception 'Exception' with message 'Ambiguous sequence: M can be followed by L or XXL'
Tôi không hiểu cách bạn có thể hợp nhất các danh sách nếu các quy tắc ưu tiên không xác định. –
@TylerDurden Tôi đã chỉnh sửa câu hỏi để hy vọng làm cho nó rõ ràng hơn một chút. cái đó có giúp ích không? – jcsanyi
Không, làm thế nào là nó mà bạn quyết định nơi XXL là liên quan đến L và XL? –