I'm using javascript doing my homework. The question is required to find all the combination of room and meeting allocation with N rooms and n meetings.
For example, if I have 5 rooms and need to allocate to 3 meetings, the outcome will be something like
[1,1,3],[1,2,2],[1,3,1],[2,1,2],[2,2,1] and [3,1,1].
I need to use recursion to solve this question. But my recursion only gives me one outcome rather then all the outcomes.
function partition(num, m) {
if (m == 1) {
return num
} else {
for (i = 1; i < num; i++) {
return i + "," + partition(num - i, m - 1)
}
}
}
console.log(partition(5, 3))How to list all the combinations with recursion? I'm struggling for a long time. Thank you very much.
Some issues:
Your code uses one global variable called i. This is not right, as the loop iteration in recursion will change the i that outer loops are using. Always declare your variables in a local scope. So for (let i.....)
Your function should not build a string through concatenation (+) and return a string, nor should it return a number in the base case, but it should return an array of arrays, just like you have depicted in the example output.
So the base case should return [[num]]. The outer array has just one element, which represents that there is just one partitioning possible, and the inner array specifies what that partitioning is: it just has one room.
Since the recursive call returns an array of arrays, you should iterate that recursive result, and add the current room assignment to form new combinations.
The iteration can stop a bit earlier than you have foreseen, since there must be enough "value" in num - i to fill up the remaining rooms with at least 1.
Here is a solution:
function partition(num, m) {
if (m == 1) {
return [[num]]; // return an array or arrays
} else {
let collect = []; // Prepare array for collecting the partitions
// Quit loop when not enough value to distribute in remaining rooms
for (let i = 1; i <= num - m + 1; i++) {
// Iterate the arrays that come back from recursion...
for (let arr of partition(num - i, m - 1)) {
collect.push([i, ...arr]); // ... and extend them.
}
}
return collect;
}
}
console.log(partition(5, 3));It seems like you already know how to generate the sequences, so just describe the rules you used in your head. Then work the program backwards from there. Below we describe how to generate fixed-size combinations of size k from any array, t -
k, is zero, yield the empty combination, ()k is at least one. If the array t, is empty, there is nothing left to choose. Stop iterationk is at least one and the array has at least one element. Choose the first element of t and add it to each combination of the sub-problem, (t.slice(1), k - 1). And do not choose this element and yield from the sub-problem, (t.slice(1), k).function* choosek(t, k) {
if (k == 0)
return (yield []) // 1
else if (t.length == 0)
return // 2
else {
// choose first element // 3
for (const c of choosek(t.slice(1), k - 1))
yield [t[0], ...c]
// skip first element
yield* choosek(t.slice(1), k)
}
}
for (const c of choosek(["๐ด","๐ข","๐ต","๐ก","โซ๏ธ"], 3))
console.log(c.join(""))
๐ด๐ข๐ต
๐ด๐ข๐ก
๐ด๐ขโซ๏ธ
๐ด๐ต๐ก
๐ด๐ตโซ๏ธ
๐ด๐กโซ๏ธ
๐ข๐ต๐ก
๐ข๐ตโซ๏ธ
๐ข๐กโซ๏ธ
๐ต๐กโซ๏ธ
A benefit of using an array as input instead of a number is we can generate fixed-sized combinations from any input, not just numerical ones. And because .slice also works on Strings, we can actually use string-based inputs too!
for (const c of choosek("ABCDE", 3))
console.log(c.join(""))
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE