Как отсортировать массив массивов строк в js?

Question

[MariaCorneva]

Нужно выстроить вот такой массив:

[['butter', 'jelly'], ['bananas', 'apples'], ['peanuts', 'butter'], ['jelly', 'bananas']]

Вот в такой последовательности:

[['peanuts', 'butter'], ['butter', 'jelly'], ['jelly', 'bananas'], ['bananas', 'apples']]

То есть нужно, чтобы каждый второй элемент массива совпадал с первым элементом следующего массива.

Вот такой код срабатывает, но не всегда (не для всех кейсов):

routes.sort(([a, b], [c, d]) => {
     return b === c ? -1 : a === d ? 1 : 0 
})

Полагаю, нужно добавить еще условий. Вообще, алгоритм связан с направленными графами и на взрослых языках решается с помощью HashMap и reversed Hash Map, однако в JS вариант с сортировкой кажется самым лаконичным (эффективность не имеет значения)

Comments

[WbICHA]

Все пары уникальны (то есть во всём массиве массивов может быть только 2 'butter', к примеру, один в нулевом индексе и второй в первом) или могут повторяться?
Если первое, то всё просто, а если второе, то надо будет все возможные комбинации просчитать.
И метод сорт тут не поможет, поскольку ты не можешь знать в какую сторону сдвигать массив.

[MariaCorneva]

WbICHA, вообще, предполагается, что все пары уникальны, нужно просто собрать последовательность

Answer 1

[Дмитрий Беляев]

Данная задача в принципе не решается сортировкой, так как сортировка это про отношение больше/меньше/равно, которого в данном случае нет.
Самое простое здесь, это построить из этих элементов двусвязный список, а затем преобразовать его в результирующий массив:

function orderArray(arr) {
  // для начала построим ноды списка и соберем их в 2 HashMap по обоим строкам
  const maps = arr.reduce((acc, item) => {
    const node = {item, next: null, prev: null};
    acc[0][item[0]] = node;
    acc[1][item[1]] = node;
    return acc;
  }, [{}, {}]);

  // после пройдемся по обоим HashMap и соединим связи
  for(const key of Object.keys(maps[0])) {
    maps[0][key].next = maps[0][maps[0][key].item[1]] || null;
  }
  for(const key of Object.keys(maps[1])) {
    maps[1][key].prev = maps[1][maps[1][key].item[0]] || null;
  }

  // найдем начальную ноду списка (ноду без предыдущей ноды)
  let cur = Object.values(maps[0]).find(({prev}) => prev === null);

  // и начиная с нее соберем список в массив
  const result = [];
  while(cur) {
    result.push(cur.item);
    cur = cur.next;
  }

  return result;
}

console.log(orderArray([['butter', 'jelly'], ['bananas', 'apples'], ['peanuts', 'butter'], ['jelly', 'bananas']]));

Comments

[Роман]

Не могли бы вы мое решение глянуть на предмет недостатков?

Answer 2

[WbICHA]

Раз такое дело, Дмитрий Беляев, Роман, оцените.)

(() => {
  const orderArray = (arr) => {
    const itemsForMap = arr.map((items) => ([items[0], { items, prev: undefined }]))
    const itemsMap = new Map(itemsForMap);

    let last;
    itemsMap.forEach((node) => {
      const next = itemsMap.get(node.items[1]);
      if(next) {
        next.prev = node;
      }
      else {
        last = node;
      }
    });

    const result = [];
    result.length = arr.length;

    let current = last;
    for(let i = result.length - 1; i > -1; i--) {
      result[i] = current.items;
      current = current.prev;
    }

    return result;
  };
  
  return orderArray([['butter', 'jelly'], ['bananas', 'apples'], ['peanuts', 'butter'], ['jelly', 'bananas']]);
})()

Вроде всё верно, но я это в 7 утра перед сном писал...

Comments

[Роман]

Прикольно. Почему то я почти не пользуюсь Set-ами и Map-ами, но всегда интересно посмотреть практику их применения.