Как найти начальную точку для определения маршрутов в двумерном массиве?

JavaScript Алгоритмы

1 ответ

Здраствуйте. Возможно очень странно сформулировал вопрос за это извините. Решая задачу наткнулся на одну проблему. Есть входной двумерный массив с странами:
[["USA", "BRA"], ["JPN", "PHL"], ["BRA", "UAE"], ["UAE", "JPN"]]

Нужно вывести правильную последовательность следования маршрутов объединив элементы массива в одну строку. Вот такой результат должен вывестись:
"USA, BRA, UAE, JPN, PHL"

Всё бы ничего и мой код работал бы (чуть ниже), если бы был известен начальный маршрут от которого нужно отталкиваться. Если поменять местами входные данные то мой код перестаёт выдавать правильную последовательность. Точка начала маршрута у меня находиться в переменной initialRoute. Пример:
[["JPN", "PHL"], ["USA", "BRA"], ["BRA", "UAE"], ["UAE", "JPN"]],
Вывод: "JPN, PHL"

Вот мой код

function findRoutes(routes) {   const dictionary = {};   // Точка начала маршрута    const initialRoute = routes[0][0];   const stack = [initialRoute];    routes.forEach((el) =&gt; {     dictionary[el[0]] = el[1];   });    function checkRoutesPos(dictionary, initialRoute) {     let thisRoute = initialRoute;     let pushElem = dictionary[thisRoute];     while (pushElem !== undefined) {       thisRoute = dictionary[thisRoute];       stack.push(pushElem);       pushElem = dictionary[thisRoute];     }   }   checkRoutesPos(dictionary, initialRoute);   return stack.join(", "); } console.log(   findRoutes([     ["USA", "BRA"],     ["JPN", "PHL"],     ["BRA", "UAE"],     ["UAE", "JPN"],   ]) ); console.log(   findRoutes([     ["JPN", "PHL"],     ["USA", "BRA"],     ["BRA", "UAE"],     ["UAE", "JPN"],   ]) );

Дополнительно:

Какова задача? Путь должен пройти все точки по одному разу? Повторять точки и переходы нельзя?

Какие данные гарантируются условием? Может ли быть два разных перехода из одной страны? Или в одну страну? Могут ли быть циклы?

Данные из примера выстраиваются в цепочку без циклов и ветвлений. Для такого частного случая надо найти стартовую страну (в которую нет перехода), построить хештаблицу (Map) в для переходов, чтобы быстро искать, куда летим из каждой точки, и далее циклом выстроить цепь, итого O(n) действий и несколько строк кода.

Но в общем случае всё будет куда сложнее, как по асимптотике, так и по реализации.

Alexandroppolus, На вход приходит двумерный массив в подмассивах которого может быть только 2 элемента. Пример:
[ [Москва, Омск], [Омск, Новгород], [Новгород, Волгоград] ]

Нужно получить последовательность чтобы сохранялась вся цепочка. Вывод для выше указанного примера должен быть таким:
Москва, Омск, Новгород, Волгоград

Так как Москва начальная точка из которого идёт путь, с неё инэ начинается последовательность.
Из Москвы мы попадаем в Омск (Так как есть элемент [Москва, Омск])
из Омска в Новгород (Так как есть элемент [Омск, Новгород]),
а из Новгорода в Тюмень (Так как есть элемент [Новгород, Тюмень])

В двумерном массиве подмассивы могут быть в разном порядке. Моя проблема в том что я не могу понять как узнать от какого подмассива начинается последовательность

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

И если тебе приходит на вход именно двумерный массив с неопределённым порядком - значит так и должно быть?

Например, в твоём примере ([["USA", "BRA"], ["JPN", "PHL"], ["BRA", "UAE"], ["UAE", "JPN"]]) можно предположить, что отправная точка - USA, которая не имеет отправителя, а конечная точка - PHL, которая не имеет принимающего?

Если так, то остальные массивы - это промежуточные точки, которые имеют и отправителя и принимающего.

Есть вообще ещё примеры с данными?

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

Например:

const routes = [     ['A', 'B'], ['O', 'P'], // [начало], [конец]     ['E', 'F'],     ['J', 'K'],     ['F', 'G'],     ['K', 'L'],     ['N', 'O'],     ['M', 'N'],     ['L', 'M'],     ['G', 'H'],     ['B', 'C'],     ['H', 'I'],     ['M', 'N'],     ['C', 'D'],     ['D', 'E'],     ['I', 'J'] ]

const routes = [ ['A', 'B'], ['O', 'P'], // [начало], [конец] ['E', 'F'], ['J', 'K'], ['F', 'G'], ['K', 'L'], ['N', 'O'], ['M', 'N'], ['L', 'M'], ['G', 'H'], ['B', 'C'], ['H', 'I'], ['M', 'N'], ['C', 'D'], ['D', 'E'], ['I', 'J'] ]

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

Если конечно это так и есть всё, по логике.

function findSequence(input) {     const adjacencyList = {}, indegree = {};      input.forEach(([from, to]) =&gt; {         adjacencyList[from] = (adjacencyList[from] || []).concat(to);         indegree[to] = (indegree[to] || 0) + 1;     });      const start = Object.keys(adjacencyList).find(country =&gt; !indegree[country]);     if (!start) {         return false;     }      const result = [], visited = {};      function dfs(node) {         visited[node] = true;         result.push(node);         adjacencyList[node]?.forEach(neighbor =&gt; !visited[neighbor] &amp;&amp; dfs(neighbor));     }      dfs(start);     return result.join(', '); } findSequence([["USA", "BRA"], ["JPN", "PHL"], ["BRA", "UAE"], ["UAE", "JPN"]])//"USA, BRA, UAE, JPN, PHL"

Ваше решение единственное правильное. Спасибо вам

Вот что у меня в конце концов получилось

function findRoutes(routes) {   const dictionary = {};   const indegree = {};    routes.forEach(([from, to]) =&gt; {     dictionary[from] = to;     indegree[to] = (indegree[to] || 0) + 1;   });    const initialRoute = Object.keys(dictionary).find((el) =&gt; {     return !Object.keys(indegree).includes(el);   });    const stack = [initialRoute];    function checkRoutesPos(dictionary, initialRoute) {     let thisRoute = initialRoute;     let pushElem = dictionary[thisRoute];     while (pushElem !== undefined) {       thisRoute = dictionary[thisRoute];       stack.push(pushElem);       pushElem = dictionary[thisRoute];     }   }   checkRoutesPos(dictionary, initialRoute);   return stack.join(", "); }

Ответы:

В общем случае - теория графов, Эйлеров путь.
Для случая, когда путь заведомо есть, он только один и проходит через каждую вершину только один раз, ищем вершину, для которой есть исходящий маршрут, но нет входящих.
В вашем примере это "USA". Есть маршрут, который с неё начинается, но нет маршрута, который в ней заканчивается.

Я пытался что то сделать с вложенными циклами, но ничего дельного не получилось, можете помочь своим решением

Всё бы ничего и мой код работал бы (чуть ниже), если бы был известен начальный маршрут от которого нужно отталкиваться.

Ну так найдите начало (если оно гарантированно есть) или кандидата (если таковых несколько или может не быть).
То есть просто ищите значение(я), которое присутствует в первом элементе пары, но отсутствует во втором по всему массиву.

Применительно к показанному массиву - только значение USA соответствует описанному условию.

А ещё - обязательно проверяйтесь на цикл. Например, исходные (А,Б),(Б,В),(В,Б) отправят вашу программу в нирвану... Как вариант, можно просто исключать уже использованные элементы из дальнейших итераций.

Сколько не пытаюсь не получается, нужна ваша помощь
DZHAMBUALT, не-а, я с JScript не работаю, а копаться в доках мне тупо лень.

const routes = [     ['USA', 'BRA'], ['JPN', 'PHL'], ['BRA', 'UAE'], ['UAE', 'JPN'] ]  const length = routes.length const start = routes.shift() const chain = [ start ]  while(chain.length !== length){     const [ _, to ] = chain[ chain.length -1 ]     routes.forEach(([ from ], index) =&gt; {         if(to === from){             chain.push(routes[index])         }     }) }  const set = new Set()  chain.forEach(([ from, to ]) =&gt; set.add(from).add(to))  const route = []  set.forEach(any =&gt; route.push(any))  const string = route.join(',')  console.log(string)

const routes = [ ['USA', 'BRA'], ['JPN', 'PHL'], ['BRA', 'UAE'], ['UAE', 'JPN'] ] const length = routes.length const start = routes.shift() const chain = [ start ] while(chain.length !== length){ const [ _, to ] = chain[ chain.length -1 ] routes.forEach(([ from ], index) => { if(to === from){ chain.push(routes[index]) } }) } const set = new Set() chain.forEach(([ from, to ]) => set.add(from).add(to)) const route = [] set.forEach(any => route.push(any)) const string = route.join(',') console.log(string)

Так?

P.S.: Пропустил, что в строку надо, поправил.
Ну и это не сработает с вариантом, когда ты отправной точкой (start) будешь объявлять массив, значение to (второе) которого не присутствует в from (первом значении) других массивов.

Если ты ниндзя

const data = [     ['A', 'B'], ['O', 'P'], // [начало], [конец (возможно)]     ['E', 'F'], ['J', 'K'],     ['F', 'G'], ['K', 'L'],     ['N', 'O'], ['M', 'N'],     ['L', 'M'], ['G', 'H'],     ['B', 'C'], ['H', 'I'],     ['M', 'N'], ['C', 'D'],     ['D', 'E'], ['I', 'J'] ]  const [ length, chain, [ start, end ], routes ] = [ data.length, [ ], [ ...data ], data.slice(2) ]  chain.push(start)  while(chain.length !== length -1){     const [ , to ] = chain[ chain.length -1 ]     routes.forEach(([ from ], index) =&gt; to === from ? chain.push(routes[ index ]) : void(0)) }  chain.push(end)  console.log(chain.map(([ from, to ], index) =&gt; index === chain.length -1 ? [ from, to ].join(',') : from).join(', '))

const data = [ ['A', 'B'], ['O', 'P'], // [начало], [конец (возможно)] ['E', 'F'], ['J', 'K'], ['F', 'G'], ['K', 'L'], ['N', 'O'], ['M', 'N'], ['L', 'M'], ['G', 'H'], ['B', 'C'], ['H', 'I'], ['M', 'N'], ['C', 'D'], ['D', 'E'], ['I', 'J'] ] const [ length, chain, [ start, end ], routes ] = [ data.length, [ ], [ ...data ], data.slice(2) ] chain.push(start) while(chain.length !== length -1){ const [ , to ] = chain[ chain.length -1 ] routes.forEach(([ from ], index) => to === from ? chain.push(routes[ index ]) : void(0)) } chain.push(end) console.log(chain.map(([ from, to ], index) => index === chain.length -1 ? [ from, to ].join(',') : from).join(', '))

Ваш код работает только если точка старта находиться в самом начале массива. Я поменял порядок элементов
в массиве routes. Всё нормально работает только тогда когда массив с начальной точкой входа на первом месте. Когда я его перемещаю на другую позицию то у меня браузер зависает ничего не выводит и бесконечно грузиться.

const routes = [ ["USA", "BRA"], ["JPN", "PHL"], ["UAE", "JPN"], ["BRA", "UAE"] ]; // Вывод: USA,BRA,UAE,JPN,PHL  const routes = [ ["UAE", "JPN"], ["USA", "BRA"], ["JPN", "PHL"], ["BRA", "UAE"] ]; // Браузер завис

const routes = [ ["USA", "BRA"], ["JPN", "PHL"], ["UAE", "JPN"], ["BRA", "UAE"] ]; // Вывод: USA,BRA,UAE,JPN,PHL const routes = [ ["UAE", "JPN"], ["USA", "BRA"], ["JPN", "PHL"], ["BRA", "UAE"] ]; // Браузер завис

Когда массив ["USA", "BRA"] не на первом месте браузер зависает и код не срабатывает

DZHAMBUALT, ну, значит я не так вопрос понял.
И ещё что я не понял - это то, зачем менять руками входные данные.

От исходной точки можно искать не только вперёд, но и назад.

Можете блеснуть своим кодом?

function findRoute(arr) {     const map = arr.reduce((acc, [from, to]) =&gt; (acc[from] = to, acc), {})       const result = []     let curr = arr[0][0]     while (curr) {         result.push(curr)         curr = map[curr]     }     return result }

function findRoute(arr) { const map = arr.reduce((acc, [from, to]) => (acc[from] = to, acc), {}) const result = [] let curr = arr[0][0] while (curr) { result.push(curr) curr = map[curr] } return result }

Ваш код работает только если точка старта находиться на [0][0]. Если я поменяю входные данные функции то результат отображается неверно. Вот примеры входных данных с выводом для вашего кода

findRoute([ ["JPN", "PHL"], ["BRA", "UAE"], ["UAE", "JPN"], ["USA", "BRA"] ]) // Вывод ['JPN', 'PHL']  findRoute([ ["BRA", "UAE"], ["JPN", "PHL"], ["UAE", "JPN"], ["USA", "BRA"] ]) // Вывод ['BRA', 'UAE', 'JPN', 'PHL']

findRoute([ ["JPN", "PHL"], ["BRA", "UAE"], ["UAE", "JPN"], ["USA", "BRA"] ]) // Вывод ['JPN', 'PHL'] findRoute([ ["BRA", "UAE"], ["JPN", "PHL"], ["UAE", "JPN"], ["USA", "BRA"] ]) // Вывод ['BRA', 'UAE', 'JPN', 'PHL']

Нужно решить такую задачу?

Опишите проблему, и специалист поможет с настройкой, исправлением ошибки или доработкой сайта. Подберём понятный план работ без лишней переписки.

Заказать помощь

Лучший ответ

Максим Павлов Ответ

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

Пример кода на PHP:

function findStartingPoint($arr) {
    $rows = count($arr);
    $cols = count($arr[0]);
 
    for ($i = 0; $i &lt; $rows; $i++) {
        for ($j = 0; $j &lt; $cols; $j++) {
            if ($arr[$i][$j] == &#039;X&#039;) { // здесь &#039;X&#039; - условие, которое определяет начальную точку
                return [$i, $j]; // возвращаем координаты начальной точки
            }
        }
    }
 
    return null; // если не найдено подходящей точки
}
 
// Пример использования функции
$array = [
    [&#039;O&#039;, &#039;O&#039;, &#039;O&#039;],
    [&#039;O&#039;, &#039;X&#039;, &#039;O&#039;],
    [&#039;O&#039;, &#039;O&#039;, &#039;O&#039;]
];
 
$startingPoint = findStartingPoint($array);
if ($startingPoint) {
    echo &quot;Найдена начальная точка в позиции ($startingPoint[0], $startingPoint[1])&quot;;
} else {
    echo &quot;Начальная точка не найдена&quot;;
}

Этот код пройдется по всем элементам двумерного массива и вернет координаты точки, которая соответствует условию (в данном случае элемент равен 'X'). Вы можете изменить условие в функции findStartingPoint() в зависимости от ваших требований.

Другие ответы (0)

Пока нет других ответов. Будьте первым, кто поможет автору.

Ответить на вопрос

комментарий Отменить ответ

Вам также может быть интересно

VPN Как правильно настроить vless для Android TV? 0 ответов Pyrogram Как правильно зарегистрировать юзер бота в Telegram? 0 ответов печатные-платы Как заставить запускаться программу M3.exe от компании Hanxing AOI в инспекционной машине на Windows 7 Pro? 0 ответов Аккумуляторные батареи Почему при зарядке автостарта слышен писк, где искать причину? 0 ответов

Как найти начальную точку для определения маршрутов в двумерном массиве?

Дополнительно:

Ответы:

комментарий Отменить ответ

Вам также может быть интересно

Ежедневно, круглосуточно