代码之家 › 专栏 › 技术社区 › Banana

找到第一个合适的元素数组

recursion php

0

Banana · 技术社区 · 7 年前

我有一种从另一个方法输出的树结构,格式为:

$tracks = [[1,4],[3,5],[2,3,5],[1,2],[2,4]];

其中top节点为空数组,并且 $tracks[0] = [1,4] 组合前两个节点(或 1 或 4 )这不是从中看到的二叉树 $tracks[2] = [2,3,5] 这意味着有三个可能的节点。

我想找到第一个数字不重复的组合(例如 [1,3,5,2,4] ,所以不需要穿过整棵树。

我创建了一个函数,但遇到了一个我无法解决的问题:

$availableTracks = [[1,4],[3,5],[2,3,5],[1,2],[2,4]];
$availableTracks2 = [[1,4],[3,5],[2,3,5],[1],[2,4]];


/*
    $pairedTracks = all tracks given
    $currentPath = generated path
    $level = which level in tree
    $nodeElement = element position
    $previousnode = which node it started from in current level
*/

function findBestPath($pairedtracks,$currentPath,$level,$nodeElement,$previousNode){
    if (in_array($pairedtracks[$level][$nodeElement],$currentPath)){
        echo "[IN ARRAY]: Node element in current: ".$pairedtracks[$level][$nodeElement]." on level: ".$level;
        echo "<br>";
        echo "Node which level lowered from: ".$previousNode;
        echo "<br>";
        //Check if node element is in array
        $maxLength = count($pairedtracks[$level]);
        if ($nodeElement+1 == $maxLength){
            //Current was final, return back up
            $level -= 1;
            // Go forward from previous
            $previousNode += 1;
            // Set new start node in recursive function
            $nodeElement = $previousNode;
            if ($nodeElement == count($pairedtracks[$level])){
                //Check if node element is on the same length, then go back even more.
                /*
                    At this point i realized that i'm going to need to keep track of too many previous iterations
                */

            }
            echo "Moving back up to level: ".$level.", starting iteration from: ".$nodeElement;
            echo "<br>";
            // Remove previously added element from that level!
            array_splice($currentPath, $currentPath[count($currentPath)-1], 1);
            return findBestPath($pairedtracks,$currentPath,$level,$nodeElement,$previousNode);
        }
        else {
            //More elements to follow
            $nodeElement += 1;
            return findBestPath($pairedtracks,$currentPath,$level,$nodeElement,$previousNode);
        }

    }
    else {
        //Was not in array, element can be added to current path
        echo "Adding element to current path: ".$pairedtracks[$level][$nodeElement];
        echo "<br>";
        $currentPath[] = $pairedtracks[$level][$nodeElement];
        //Check if path has finalized or check more
        if (count($currentPath) == count($pairedtracks)){
            //Search finished
            return $currentPath;
        }
        else {
            //Move downwards
            $level += 1;
            return findBestPath($pairedtracks,$currentPath,$level,0,$nodeElement);
        }
    }


}

$path = findBestPath($availableTracks2,[],0,0,0);
foreach ($path as &$value) {
    echo $value." ";
}

它会起作用的 availableTracks 但当它必须返回多个级别时会遇到问题。我得出一个结论,我需要保留不止一个 previousnode ,但我敢肯定,不应该将它保存在内存中,而应该相应地修改每个递归上数组的长度。不幸的是,我找不到一个方法来做,也许有人能帮我?

1 回复 | 直到 7 年前

1

0

Banana 7 年前

不知道为什么我没有任何评论就被否决了,但我想我设法解决了:

$availableTracks = [[1,4],[3,5],[2,3,5],[1,2],[2,4]];
$availableTracks2 = [[1,4],[3,5],[2,3,5],[1],[2,4]];


function findBestPath($pairedtracks,$currentPath,$level,$nodeElement,$previousNode){
    $maxLength = count($pairedtracks[$level]);
    if ($nodeElement == $maxLength){
        echo "[Back up more]<br>";
        echo "Current pair: [";
        foreach ($pairedtracks[$level] as &$pairElement){
            echo $pairElement.",";
        }
        echo "]<br>";
        echo "Current path: [";
        foreach ($currentPath as &$pathElement){
            echo $pathElement.",";
        }
        echo "]<br>";
        //Current was final, return back up
        $level -= 1;
        $lastInserted = $currentPath[count($currentPath)-1];
        //Take index from previous level
        $indexNumber = 0;
        foreach ($pairedtracks[$level] as &$pairElement){
            echo "Pair: ".$pairElement."<br>";
            if ($pairElement == $lastInserted){
                break;
            }
            $indexNumber += 1;
        }
        echo "Previous element was on index ".$indexNumber."<br>";
        $nodeElement = $indexNumber+1;
        echo "Moving back up to level: ".$level.", starting iteration from: ".$nodeElement.", removed element: ".$currentPath[count($currentPath)-1];
        echo "<br>";
        // Remove previously added element from that level!
        array_splice($currentPath, count($currentPath)-1, 1);
        return findBestPath($pairedtracks,$currentPath,$level,$nodeElement,$previousNode);  
    }
    else if (in_array($pairedtracks[$level][$nodeElement],$currentPath)){
        echo "[IN ARRAY]: Node element in current: ".$pairedtracks[$level][$nodeElement]." on level: ".$level;
        echo "<br>";
        //Check if node element is in array

        if ($nodeElement+1 >= $maxLength){
            //Current was final, return back up
            $level -= 1;
            $lastInserted = $currentPath[count($currentPath)-1];
            //Take index from previous level
            $indexNumber = 0;
            foreach ($pairedtracks[$level] as &$pairElement){
                if ($pairElement == $lastInserted){
                    break;
                }
                $indexNumber += 1;
            }
            echo "Previous element was on index ".$indexNumber."<br>";
            $nodeElement = $indexNumber+1;
            echo "Moving back up to level: ".$level.", starting iteration from: ".$nodeElement.", removed element: ".$currentPath[count($currentPath)-1];
            echo "<br>";
            // Remove previously added element from that level!
            array_splice($currentPath, count($currentPath)-1, 1);
            return findBestPath($pairedtracks,$currentPath,$level,$nodeElement,$previousNode);
        }
        else {
            //More elements to follow
            $nodeElement += 1;
            return findBestPath($pairedtracks,$currentPath,$level,$nodeElement,$previousNode);
        }

    }
    else {
        //Was not in array, element can be added to current path
        echo "Adding element to current path: ".$pairedtracks[$level][$nodeElement];
        echo "<br>";
        $currentPath[] = $pairedtracks[$level][$nodeElement];
        //Check if path has finalized or check more
        if (count($currentPath) == count($pairedtracks)){
            //Search finished
            return $currentPath;
        }
        else {
            //Move downwards
            $level += 1;
            return findBestPath($pairedtracks,$currentPath,$level,0,$nodeElement);
        }
    }


}

$path = findBestPath($availableTracks,[],0,0,0);
foreach ($path as &$value) {
    echo $value." ";
}

我用过 currentPath 作为记忆工具。在回到上一级之前,我把最后一个元素 当前路径 (移回顶部时移除的那个)并检查上面的索引是什么。然后我从那个索引开始迭代(因为以前的索引已经完成了)。