|
 |
| |
สอบถามวิธีการทำ topological sort หน่อยครับ (แบบที่มีการจัดเรียงโดยเอาตัวที่มัน depend มาขึ้นก่อนน่ะครับ) |
| |
 |
|
|
 |
 |
|
ผมมีข้อมูล array แบบนี้
Code (PHP)
$test = [
['id' => 'one', 'deps' => ['two']],
['id' => 'two', 'deps' => ['three', 'four']],
['id' => 'three', 'deps' => []],
['id' => 'four', 'deps' => []],
['id' => 'five', 'deps' => ['four']],
['id' => 'six', 'deps' => []],
];
ผมอยากให้มันเรียงออกมาเป็น...
Code (PHP)
[
['id' => 'three', 'deps' => []],
['id' => 'four', 'deps' => []],
['id' => 'two', 'deps' => ['three', 'four']],
['id' => 'one', 'deps' => ['two']],
['id' => 'five', 'deps' => ['four']],
['id' => 'six', 'deps' => []],
];
ปัจจุบันมีโค้ดที่ลองไปแล้วหลายตัว ได้แก่
1 http://stackoverflow.com/questions/39711720/php-order-array-based-on-elements-dependency
2 http://stackoverflow.com/questions/15901159/how-can-i-rearrange-array-items-moving-dependencies-on-top
แต่ว่ายังไม่มีตัวไหนทำงานได้อย่างที่ต้องการ ที่ทำได้ใกล้เคียงที่สุดลำดับมันก็ค่อนข้างมั่วเลยครับ ไม่ให้ความสำคัญกับลำดับที่ปรากฏมาก่อนในต้นฉบับเลย
ยกตัวอย่างลิ้งค์แรกจะได้ three, four, five, six, two, one ซึ่งควรจะเป็น three, four, two, one, five, six.
ทีนี้ส่วนของกระผมที่ทำไปแล้วก็มีอยู่ แต่มันออกไม่หมด เพราะมันติดตรงส่งผ่านค่าที่เป็น sub ย่อยลงไปแล้วตัวแม่มันหาย -_-!
Code (PHP)
function topologicalSort(array $items, array &$sorted = [])
{
foreach ($items as $indexKey => $item) {
echo 'loop items: '.$item['id'].'<br>';// debug
if (isset($item['deps']) && is_array($item['deps']) && !empty($item['deps'])) {
echo ' '.$item['id'].' has depend.<br>';// debug
foreach ($item['deps'] as $dependency_id) {
echo ' searching key for depend '.$dependency_id.'<br>';// debug
if (false !== $items_key = array_search($dependency_id, array_column($items, 'id'))) {
echo ' depend on '.$dependency_id.' => '.$items_key.'<br>';// debug
echo ' >> ';// debug
//$sorted[] = $item;
topologicalSort([$items_key => $items[$items_key]], $sorted);
echo ' after request on depend '.$dependency_id.' from '.$item['id'].'<br>';// debug
}
}// endforeach;
unset($dependency_id);
echo ' end load dependencies for '.$item['id'].'<br>';// debug
} else {
echo ' '.$item['id'].' doesn\'t have depend.<br>';// debug
if (isset($item['id']) && false === $item_key = array_search($item['id'], array_column($sorted, 'id'))) {
echo ' [['.$item['id'].' was set.]]<br>';// debug
$sorted[] = $item;
}
}// endif; dependency.
}// endforeach;
unset($indexKey, $item);
}// topologicalSort
Tag : PHP
|
ประวัติการแก้ไข
2017-05-15 19:12:59
2017-05-15 19:13:31
|
 |
 |
 |
 |
| Date :
2017-05-15 19:09:46 |
By :
mr.v |
View :
706 |
Reply :
1 |
|
 |
 |
 |
 |
|
|
|
|
 |
 |
|
 |
 |
| |
|
|
|
| |
|
ได้ละ ใช้ marcj/topsort
https://github.com/marcj/topsort.php
ติดตั้งผ่าน composer https://packagist.org/packages/marcj/topsort
Code (PHP)
<?php
$test = [
['id' => 'one', 'deps' => ['two']],
['id' => 'two', 'deps' => ['three', 'four']],
['id' => 'three', 'deps' => []],
['id' => 'four', 'deps' => []],
['id' => 'five', 'deps' => ['four']],
['id' => 'six', 'deps' => []],
['id' => 'seven', 'deps' => ['eight']],
['id' => 'eight', 'deps' => ['nine']],
['id' => 'nine', 'deps' => ['one']],
];
// the sorted should be three, four, two, one, five, six, nine, eight, seven
require 'vendor/autoload.php';
var_dump($test);
echo '<hr>';
echo '<div>the result should be "three, four, two, one, five, six, nine, eight, seven"</div>'."\n";
$Sorter = new \MJS\TopSort\Implementations\FixedArraySort();
foreach ($test as $item) {
if (isset($item['id']) && isset($item['deps'])) {
$Sorter->add($item['id'], $item['deps']);
}
}// endforeach;
$result = $Sorter->sort();
var_dump($result);
unset($result, $Sorter);
|
ประวัติการแก้ไข
2017-05-16 14:03:12
| |
|
|
| |
| Date :
2017-05-16 13:42:44 |
By :
mr.v |
|
|
| |
|
|
|
|
|
| |
|
|
|
|
|
| |
|
 Load balance : Server 00
|
