Правильно получить порядок сортировки этого массива в переполнении стека
У меня есть 2-мерный массив, значения которого …
9999999999999999 3201 4584 4821 1628 1218 1786 4738 4897
3122 9999999999999999 1400 1638 1797 2756 3323 5310 5472
4523 1400 9999999999999999 237 3198 4156 4723 6711 6872
4760 1638 237 9999999999999999 3435 4394 4961 6948 7110
1324 1846 3247 3485 9999999999999999 958 1525 3931 4093
932 2854 4273 4510 1002 9999999999999999 567 4873 5034
1499 3422 4840 5078 1569 567 9999999999999999 5440 5602
5061 5359 6760 6998 4019 4959 5526 9999999999999999 161
5233 5531 6931 7169 4190 5130 5697 171 9999999999999999
Вот тот же массив в коде:
array:9 [
0 => array:9 [
0 => 9999999999999999
1 => 3122
2 => 4523
3 => 4760
4 => 1324
5 => 932
6 => 1499
7 => 5061
8 => 5233
]
1 => array:9 [
0 => 3201
1 => 9999999999999999
2 => 1400
3 => 1638
4 => 1846
5 => 2854
6 => 3422
7 => 5359
8 => 5531
]
2 => array:9 [
0 => 4584
1 => 1400
2 => 9999999999999999
3 => 237
4 => 3247
5 => 4273
6 => 4840
7 => 6760
8 => 6931
]
3 => array:9 [
0 => 4821
1 => 1638
2 => 237
3 => 9999999999999999
4 => 3485
5 => 4510
6 => 5078
7 => 6998
8 => 7169
]
4 => array:9 [
0 => 1628
1 => 1797
2 => 3198
3 => 3435
4 => 9999999999999999
5 => 1002
6 => 1569
7 => 4019
8 => 4190
]
5 => array:9 [
0 => 1218
1 => 2756
2 => 4156
3 => 4394
4 => 958
5 => 9999999999999999
6 => 567
7 => 4959
8 => 5130
]
6 => array:9 [
0 => 1786
1 => 3323
2 => 4723
3 => 4961
4 => 1525
5 => 567
6 => 9999999999999999
7 => 5526
8 => 5697
]
7 => array:9 [
0 => 4738
1 => 5310
2 => 6711
3 => 6948
4 => 3931
5 => 4873
6 => 5440
7 => 9999999999999999
8 => 171
]
8 => array:9 [
0 => 4897
1 => 5472
2 => 6872
3 => 7110
4 => 4093
5 => 5034
6 => 5602
7 => 161
8 => 9999999999999999
]
]
Я пытаюсь найти порядок сортировки этого массива с точки зрения ближайшего. Каждый ряд содержит расстояние от места до другого места.
Другими словами, массив выглядит примерно так:
China India USA Japan
China 0 50 4000 2000
India 50 0 4100 2100
USA 4050 4120 2 3000
Japan 2010 1950 2997 0
Как видите, значение для себя равно 0, иногда это небольшое число, например 2-10 (не совсем уверен), потому что API матрицы расстояний Google иногда возвращает большие значения для того же источника и пункта назначения, поэтому я заменил его на 9999999999999999 по всей диагонали в моем исходном массиве выше.
Цель состоит в том, чтобы получить сортировку по расстоянию. Первая запись является отправной точкой, поэтому в случае вышеупомянутого гипотетического массива это будет:
[0 1 3 2] То есть из Китая в Индию, затем из Индии в Японию и из Японии в США. Моя цель — в конце концов использовать array_multisort, чтобы упорядочить только ключи с названиями мест, чтобы они были упорядочены правильно.
Код, который я придумал, не работает, как я надеялся:
$order = [0];
$i = 0;
$nextItemToProcessIndex = 0;
foreach($tempMatrix as $key => $entry) {
$tempMatrix[$key][$key] = PHP_INT_MAX;
}
while(!empty($tempMatrix)) {
$closestItemIndex = array_search(min($tempMatrix[$nextItemToProcessIndex]), $tempMatrix[$nextItemToProcessIndex]);
array_push($order, $closestItemIndex);
$this->pull_item($tempMatrix, $nextItemToProcessIndex);
$nextItemToProcessIndex = $closestItemIndex - 1;
$i++;
}
dd($order);
...
...
public function pull_item(&$array, $offset) {
array_walk($array, function (&$v) use ($offset) {
array_splice($v, $offset, 1);
});
$row = array_splice($array, $offset, 1);
return $row;
}
Решение
Если изменение меток столбцов матрицы подходит вам — вы можете выполнить сортировку следующим образом:
$dist = [
"China" => ['China' => 0, 'India' => 50, 'USA' => 4000, 'Japan' => 2000],
"India" => ['China' => 50, 'India' => 0, 'USA' => 4100, 'Japan' => 2100],
"USA " => ['China' => 4050, 'India' => 4120, 'USA' => 2, 'Japan' => 3000],
"Japan" => ['China' => 2010, 'India' => 1950, 'USA' => 2997, 'Japan' => 0]
];
// sort columns by distance
foreach ($dist as $key => $value) {
asort($dist[$key]);
}
// display distances matrix
foreach ($dist as $row_c => $data) {
$row1 = "\t";
$row2 = $row_c . " : ";
foreach ($data as $col_c => $col_dist) {
$row1 .= $col_c . "\t";
$row2 .= $col_dist . "\t";
}
echo "{$row1}\n{$row2}\n\n";
}
Выходы:
Китай Индия Япония США Китай: 0 50 2000 4000 Индия Китай Япония США Индия: 0 50 2100 4100 США Япония Китай Индия США: 2 3000 4050 4120 Япония Индия Китай США Япония: 0 1950 2010 2997
Другие решения
Я смог найти решение для этого самостоятельно. Размещение здесь, если кто-то сталкивался с той же проблемой:
$nextItemToProcess = 0;
$order = [0];
foreach(range(0, count($tempMatrix) - 2) as $i) {
if(count(array_diff_key($tempMatrix[$nextItemToProcess], $order)) == 1) {
$order = array_merge($order, array_diff(range(0, count($tempMatrix)-1), $order));
break;
}
$diffArray = array_diff_key($tempMatrix[$nextItemToProcess], array_flip($order));
$closestItemIndex = array_search(min($diffArray), $tempMatrix[$nextItemToProcess]);
array_push($order, $closestItemIndex);
$nextItemToProcess = $closestItemIndex;
}
$ascOrigins = [];
foreach($order as $i) {
array_push($ascOrigins, $arrOrigins[$i]);
}
ascOrigins — это массив в порядке возрастания расстояния до места. Я думал, что смогу использовать php array_multisort, но это было бесполезно, так как здесь я сортирую ключи arr на основе значений порядка. (Я знаю, что array_flip мог бы добиться цели, но это прекрасно работает).