javascript - 什么是重新排列项目的好算法和数据结构？

Question

假设我有一些项目，每个项目都有一个序列 - 较小的序列意味着项目在上面。一个项目可以对其他项目具有依赖性/依赖性。此外，一个项目可以有依赖项——即其他一些项目可能依赖于它。下面的项目列表(我在这里使用了关联数组)列出了项目 - 每个项目的属性“dep”列出了依赖项和可依赖项。

var dependencyDict = {
  item1: {dependsOn: [], dependable: ['item3']},
  item2: {dependsOn: [], dependable: []},
  item3: {dependsOn: ['item1'], dependable: ['item4']},
  item4: {dependsOn: ['item3'], dependable: []}
}

var itemList  = {
  item1: {
    name: 'item1',
    seq: 1,
    dep: dependencyDict['item1']
  },
  item2: {
    name: 'item2',
    seq: 2,
    dep: dependencyDict['item2']
  },
  item3: {
    name: 'item3',
    seq: 3,
    dep: dependencyDict['item3']
  },
  item4: {
    name: 'item4',
    seq: 4,
    dep: dependencyDict['item4']
  }
}

根据上面的顺序，项目的顺序是这样的:

item1
item2
item3
item4

我的目标是重新排序项目，即更改顺序(如果可能)，以便相关性完好无损。

验证:只有当相关性保持不变时，项目才能移动:即

• 一个项目只能依赖于它上面的项目，即它们的顺序小于项目的顺序 反之亦然

• 只有当项目低于项目时，项目才能将项目作为依赖项，即它们的序列大于项目的序列

例如，如果我说 move(item3, 2) - 我要求将 item3 移动到位置 2，这样新的项目列表应该是这样的:

{
  item1: {
    name: 'item1',
    seq: 1,
    dep: dependencyDict['item1']
  },
  item2: {
    name: 'item2',
    seq: 3,
    dep: dependencyDict['item2']
  },
  item3: {
    name: 'item3',
    seq: 2,
    dep: dependencyDict['item3']
  },
  item4: {
    name: 'item4',
    seq: 4,
    dep: dependencyDict['item4']
}

注意序列的变化

但是如果我说 move(item3, 1)，它不会，因为 item3 依赖于 item1 - 如果它移动到位置 1，item1 将转到位置 2，这使项目只能依赖于项目的规则无效在它之上。

我的代码处于工作状态，但我使用的 if-elses 多于正确的算法

灵 active :itemlist可以放在任何数据结构中，可以使用任何算法

Answer 1

一些建议:

• 如果您的数据很大并且有很多依赖项，使用 Set 来注册依赖项可能比使用数组更有效。
• 消除dependsOn 或dependable 中的一个，因为一个可以从另一个派生
• 不存储seq，而是仅依赖于数组中项目的索引。没错，这意味着您必须使用 indexOf 扫描数组，但另一方面，您不必对移动中涉及的所有 seq 属性进行更新。
• 使用从零开始的索引，而不是从 1 开始的位置。

这是我建议的数据结构的类实现。

class OrderedGraph {
    constructor(pairs) {
        this._dep = new Map;
        this._order = [];
        if (pairs) for (let [item, dependsOn] of pairs) this.add(item, dependsOn);
    }
    add(item, dependsOn=[]) {
        for (let ref of dependsOn) if (!this._dep.has(ref)) throw ref + " not found";
        this._dep.set(item, new Set(dependsOn));
        this._order.push(item);
    }
    move(item, toIdx) {
        let fromIdx = typeof item === "number" ? item : this._order.indexOf(item);
        if (fromIdx < 0) throw "not found: " + item
        if (typeof item === "number") item = this._order[item];
        let dep = this._dep.get(item);
        let ok = fromIdx > toIdx
            ? !this._order.slice(toIdx, fromIdx).some(it => dep.has(it))
            : !this._order.slice(fromIdx+1, toIdx+1).some(it => this._dep.get(it).has(item));
        if (ok) this._order.splice(toIdx, 0, ...this._order.splice(fromIdx, 1));
        return ok;
    }
    indexOf(item)  { return this._order.indexOf(item) }
    includes(item) { return this._dep.has(item) }
    * values()     { yield * this._order }
    [Symbol.iterator]() { return this.values() }
}

// Example use
let data = new OrderedGraph([
    ["item1", []],
    ["item2", []],
    ["item3", ["item1"]],
    ["item4", ["item3"]]
]);

// Some actions on the data object:
console.log(JSON.stringify(Array.from(data)));
console.log("success moving 'item3' to 0? ", data.move("item3", 0));
console.log(JSON.stringify(Array.from(data)));
console.log("success moving 'item3' to 1? ", data.move("item3", 1));
console.log(JSON.stringify(Array.from(data)));
console.log("success moving 'item3' to 1? ", data.move("item3", 1));
console.log(JSON.stringify(Array.from(data)));
console.log("success moving 'item3' to 2? ", data.move("item3", 2));
console.log(JSON.stringify(Array.from(data)));
console.log("index of 'item3': ", data.indexOf("item3"));