Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
generate chars order from given array
// Question from
// https://twitter.com/RplusTW/status/1498288300934971401
// inspired from @esp10mm
// want to get all order => [a, c, b, d]
genOrder([
['c', 'b'],
['a', 'b', 'd'],
['a', 'c'],
]);
function genOrder(data) {
var relations = data.reduce((all, i) => {
let prevChars = [];
i.forEach(j => {
if (!all[j]) {
all[j] = {
value: j,
prev: [],
};
}
// collect prev chars & remove dup item
all[j].prev = [...new Set(all[j].prev.concat(prevChars))];
prevChars.push(j);
});
return all;
}, {});
// {
// "c": { "value": "c", "prev": ["a"] },
// "b": { "value": "b", "prev": ["c", "a"] },
// "a": { "value": "a", "prev": [] },
// "d": { "value": "d", "prev": ["a", "b"] }
// }
let calcOrder = (prevArr) => {
if (!prevArr.length) {
return 0;
}
return prevArr.reduce((all, i) => {
return all + getOrder(i);
}, 1 /* base */);
}
// reduce duplicated calc, but pass order = 0
let getOrder = (char) => {
let order = relations[char].order ?? -1;
if (order === -1) {
order = relations[char].order = calcOrder(relations[char].prev) ;
}
return order;
}
for (let i in relations) {
relations[i].order = calcOrder(relations[i].prev);
}
return Object.values(relations)
.sort((a, b) => a.order - b.order)
.map(i => i.value);
}
genOrder([
['c', 'b'],
['a', 'b', 'd'],
['a', 'c'],
]);
function genOrder(data) {
// 將所有關係打散為前後兩兩一組
// 再直接遞迴遞增序號
const spliter = '___';
const relations = data.map(i => {
let str = i.join(spliter);
let reg = new RegExp(`(?=([^${spliter}]${spliter}[^${spliter}]))`, 'g');
return Array.from(str.matchAll(reg), x => x[1].split(spliter));
})
.flat();
const chars = [...new Set(relations.flat())]
.reduce((all, char) => {
all[char] = {
char: char,
prev: [],
}
return all;
}, {});
relations.forEach(relation => {
chars[relation[1]].prev = [...new Set([
...chars[relation[1]].prev, relation[0]
])];
});
for (let i in chars) {
chars[i].order = 0;
chars[i].order = calcCharOrder(i);
}
let output = Object.values(chars).sort(sortCharOrder);
// check
{
if (output.findIndex(i => i.order === 0) === -1) {
console.warn('contradiction for 1st item', output);
}
let checking = output.reduce((all, i) => {
if (!all[i.order]) {
all[i.order] = {
order: i.order,
chars: [],
}
}
all[i.order].chars.push(i.char);
return all;
}, [])
.filter(i => i.chars.length > 1);
if (checking.length) {
console.warn('dup. order', checking);
}
}
return output.map(i => i.char);
function calcCharOrder(char) {
let prevArr = chars[char].prev;
if (!prevArr.length) { return 0; }
return prevArr.reduce((all, i) => {
let order = chars[i].order ?? calcCharOrder(i);
// save order to reduce calculation
if (isNaN(chars[i].order)) {
chars[i].order = order;
}
return all + order;
}, 1 /* upup! */ )
}
function sortCharOrder(a, b) {
return a.order - b.order;
}
}
@Rplus
Copy link
Author

Rplus commented Feb 28, 2022

There is still an issue of incomplete condition.
[aa,bb,dd] [aa,cc] [cc,dd] => can't make sure order of bb & cc.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment