按匹配的起始节点和结束节点对项目进行排序

Question

假设我有一个随机打乱的数组，其中包含不同组别的碎片。例如：

let pieces = [
  {
    id: "a1",
    startNode: 18,
    endNode: 42,
  },
  {
    id: "a3",
    startNode: 16,
    endNode: 30,
  },
  {
    id: "b2",
    startNode: 48,
    endNode: 65,
  },
  {
    id: "a2",
    startNode: 42,
    endNode: 16,
  },
  {
    id: "a4",
    startNode: 30,
    endNode: 31,
  },
  {
    id: "b1",
    startNode: 23,
    endNode: 48,
  },
];

我希望它们以正确的顺序返回为两个数组：

ordered = [
  [
    {
      id: "a1",
      startNode: 18,
      endNode: 42,
    },
    {
      id: "a2",
      startNode: 42,
      endNode: 16,
    },
    {
      id: "a3",
      startNode: 16,
      endNode: 30,
    },
    {
      id: "a4",
      startNode: 30,
      endNode: 31,
    },
  ],[
    {
      id: "b1",
      startNode: 23,
      endNode: 48,
    },
    {
      id: "b2",
      startNode: 48,
      endNode: 65,
    },
  ]
];

它们按照匹配的起始和结束节点排序，因此"a2"排在"a1"之后，因为它的startNode与"a1"的endNode匹配。 "b1"和"b2"属于另一组，因为它们与任何"a"组没有共享起始或结束节点。id不能用于排序，仅用于澄清此处。

有关如何实现它的任何想法吗？我认为它需要某种递归函数，但我无法完全理解。

- s.haensch

Answer 1

您可以使用迭代方法对子结果和实际（外部）元素进行迭代处理。

这个单一元素会将所有匹配的起始节点和结束节点收集到一个数组中，而其他不匹配的节点则被过滤，并在后面与收集的数组连接。

var pieces = [{ id: "a1", startNode: 18, endNode: 42 }, { id: "a3", startNode: 16, endNode: 30 }, { id: "b2", startNode: 48, endNode: 65 }, { id: "a2", startNode: 42, endNode: 16 }, { id: "a4", startNode: 30, endNode: 31 }, { id: "b1", startNode: 23, endNode: 48 }],
    result = pieces.reduce(function (r, a) {
        var temp = [a];
        return r.filter(function (b) {
            if (temp[temp.length - 1].endNode === b[0].startNode) {
                temp = temp.concat(b);
                return;
            }
            if (temp[0].startNode === b[b.length - 1].endNode) {
                temp = b.concat(temp);
                return;
            }
            return true;
        }).concat([temp]);
    }, []);

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

- Nina Scholz

---

哇，妮娜，这真的很管用。我还尝试了更多的数据，它也像魔法一样工作。现在我需要非常仔细地看看你使用的过滤函数。非常感谢你。 - s.haensch

Answer 2

尝试使用简单的 Array#sort() => 以 a.id > b.id 的方式排序。

let pieces = [ { id: "a1", startNode: 18, endNode: 42, }, { id: "a3", startNode: 16, endNode: 30, }, { id: "b2", startNode: 48, endNode: 65, }, { id: "a2", startNode: 42, endNode: 16, }, { id: "a4", startNode: 30, endNode: 31, }, { id: "b1", startNode: 23, endNode: 48, }, ];

console.log(pieces.sort((a,b)=> a.id > b.id))

不支持在ES5中使用箭头函数=>

   console.log(
    pieces.sort(function(a,b){
    return a.id > b.id})
    )

- prasanth

---

尽管这对测试用例有效，但我认为排序应该是startNode == previous endNode。 - James

抱歉，但id和node值实际上是一些任意的9位数字序列。我在这里修改了它们以便更易读。它们不能用于排序，只有node值可以。 - s.haensch