I'm trying to code a recursive function but I'm struggling and I was hoping someone could help push me in the right direction. I believe that this would be considered "Tree Recursion".
This is a trivial example to illustrate the data and what I'm trying to do. Obviously, the real data is more complex...
Basically, I start with an array containing a single array of objects like below where prop2 in any of the objects can either be a valid string or an empty string...
[
[
{ prop1: "abc", prop2: "" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
]
]
My algorithm needs to look at the array above and iterate over the objects. As soon as it encounters an object with an empty string in prop2, it needs to clone the array three times and replace the empty string in that object (and only that object) with three different values (one/two/three) like this...
[
[
{ prop1: "abc", prop2: "one" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
],
[
{ prop1: "abc", prop2: "two" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
],
[
{ prop1: "abc", prop2: "three" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
]
]
Then the algorithm starts again, except that the the input is this new array containing three arrays.
So on the second iteration, each of the three arrays will get cloned three times and the empty string will get replaced in the same way.
The end result for this simple example would be an array of nine arrays.
If the array had more objects with empty prop2 values, there would be more iterations.
Basically, I'm taking an array of objects where some of the props are empty strings and "expanding" that particular prop value to every permutation of "one"/"two"/"three"
I know that this is an ideal problem for recursion but I'm having trouble figuring out the code.
I think that the "base case" would probably be where I have an array of objects and none of the objects have properties with empty strings. That case would return that array.
I don't know what the other case would look like other than calling the same function three times with the three newly created variants. I also don't know what this case should be returning.
I'm having trouble finding reference examples online that are similar to what I'm trying to do.
CodePudding user response：
I suggest this non-reclusive solution it serves your end-result requirements:
const myTree = [
[
{ prop1: "abc", prop2: "" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
]
];
let nodesWithEmptyStrings = myTree.filter(n=> !!n.find(l=> l.prop2===""));
while(nodesWithEmptyStrings.length > 0) {
nodesWithEmptyStrings.forEach(n => {
const firstEmptyStringLeaveIndex = n.findIndex(l=> l.prop2==="");
n[firstEmptyStringLeaveIndex].prop2 = "one";
const copy1 = JSON.parse(JSON.stringify(n));
copy1[firstEmptyStringLeaveIndex].prop2 = "two";
myTree.push(copy1);
const copy2 = JSON.parse(JSON.stringify(n));
copy2[firstEmptyStringLeaveIndex].prop2 = "three";
myTree.push(copy2);
});
nodesWithEmptyStrings = myTree.filter(n=> !!n.find(l=> l.prop2===""));
}
document.getElementById('result').innerText = JSON.stringify(myTree, null, 2);<pre id="result"></pre>CodePudding user response：
Yes, you can do this using recursion. The basic principle is to modify the array and then check if it needs to be modified some more, if that is the case, return the result of calling the function with the new array.
Here is an example:
const fillers = ['one', 'two', 'three'];
const propToCheck = 'prop2';
function recursion(arr) {
const mod = arr.reduce((a, c) => {
const found = c.find(v => !v[propToCheck]);
if (found) {
const tmp = c.filter(v => v !== found);
return [...a, ...fillers.map(filler => [...tmp, { ...found, [propToCheck]: filler }])];
}
return [...a, c];
}, []);
const notDone = mod.some(v => v.some(o => !o[propToCheck]))
if (notDone) {
return recursion(mod);
}
return mod;
}
const result = recursion([
[
{ prop1: "abc", prop2: "" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
]
]);
console.log(result);CodePudding user response：
I don't know if this is a problem that intuitively I would want to solve with recursion, but this general function that takes both substitutions and what key to check for the empty string as arguments would work (using es6 syntax and functionality with a lot of destructuring):
const substitute = (data, index, keyToCheck, substitutes) => {
const indexOfObjectWithEmptyKeyToCheck = data[index].findIndex(obj => obj[keyToCheck] === "")
if(indexOfObjectWithEmptyKeyToCheck === -1) {
if(index === data.length - 1)
return data
else
return substitute(data, index 1, keyToCheck, substitutes)
}
else {
return substitute(
[
...data.slice(0, index),
...(substitutes.map(
substitute => [
...data[index].slice(0, indexOfObjectWithEmptyKeyToCheck),
{ ...data[index][indexOfObjectWithEmptyKeyToCheck], [keyToCheck]: substitute },
...data[index].slice(indexOfObjectWithEmptyKeyToCheck 1)
]
)),
...data.slice(index 1)
],
index,
keyToCheck,
substitutes
)
}
}
const SUBSTITUTES = ["one", "two", "three"];
const result = substitute(
[
[
{ prop1: "abc", prop2: "" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
]
],
0,
"prop2",
SUBSTITUTES
)
console.log(result)
console.log("Size of result: " result.length)Basically, we iterate through the array, only incrementing the index if the current array has no object where the key to check is the empty string, otherwise we do replacements as necessary and recurse on the same index. The base case is when the key to check is not the empty string and the index is the last index of the input array.
The Typescript part I left to you as an exercise as I don't believe typing the input data is the big problem here.