Rplus · March 1, 2022 16:51 · Mar 1, 2022 · Mar 1, 2022 · Mar 1, 2022 · Feb 28, 2022
diff --git a/gen_chars_order_from_arrays.js b/gen_chars_order_from_arrays.js
@@ -23,7 +23,7 @@ function genOrder(data) {
       }
 
       // collect prev chars & remove dup item
-      all[j].prev = [...new Set(all[j].prev, prevChars)];
+      all[j].prev = [...new Set(all[j].prev.concat(prevChars))];
       prevChars.push(j);
     });
     return all;

diff --git a/gen_chars_order_from_arrays.js b/gen_chars_order_from_arrays.js
@@ -22,7 +22,7 @@ function genOrder(data) {
         };
       }
 
-      // collect prev chars
+      // collect prev chars & remove dup item
       all[j].prev = [...new Set(all[j].prev, prevChars)];
       prevChars.push(j);
     });

diff --git a/gen_chars_order_from_arrays.js b/gen_chars_order_from_arrays.js
@@ -23,7 +23,7 @@ function genOrder(data) {
       }
 
       // collect prev chars
-      all[j].prev = all[j].prev.concat(prevChars);
+      all[j].prev = [...new Set(all[j].prev, prevChars)];
       prevChars.push(j);
     });
     return all;

diff --git a/v2.js b/v2.js
@@ -0,0 +1,83 @@
+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;
+  }
+}
diff --git a/gen_chars_order_from_arrays.js b/gen_chars_order_from_arrays.js
@@ -45,10 +45,10 @@ function genOrder(data) {
     }, 1 /* base */);
   }
 
+  // reduce duplicated calc, but pass order = 0
   let getOrder = (char) => {
     let order = relations[char].order ?? -1;
 
-    // reduce duplicated calc, but pass order = 0
     if (order === -1) {
       order = relations[char].order = calcOrder(relations[char].prev) ;
     }

diff --git a/gen_chars_order_from_arrays.js b/gen_chars_order_from_arrays.js
@@ -1,53 +1,65 @@
 // Question from
 // https://twitter.com/RplusTW/status/1498288300934971401
-// inspired from @@esp10mm
+// inspired from @esp10mm
 
-// want to get all chars order from given array => [a, c, b, d]
-genCharsOrder([
+// want to get all order => [a, c, b, d]
+genOrder([
   ['c', 'b'],
   ['a', 'b', 'd'],
   ['a', 'c'],
 ]);
 
 
-function genCharsOrder(data) {
+
+function genOrder(data) {
   var relations = data.reduce((all, i) => {
     let prevChars = [];
     i.forEach(j => {
       if (!all[j]) {
-        all[j] = [];
+        all[j] = {
+          value: j,
+          prev: [],
+        };
       }
+
       // collect prev chars
-      all[j] = all[j].concat(prevChars);
+      all[j].prev = all[j].prev.concat(prevChars);
       prevChars.push(j);
     });
     return all;
   }, {});
   // {
-  //   "c": ["a"],
-  //   "b": ["c", "a"],
-  //   "a": [],
-  //   "d": ["a", "b"]
+  //   "c": { "value": "c", "prev": ["a"] },
+  //   "b": { "value": "b", "prev": ["c", "a"] },
+  //   "a": { "value": "a", "prev": [] },
+  //   "d": { "value": "d", "prev": ["a", "b"] }
   // }
 
-  function calcOrder(prevArr) {
+  let calcOrder = (prevArr) => {
     if (!prevArr.length) {
       return 0;
     }
+
     return prevArr.reduce((all, i) => {
-      return all + calcOrder(relations[i]);
-    }, 1);
+      return all + getOrder(i);
+    }, 1 /* base */);
   }
 
-  function sortOrder(a, b) {
-    return a.order - b.order;
+  let getOrder = (char) => {
+    let order = relations[char].order ?? -1;
+
+    // reduce duplicated calc, but pass order = 0
+    if (order === -1) {
+      order = relations[char].order = calcOrder(relations[char].prev) ;
+    }
+    return order;
   }
 
-  var charOrder = Object.keys(relations)
-    .map(i => ({
-      value: i,
-      order: calcOrder(relations[i]),
-    }));
+  for (let i in relations) {
+    relations[i].order = calcOrder(relations[i].prev);
+  }
 
-  return charOrder.sort(sortOrder).map(i => i.value);
+  return Object.values(relations)
+    .sort((a, b) => a.order - b.order)
+    .map(i => i.value);
 }
diff --git a/gen_chars_order_from_arrays.js b/gen_chars_order_from_arrays.js
@@ -0,0 +1,53 @@
+// Question from
+// https://twitter.com/RplusTW/status/1498288300934971401
+// inspired from @@esp10mm
+
+// want to get all chars order from given array => [a, c, b, d]
+genCharsOrder([
+  ['c', 'b'],
+  ['a', 'b', 'd'],
+  ['a', 'c'],
+]);
+
+
+function genCharsOrder(data) {
+  var relations = data.reduce((all, i) => {
+    let prevChars = [];
+    i.forEach(j => {
+      if (!all[j]) {
+        all[j] = [];
+      }
+      // collect prev chars
+      all[j] = all[j].concat(prevChars);
+      prevChars.push(j);
+    });
+    return all;
+  }, {});
+  // {
+  //   "c": ["a"],
+  //   "b": ["c", "a"],
+  //   "a": [],
+  //   "d": ["a", "b"]
+  // }
+
+  function calcOrder(prevArr) {
+    if (!prevArr.length) {
+      return 0;
+    }
+    return prevArr.reduce((all, i) => {
+      return all + calcOrder(relations[i]);
+    }, 1);
+  }
+
+  function sortOrder(a, b) {
+    return a.order - b.order;
+  }
+
+  var charOrder = Object.keys(relations)
+    .map(i => ({
+      value: i,
+      order: calcOrder(relations[i]),
+    }));
+
+  return charOrder.sort(sortOrder).map(i => i.value);
+}