Забавная проблема для решения;Я думаю, что только частично добился успеха.
- Я проигнорировал "недостаточно конкретный" пример
B -> A -> T против T -> B -> A - Это очень неэффективно
Тем не менееопубликовать, потому что я думаю, что это может помочь вам сделать все правильно.Вот мой подход:
Шаг 1: создать наивный индекс
Мы создаем объект, который для каждого уникального элемента во вложенных массивах отслеживает, какой ему предшествовал или предшествовал:
{
"X": { prev: Set({}), next: Set({ "D", "H", "B", "K", "Z", "A", "M", "T" })
"M": { prev: Set({ "X" }), next: Set({ "D", "H", "B" })
// etc.
}
Я назвал это «наивным», потому что эти наборы содержат информацию только одного уровня.
То есть: они сообщают только об отношениях между элементами, которые были в одном массиве.Они не могут видеть, что M предшествует K, потому что они никогда не были в одном и том же массиве.
Шаг 2: рекурсивное объединение индексов
Здесь я проигнорировал всеБиг-о проблем, которые можно иметь ?.Я рекурсивно объединяю индекс: next из M является объединением next из D, H, B.Повторяйте, пока не найдете элемент, который не имеет next, то есть T или A.
Шаг 3: создайте сортировщик, который учитывает индекс сортировки:
const indexSorter = idx => (a, b) =>
idx[a].next.has(b) || idx[b].prev.has(a) ? -1 :
idx[a].prev.has(b) || idx[b].next.has(a) ? 1 :
0 ;
Эта функция создает метод сортировки, который использует сгенерированный индекс для поиска порядка сортировки между любыми двумя элементами.
Объединение всего этого вместе:
(function() {
const naiveSortIndex = xss => xss
.map(xs =>
// [ prev, cur, next ]
xs.map((x, i, xs) => [
xs.slice(0, i), x, xs.slice(i + 1)
])
)
// flatten
.reduce((xs, ys) => xs.concat(ys), [])
// add to index
.reduce(
(idx, [prev, cur, next]) => {
if (!idx[cur])
idx[cur] = {
prev: new Set(),
next: new Set()
};
prev.forEach(p => {
idx[cur].prev.add(p);
});
next.forEach(n => {
idx[cur].next.add(n);
});
return idx;
}, {}
);
const expensiveSortIndex = xss => {
const naive = naiveSortIndex(xss);
return Object
.keys(naive)
.reduce(
(idx, k) => Object.assign(idx, {
[k]: {
prev: mergeDir("prev", naive, k),
next: mergeDir("next", naive, k)
}
}), {}
)
}
const mergeDir = (dir, idx, k, s = new Set()) =>
idx[k][dir].size === 0
? s
: Array.from(idx[k][dir])
.reduce(
(s, k2) => mergeDir(dir, idx, k2, s),
new Set([...s, ...idx[k][dir]])
);
// Generate a recursive sort method based on an index of { key: { prev, next } }
const indexSorter = idx => (a, b) =>
idx[a].next.has(b) || idx[b].prev.has(a) ? -1 :
idx[a].prev.has(b) || idx[b].next.has(a) ? 1 :
0;
const uniques = xs => Array.from(new Set(xs));
// App:
const arrays = [
['X', 'D', 'H', 'B'],
['X', 'D', 'K', 'Z', 'H', 'B', 'A'],
['X', 'M', 'D', 'H', 'B'],
['X', 'H', 'T'],
['X', 'D', 'H', 'B']
];
const sortIndex = expensiveSortIndex(arrays);
const sorter = indexSorter(sortIndex);
console.log(JSON.stringify(
uniques(arrays.flat()).sort(sorter)
))
}())
Рекомендации
Полагаю, элегантное решение проблемы могло бы пропустить все объединения Set с помощью связанного списка / дерева-подобная структура и внедрение элементов в правильные индексы путем обхода, пока не будет найден элемент его prev / next.