我正在使用 javascript 做我的作業。該問題需要找到所有包含 N 個房間和 n 個會議的房間和會議分配組合。
例如，如果我有5 rooms并且需要分配到3 meetings，結果將類似于
[1,1,3],[1,2,2],[1,3,1],[2,1,2],[2,2,1] and [3,1,1]。
我需要使用遞回來解決這個問題。但是我的遞回只給了我一個結果，而不是所有的結果。
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))如何使用遞回列出所有組合？我掙扎了很久。非常感謝你。
uj5u.com熱心網友回復：
一些問題：
您的代碼使用一個名為
i. 這是不對的，因為遞回中的回圈迭代會改變i外部回圈正在使用的內容。始終在本地范圍內宣告變數。所以for (let i.....)您的函式不應通過連接 (
所以基本情況應該回傳
[[num]]。外部陣列只有一個元素，表示只有一個可能的磁區，內部陣列指定磁區是什么：它只有一個房間。由于遞回呼叫回傳一個陣列陣列，因此您應該迭代該遞回結果，并添加當前的房間分配以形成新的組合。
迭代可能會比您預想的更早停止，因為必須有足夠的“價值”
num - i才能用至少 1 個來填充剩余的房間。
這是一個解決方案：
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));uj5u.com熱心網友回復：
似乎您已經知道如何生成序列，所以只需描述您在腦海中使用的規則。然后從那里向后作業程式。下面我們描述如何k從任何陣列生成固定大小的大小組合，t-
- 如果要選擇的數量
k, 為零，則產生空組合，() - (inductive)
k至少是一個。如果陣列t, 為空，則沒有任何選擇。停止迭代 - (inductive)
k至少為 1 且陣列具有至少一個元素。選擇 t 的第一個元素并將其添加到子問題的每個組合中(t.slice(1), k - 1)。并且不要從子問題中選擇這個元素和產量，(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(""))
??????
??????
??????
??????
??????
??????
??????
??????
??????
??????
使用陣列而不是數字作為輸入的一個好處是我們可以從任何輸入生成固定大小的組合，而不僅僅是數字組合。而且因為.slice也適用于字串，我們實際上也可以使用基于字串的輸入！
for (const c of choosek("ABCDE", 3))
console.log(c.join(""))
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/411308.html
標籤：
上一篇：用元組在python中構建一棵樹