generate chars order from given array

gen_chars_order_from_arrays.js

// 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);
}

v2.js

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;
  }
}

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