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

Question

I have kind of a tree structure outputted from another method in a format:

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

Where top node is empty array and $tracks[0] = [1,4] combines first two nodes (either 1 or 4). This is not a binary tree as seen from $tracks[2] = [2,3,5] which would mean that there are three possible nodes.

I want to find the first combination where numbers do not repeat (for example [1,3,5,2,4]), so going through the whole tree is not necessary.

I have created a function, but ran into a problem which I cannot figure out how to solve:

$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." ";
}    

It will work for availableTracks, but runs into problems when it has to go back more than one level. I came to a conclusion that i'd need to keep more than a single previousnode, but i'm certain that it should be possible to not keep it in memory, but just modify the length of array on each recursion accordinly. Unfortunately i couldn't figure out a way to do that and maybe someone can help me with that?

Answer 1

Not sure why i was downvoted without any comments, but i think i managed to solve it:

$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." ";
}

I used currentPath as a memory tool. Before moving back to previous level I took the final element in currentPath (the one which is removed when moving back to top) and checked what is it's index on level above. Then i started the iteration from that index (as previous indexes were already done).