Forgot Password ??

PHP , ASP , ASP.NET, VB.NET, C#, Java , jQuery , Android , iOS , Windows Phone

	Registered : 109,038

HOME > PHP > PHP Forum > สอบถามวิธีการทำ topological sort หน่อยครับ (แบบที่มีการจัดเรียงโดยเอาตัวที่มัน depend มาขึ้นก่อนน่ะครับ)

[PHP] สอบถามวิธีการทำ topological sort หน่อยครับ (แบบที่มีการจัดเรียงโดยเอาตัวที่มัน depend มาขึ้นก่อนน่ะครับ)

เริ่มหัวข้อใหม่

mr.v

โพสกระทู้ ( 4,762 )
บทความ ( 8 )

ผมมีข้อมูล 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 ' &nbsp;&nbsp; '.$item['id'].' has depend.<br>';// debug
            foreach ($item['deps'] as $dependency_id) {
                echo ' &nbsp;&nbsp; searching key for depend '.$dependency_id.'<br>';// debug
                if (false !== $items_key = array_search($dependency_id, array_column($items, 'id'))) {
                    echo ' &nbsp;&nbsp; depend on '.$dependency_id.' => '.$items_key.'<br>';// debug
                    echo ' &nbsp;&nbsp; &nbsp; &nbsp; &gt;&gt; ';// debug
                    //$sorted[] = $item;
                    topologicalSort([$items_key => $items[$items_key]], $sorted);
                    echo ' &nbsp;&nbsp; after request on depend '.$dependency_id.' from '.$item['id'].'<br>';// debug
                }
            }// endforeach;
            unset($dependency_id);
            echo ' &nbsp;&nbsp; end load dependencies for '.$item['id'].'<br>';// debug
        } else {
            echo ' &nbsp;&nbsp; '.$item['id'].' doesn\'t have depend.<br>';// debug
            if (isset($item['id']) && false === $item_key = array_search($item['id'], array_column($sorted, 'id'))) {
                echo ' &nbsp;&nbsp; [['.$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 : 739

Reply : 1

No. 1

mr.v

โพสกระทู้ ( 4,762 )
บทความ ( 8 )

ได้ละ ใช้ 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 &quot;three, four, two, one, five, six, nine, eight, seven&quot;</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

ค้นหาข้อมูล

แสดงความคิดเห็น

Re : สอบถามวิธีการทำ topological sort หน่อยครับ (แบบที่มีการจัดเรียงโดยเอาตัวที่มัน depend มาขึ้นก่อนน่ะครับ)

รายละเอียด

เพื่อความเรียบร้อยของข้อความ ควรจัดรูปแบบให้พอดีกับขนาดของหน้าจอ เพื่อง่ายต่อการอ่านและสบายตา และตรวจสอบภาษาไทยให้ถูกต้อง

อัพโหลดแทรกรูปภาพ

Notice

เพื่อความปลอดภัยของเว็บบอร์ด ไม่อนุญาติให้แทรก แท็ก [img]....[/img] โดยการอัพโหลดไฟล์รูปจากที่อื่น เช่นเว็บไซต์ ฟรีอัพโหลดต่าง ๆ
อัพโหลดแทรกรูปภาพ ให้ใช้บริการอัพโหลดไฟล์ของไทยครีเอท และตัดรูปภาพให้พอดีกับสกรีน เพื่อความโหลดเร็วและไฟล์ไม่ถูกลบทิ้ง

เพื่อความปลอดภัยและการตรวจสอบ กระทู้ที่แทรกไฟล์อัพโหลดไฟล์จากที่อื่น อาจจะถูกลบทิ้ง

โดย

อีเมล์

บวกค่าให้ถูก

<= ตัวเลขฮินดูอารบิก เช่น 123 (หรือล็อกอินเข้าระบบสมาชิกเพื่อไม่ต้องกรอก)

Load balance : Server 00

Registered : 109,038

No. 1

ค้นหาข้อมูล

อัพโหลดแทรกรูปภาพ

Notice