Что такое хороший алгоритм и структура данных для перестановки предметов?

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

Моя цель - переупорядочить элементы, т.е. изменить последовательность (если возможно), чтобы зависимости не были повреждены.

Проверка: элемент может перемещаться, только если зависимости остаются нетронутыми: т.е.

• элемент может зависеть только от элементов, которые находятся над ним, т. е. их последовательность меньше последовательности элемента и наоборот, т. е.

• anЭлемент может иметь элементы в качестве зависимых, только если элементы находятся ниже элемента, то есть их последовательности превышают последовательность элементов

Например, если я скажу переместить (item3, 2) - я спрашиваючтобы переместить элемент 3 в положение 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']
}

обратите внимание на изменение последовательностей

Но если я скажу переместить (item3, 1), это не так,потому что item3 зависит от item1 - если яt перемещается в позицию 1, item1 перейдет в позицию 2, что делает недействительным правило, согласно которому элемент может зависеть только от элементов, находящихся над ним.

Мой код находится в рабочем состоянии, но я использовал больше if-elsesчем правильный алгоритм

Гибкость: элемент списка может быть помещен в любую структуру данных и может использоваться любой алгоритм

Answer 1

Некоторые предложения:

• Если ваши данные большие и имеют много зависимостей, может быть более эффективно использовать Set для регистрации зависимостей вместо массива.
• Исключить одно из dependsOn или dependable, поскольку одно может быть получено из другого
• Не хранить seq, а просто полагаться на индекс, который элемент имеет вмассив. Правда, это означает, что вам нужно сканировать массив с помощью indexOf, но, с другой стороны, вам не придется обновлять все свойства seq, связанные с перемещением.
• Использовать нулииндексы вместо позиций, начинающихся с 1.

Вот class реализация структуры данных, которую я предлагаю.

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"));

Answer 2

Вы можете проверить зависимости по их индексу в списке требуемых новых узлов.

function move(node, position) {
    var nodes = Object.keys(itemList).sort(({ seq: a }, { seq: b }) => a - b);

    nodes.splice(position - 1, 0, ...nodes.splice(itemList[node].seq - 1, 1));

    var valid = nodes.every((n, i) =>
            dependencyDict[n].dependsOn.every(m => nodes.indexOf(m) <= i) &&
            dependencyDict[n].dependable.every(m => nodes.indexOf(m) >= i)
        );

    console.log(valid);
    if (valid) nodes.forEach((node, i) => itemList[node].seq = i + 1);
    console.log(nodes);
    console.log(itemList);
}

var dependencyDict = {
        item1: {dependsOn: [], dependable: ['item3']},
        item2: {dependsOn: [], dependable: []},
        item3: {dependsOn: ['item1'], dependable: ['item4']},
        item4: {dependsOn: ['item4'], dependable: []}
    },
    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'] }
    };

move('item3', 1);
move('item3', 2);

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