I've been learning Python at school, and I am learning JavaScript on my own time and tackling some JS projects. I can't figure out why my recursion function is only a list with the same entry.
Function description:
The function takes in a list of course Objects, with key-value pairs "courseCode": string and "possibleCombos": list[number]. I want my recursive function to output another list of Objects, with the course Object's "courseCode" value as its keys, and one element of the "possibleCombos" as its value. The returned list will have all the possible permutations of the Objects with course-combo pairs. The function also takes in an Object parameter, for recursion purposes.
Example data:
const dummyObject1 = {
'courseCode': 'BLUE',
'possibleCombos': [1, 2, 3, 4, 5]
}
const dummyObject2 = {
'courseCode': 'RED',
'possibleCombos': [11, 22, 33, 44]
}
const dummyObject3 = {
'courseCode': 'PURPLE',
'possibleCombos': [111, 222, 333, 444, 555, 666]
}
const dummyList = [dummyObject1, dummyObject2, dummyObject3]```
I ideally want:
let dummySchedules = recursionFunction(dummyList, {})
console.log(dummySchedules)
//ideal console output
[
{'BLUE': 1, 'RED': 11, 'PURPLE': 111},
{'BLUE': 1, 'RED': 11, 'PURPLE': 222},
{'BLUE': 1, 'RED': 11, 'PURPLE': 333},
... //and so on.
]
However, the list output I get, is just 120 entries of the same Object.
Here is my code:
function recursiveFunction(listOfCourses, dictSoFar) {
//base case, checks if listOfCourses is empty
if (!listOfCourses.length) {
return [dictSoFar]
} else {
//recursive step
var arraySoFar = [] //accumulator
//iterate through each element of listOfCourses[0]['possibleCombos']
for (let combo of listOfCourses[0]['possibleCombos']) {
//update dictSoFar entry.
dictSoFar[listOfCourses[0]['courseCode']] = combo
//filter out the course we just entered into dictSoFar.
let course = listOfCourses[0]
var cloneListOfCourses = listOfCourses.filter(item => item !== course)
//recursive call, this time with the filtered out list. If we keep following the
//the recursive call down, it should reach the point where listOfCourses is empty,
//triggering the base case. At that point, dictSoFar already has all course: combo
//pairs. This should traverse through all possible course: combo pairs.
var result = recursiveFunction(cloneListOfCourses, dictSoFar)
//update the accumulator
arraySoFar.push(...result)
}
return arraySoFar;
}
}
What is happening? On theory I think the logic makes sense, and I can't tell where its going wrong.
you can do something like this
if you need some explanation fell free to ask
const dummyObject1 = {
'courseCode': 'BLUE',
'possibleCombos': [1, 2, 3, 4, 5]
}
const dummyObject2 = {
'courseCode': 'RED',
'possibleCombos': [11, 22, 33, 44]
}
const dummyObject3 = {
'courseCode': 'PURPLE',
'possibleCombos': [111, 222, 333, 444, 555, 666]
}
const dummyList = [dummyObject1, dummyObject2, dummyObject3]
function recursiveFunction(listOfCourses) {
const loop = (data, acc) => {
if (!data.length) { // if listOfCourses is falsy
return acc
}
const [next, ...rest] = data
if(acc.length === 0){
return loop(rest, next)
}
return loop(rest, next.flatMap(n => acc.flatMap(a => Object.assign({}, a, n))))
}
const courseCombo = listOfCourses.map(({
courseCode,
possibleCombos
}) => possibleCombos.map(c => ({
[courseCode]: c
})))
return loop(courseCombo, [])
}
console.log(recursiveFunction(dummyList))I came out with a simpler solution that doesn't involve recursion at all
it's divided in two steps:
the first transformation map you dummy object in an array of elements with this form
[{ BLUE : 1}, { BLUE : 2},{ BLUE : 3}, { BLUE : 4}, { BLUE : 5}]
then using reduce it merges all combination of the three arrays together
const dummyObject1 = {
'courseCode': 'BLUE',
'possibleCombos': [1, 2, 3, 4, 5]
}
const dummyObject2 = {
'courseCode': 'RED',
'possibleCombos': [11, 22, 33, 44]
}
const dummyObject3 = {
'courseCode': 'PURPLE',
'possibleCombos': [111, 222, 333, 444, 555, 666]
}
const dummyList = [dummyObject1, dummyObject2, dummyObject3]
const result = dummyList
.map(({courseCode, possibleCombos}) => possibleCombos.map(c => ({[courseCode]: c})))
.reduce((res, item) => res.flatMap(r => item.flatMap(i => Object.assign({}, r, i))))
console.log(result)What you're looking for is usually called the Cartesian Product of the lists. With a little fiddling, we can turn your inputs into arrays like [{BLUE: 1}, {BLUE: 2}, /*...,*/ {BLUE: 5}], then do a cartesian product of your collection of these to get something like [[{BLUE: 1}, {RED: 11}, {PURPLE: 111}], [{BLUE: 1}, {RED: 11}, {PURPLE: 222}, /...,*/ [{BLUE: 5}, {RED: 44}, {PURPLE: 666}]]. Then we can just call Object.assign on each of these arrays to get your final result.
The code ends up fairly simple.
const cartesian = ([xs, ...xss]) =>
xs == undefined ? [[]] : xs .flatMap (x => cartesian (xss) .map (ys => [x, ...ys]))
const spreadCombos = ({courseCode, possibleCombos}) =>
possibleCombos .map (v => ({[courseCode]: v}))
const combine = (os) =>
cartesian (os .map (spreadCombos)) .map (xs => Object .assign ({}, ... xs))
const dummyObject1 = {courseCode: 'BLUE', possibleCombos: [1, 2, 3, 4, 5]}, dummyObject2 = {courseCode: 'RED', possibleCombos: [11, 22, 33, 44]}, dummyObject3 = {courseCode: 'PURPLE', possibleCombos: [111, 222, 333, 444, 555, 666]}
const dummyList = [dummyObject1, dummyObject2, dummyObject3]
console .log (combine (dummyList)).as-console-wrapper {max-height: 100% !important; top: 0}cartesian does the cartesian product of an array of arrays.
spreadCombos does that first transformation from your input into [{BLUE: 1}, {BLUE: 2}, /*...,*/ {BLUE: 5}]
And our main function combine first calls spreadCombos on each input element, calls cartesian, and then for each resulting array, calls Object.assign.
Note that we have to start our Object .assign calls with an empty object. In the intermediate format, the instances of, say, {BLUE: 1} are all references to the same object. If we simply spread our array as the only parameters to Object .assign, then we'd be modifying the same reference each time.
This also helps explain what's wrong with your function. You pass through dictSoFar as a reference to an object, and so continually update that same object. You can fix this by passing a clone of the object in your recursive call. For this purpose, we can make do with the shallow clone {...dictSoFar}, although other circumstances might require a deeper clone. So this patch should fix your approach:
- var result = recursiveFunction(cloneListOfCourses, dictSoFar)
+ var result = recursiveFunction(cloneListOfCourses, {...dictSoFar})