Как изменить порядок массива, чтобы иметь ключ в порядке возрастания на основе массива значений?

Я пытаюсь выполнить миграцию базы данных и столкнулся с хронологической проблемой. Я не могу изменить поведение, поэтому мне нужно как-то с этим справляться.

Предположим, у меня есть следующий массив,

const arr = [
  { model: 'modelE', associations: ['modelA'], order: 1 },
  { model: 'modelA', associations: [ 'modelB' ], order: 2 },
  { model: 'modelB', associations: [], order: 3 },
  { model: 'modelC', associations: ['modelA', 'modelB'], order: 4 },
  { model: 'modelD', associations: ['modelA'], order: 5 },
  { model: 'modelF', associations: [], order: 6 },
]

Как мы знаем, мы должны создавать эти таблицы по порядку, иначе внешние ключи не могут быть созданы и, следовательно, будет выброшена ошибка.

В этом случае у нас есть modelE, modelC и modelD, которые зависят от modelA, но modelA зависит от modelB, поэтому modelB должен быть первым элементом в этом массиве, потому что это должна быть первая создаваемая таблица.

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

const arr = [
  { model: 'modelB', associations: [], order: 1 },
  { model: 'modelF', associations: [], order: 2 },
  { model: 'modelA', associations: [ 'modelB' ], order: 3 },
  { model: 'modelC', associations: ['modelA', 'modelB'], order: 4 },
  { model: 'modelE', associations: ['modelC'], order: 5 },
  { model: 'modelD', associations: ['modelA'], order: 6 },
]

Есть ли эффективный способ сделать это? Все, о чем я могу думать, это запустить функцию sort с arr.find внутри нее. Не уверен, что это слишком производительно или даже читабельно.

Могут ли быть циклические зависимости? Для меня это больше похоже на ориентированный граф/дерево, чем на проблему сортировки массива. Используйте однажды построенный граф/дерево, чтобы создать массив в порядке, который работает.

D M 16.05.2022 22:40

Решение может быть любым

Mike K 16.05.2022 22:40
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Сравнение структур данных: Массивы и объекты в Javascript
Сравнение структур данных: Массивы и объекты в Javascript
Итак, вы изучили основы JavaScript и хотите перейти к изучению структур данных. Мотивация для изучения/понимания Структур данных может быть разной,...
Создание собственной системы электронной коммерции на базе Keystone.js - настройка среды и базовые модели
Создание собственной системы электронной коммерции на базе Keystone.js - настройка среды и базовые модели
Прошлая статья была первой из цикла статей о создании системы электронной коммерции с использованием Keystone.js, и она была посвящена главным образом...
Приложение для отслеживания бюджета на React js для начинающих
Приложение для отслеживания бюджета на React js для начинающих
Обучение на практике - это проверенная тема для достижения успеха в любой области. Если вы знаете контекст фразы "Практика делает человека...
Стоит ли использовать React в 2022 году?
Стоит ли использовать React в 2022 году?
В 2022 году мы все слышим о трендах фронтенда (React, Vue), но мы не знаем, почему мы должны использовать эти фреймворки, когда их использовать, а...
1
2
36
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Вы ищете топологическая упорядоченность.

Для этого вы можете использовать алгоритм поиска в глубину:

function topoSort(arr) {
    const visited = new Set;
    const map = new Map(arr.map(({model, associations}) => [model, associations]));
    
    function dfs(models) {
        for (let model of models) {
            if (visited.has(model)) continue;
            dfs(map.get(model));
            visited.add(model);
        }
    }
    
    dfs([...map.keys()]);
    return Array.from(visited, (model, i) => 
        ({model, associations: map.get(model), order: i+1})
    );
}

const arr = [
  { model: 'modelE', associations: ['modelA'], order: 1 },
  { model: 'modelA', associations: [ 'modelB' ], order: 2 },
  { model: 'modelB', associations: [], order: 3 },
  { model: 'modelC', associations: ['modelA', 'modelB'], order: 4 },
  { model: 'modelD', associations: ['modelA'], order: 5 },
  { model: 'modelF', associations: [], order: 6 },
]
const result = topoSort(arr);
console.log(...result);

Я получаю результат, отличный от того, что хотел OP {ассоциации: [], модель: "modelB", порядок: 1}, {ассоциации: ["modelB"], модель: "modelA", порядок: 2}, { ассоциации: ["modelA"], модель: "modelE", порядок: 3}, { ассоциации: ["modelA", "modelB"], модель: "modelC", порядок: 4}, { ассоциации: ["modelA" ], модель: "modelD", порядок: 5 }, { ассоциации: [], модель: "modelF", порядок: 6 }

Chris G 16.05.2022 23:36

Я тоже это заметил, но ничего страшного, если модель F будет последней. Он не имеет зависимостей и от него ничего не зависит, поэтому его можно создать в любое время.

Mike K 17.05.2022 09:33

Топологическое упорядочение не обязательно уникально. Для рассматриваемого примера существует несколько допустимых топологических порядков.

trincot 17.05.2022 10:12

const sortArrayByDependency = (arr) => {
  const sorted = [];
  const foundSet = new Set();
  const maxLoop = arr.length;
  let loopCount = 0;
  
  while(arr.length > 0 && loopCount < maxLoop) {
    loopCount += 1;
    const first = arr.shift();
    if(first.associations.every(ele => foundSet.has(ele))){
      sorted.push({...first, order: sorted.length + 1 });
      foundSet.add(first.model)
    }
    else {
      arr.push(first)
    }
  }
  
  return sorted;
}

const arr = [
  { model: 'modelB', associations: [], order: 1 },
  { model: 'modelF', associations: [], order: 2 },
  { model: 'modelA', associations: [ 'modelB' ], order: 3 },
  { model: 'modelC', associations: ['modelA', 'modelB'], order: 4 },
  { model: 'modelE', associations: ['modelC'], order: 5 },
  { model: 'modelD', associations: ['modelA'], order: 6 },
]

console.log(sortArrayByDependency(arr))

Этот ответ дает правильное решение в соответствии с тем, что опубликовал ОП.

Chris G 16.05.2022 23:41

Другие вопросы по теме