Как отсортировать массив объектов без последовательного повторения двух конкретных свойств в Javascript?

Question

У меня есть следующий массив объектов со свойствами от и до :

[
    {order: 0, from: 'Birigui', to: 'Penápolis'},
    {order: 1, from: 'Birigui', to: 'Araçatuba'},
    {order: 2, from: 'Avanhandava', to: 'Penápolis'},
    {order: 3, from: 'Avanhandava', to: 'Araçatuba'},
    {order: 4, from: 'Penápolis', to: 'Araçatuba'},
    {order: 5, from: 'Birigui', to: 'Avanhandava'},
    {order: 6, from: 'Marilia', to: 'São Paulo'},
    {order: 7, from: 'Marilia', to: 'Birigui'},
    {order: 8, from: 'Marilia', to: 'Penápolis'},
]

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

Например, если первыйпункт в списке содержит «Биригуи» и «Пенаполис», второй элемент не может содержать «Биригуи» или «Пенаполис» ни в с , ни в до

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

[
    {order: 0, from: 'Birigui', to: 'Penápolis'},
    {order: 1, from: 'Marilia', to: 'São Paulo'},
    {order: 2, from: 'Birigui', to: 'Araçatuba'},
    {order: 3, from: 'Avanhandava', to: 'Penápolis'},
    {order: 4, from: 'Marilia', to: 'Birigui'},
    {order: 5, from: 'Penápolis', to: 'Araçatuba'},
    {order: 6, from: 'Birigui', to: 'Avanhandava'},
    {order: 7, from: 'Marilia', to: 'Penápolis'},
    {order: 8, from: 'Avanhandava', to: 'Araçatuba'},
]

Какой хороший способ добиться этого?

---

Решено

Я нахожу решение:

const from = [
  'Penápolis',
  'Araçatuba',
  'Birigui',
  'Avanhandava',
  'Venezuela',
]

const to = [
  'Japão',
  'Penápolis',
  'Venezuela',
  'Italia',
  'China',
]

let combinations = []

// Make combinations with all 'from' and all 'to'
from.forEach(fromCity => {
  to.forEach(toCity => {
    if (
      combinations.some(combination => combination.from === fromCity && combination.to === toCity) === false &&
      combinations.some(combination => combination.from === toCity && combination.to === fromCity) === false &&
      fromCity !== toCity) {
      combinations.push({from: fromCity, to: toCity})
    }
  })
})

// Create an array with unique city names
let cities = [...from, ...to]
const unique = function(arr) {
  var a = arr.concat()
  for(var i=0; i<a.length; ++i) {
      for(var j=i+1; j<a.length; ++j) {
        if(a[i] === a[j]) a.splice(j--, 1)
      }
  }
  return a
}
cities = unique(cities)

// Split cities in  groups
let groups = {}
while (combinations.length > 0) {
  cities.forEach(city => {
    if (groups[city] === undefined) groups[city] = []
    combinations.forEach((combination, index) => {
      if (combination.from === city || combination.to === city) {
        let removed = combinations.splice(index, 1)
        groups[city].push(...removed)
      }
    })
  })
}

// Sort city names by group length
cities.sort((a, b) => groups[b].length - groups[a].length)

// Make an array ordened by cities to push ordered in the list
let combinationsToPush = []
cities.forEach(city => combinationsToPush.push(...groups[city]))

// Sort the final list
let list = []
while (combinationsToPush.length > 0) {
  combinationsToPush.forEach((combination, index) => {
    // If list is empty, just add
    if (list.length === 0) list.push(...combinationsToPush.splice(index, 1))
    // If not...
    let i = 0
    // If first element of list is different, just add
    if (list[i].from !== combination.from && list[i].to !== combination.from && list[i].from !== combination.to && list[i].to !== combination.to) {
      list.splice(i, 0, ...combinationsToPush.splice(index, 1))
    // If not, run the entire list to find a place to put combination
    } else {
      while (i < list.length - 2) {
        i++
        if (list[i].from !== combination.from && list[i].to !== combination.from && list[i].from !== combination.to && list[i].to !== combination.to
          && list[i+1].from !== combination.from && list[i+1].to !== combination.from && list[i+1].from !== combination.to && list[i+1].to !== combination.to) {
            list.splice(i+1, 0, ...combinationsToPush.splice(index, 1))
        }
      }
    }
    // If not find a place to put the combination, the combination will wait for the next while run
  })
}
console.log(list)

Answer 1

Один из способов сделать это - разбить все элементы на from, отсортированные по количеству в группе.Начните с самой большой группы и чередуйте другие группы по порядку.Для самых больших групп может быть больше участников, чем для всех остальных вместе взятых, и в этом случае ваш вид невозможен.

let arr = [{order: 0, from: 'Birigui', to: 'Penápolis'},{order: 1, from: 'Birigui', to: 'Araçatuba'},{order: 2, from: 'Avanhandava', to: 'Penápolis'},{order: 3, from: 'Avanhandava', to: 'Araçatuba'},{order: 4, from: 'Penápolis', to: 'Araçatuba'},{order: 5, from: 'Birigui', to: 'Avanhandava'},{order: 6, from: 'Marilia', to: 'São Paulo'},{order: 7, from: 'Marilia', to: 'Birigui'},{order: 8, from: 'Marilia', to: 'Penápolis'},]

// group and sort by group length
let counts = Object.values(arr.reduce((obj, item) => {
    (obj[item.from] || (obj[item.from] = [])).push(item)
    return obj
}, {})).sort((a, b) => b.length - a.length)

// take largest group (broken into individual arrays)
let main = counts.shift().map(c => [c])

// take all others as a large group and interveave into main group
let rest = counts.reduce((arr, item) => arr.concat([...item]))
rest.forEach((item, i) => main[i % main.length].push(item))

// flatten the structure and correct the order numbers
let final = main.reduce((arr, item) => arr.concat([...item]))
final.forEach((item, i) => item.order = i)

 console.log(final)

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