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?
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).