我已經設法在兩個遞回函式中做到了這一點。但我真的很好奇，是否可以在一個函式中使用兩個遞回......
這是一個練習的任務和一個提示：
撰寫一個呼叫函式，該函式
subsets將回傳陣列的所有子集。下面的例子。
提示：對于子集（[1, 2, 3]），有兩種子集：
- 那些不包含 3 的（所有這些都是 [1, 2] 的子集）。
- 對于每個不包含 3 的子集，也有一個對應的子集是相同的，只是它也確實包含 3。
這是我使用 2 個遞回的解決方案，包括任務示例：
let arr = []
console.log(JSON.stringify(subsets(arr))); // [[]]
arr = [1]
console.log(JSON.stringify(subsets(arr))); // [[], [1]]
arr = [1,2]
console.log(JSON.stringify(subsets(arr))); // [[], [1], [2], [1, 2]]
arr = [1,2,3]
console.log(JSON.stringify(subsets(arr))); // [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
// your code here
function subsets(arr) {
if (arr.length === 0) return [[]]; // base
let el = arr.slice(-1)
let prev = subsets(arr.slice(0, -1))
return prev.concat(addEl(prev,el))
//can be instead iterative: return prev.concat(prev.map(x => x.concat([el])));
}
function addEl(arrA, el) {
let firstEl = arrA[0];
let rest = arrA.slice(1)
if (arrA.length === 1) return [firstEl.concat(el)]; // base
return [firstEl.concat(el)].concat(addEl(rest, el))
}.as-console-wrapper { min-height: 100%; top: 0; }uj5u.com熱心網友回復：
您已經非常接近注釋掉的代碼了，您只需要使用x.concat(el)而不是x.concat([el]). 或者，el = arr.at(-1)代替el = arr.slice(-1).
let arr = []
console.log(subsets(arr)); // [[]]
arr = [1]
console.log(subsets(arr)); // [[], [1]]
arr = [1,2]
console.log(subsets(arr)); // [[], [1], [2], [1, 2]]
arr = [1,2,3]
console.log(subsets(arr)); // [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
// your code here
function subsets(arr) {
if (arr.length === 0) return [[]]; // base
let el = arr.slice(-1)
let prev = subsets(arr.slice(0, -1))
return prev.concat(prev.map(x => x.concat(el)));
}uj5u.com熱心網友回復：
一個簡單的單功能遞回將當前作業狀態存盤在第二個引數中，默認[]為我們的作業狀態，我們所做的作業。當沒有剩余專案時，我們只需回傳我們的作業狀態，包裝在一個額外的陣列級別。它可能看起來像這樣：
const subsets = ([x, ...xs], ys = []) =>
x == undefined
? [ys]
: [...subsets (xs, ys), ...subsets (xs, ys .concat (x))]
console .log (subsets ([1, 2, 3]))我們可以像這樣可視化呼叫樹，[<xs>]-[<ys>]在每個節點處：
[1, 2, 3]-[]
|
,------------------- -------------------,
[2, 3]-[] [2, 3]-[1]
| |
,------- --------, ,----------- ------------,
[3]-[] [3]-[2] [3]-[1] [3]-[1, 2]
| | | |
,---- ---, ,---- ----, ,---- -----, ,------ ------,
[]-[] []-[3] []-[2] []-[2, 3] []-[1] []-[1, 3] []-[1, 2] []-[1, 2, 3]
\_____ \____ \_ \ / __/ ___/ _____/
\____ \_ \_ | | _/ ____/ ______/
\ \ \ | | / / /
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
uj5u.com熱心網友回復：
遞回生成器
要獲得子集的惰性迭代，您可以使用遞回生成器。實用tee函式用于“分支”可迭代 -
function *subsets(arr) {
if (arr.length === 0) return yield []
const last = arr.slice(-1)
const [exclude, include] = tee(subsets(arr.slice(0, -1))) // recursive
yield *exclude
for (const s of include) yield s.concat(last)
}
function *tee(g, n = 2) {
const memo = []
function* iter(i) {
while (true) {
if (i >= memo.length) {
const w = g.next()
if (w.done) return
memo.push(w.value)
}
else yield memo[i ]
}
}
while (n-- >= 0) yield iter(0)
}
console.log(JSON.stringify(Array.from(subsets([]))))
console.log(JSON.stringify(Array.from(subsets([1]))))
console.log(JSON.stringify(Array.from(subsets([1,2]))))
console.log(JSON.stringify(Array.from(subsets([1,2,3])))).as-console-wrapper { min-height: 100%; top: 0; }[[]]
[[],[1]]
[[],[1],[2],[1,2]]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
免費地圖
Array.from有可選引數，mapFn并且thisArg. 我們可能會天真地寫Array.from(...).map(mapFn)，但在一半的迭代Array.from(..., mapFn)中做同樣的事情。
想象一下，我們withStat在生成子集時提供一些關于子集的統計資訊——
function withStat(subset) {
return {
length: subset.length,
sum: subset.reduce((a,b) => a b, 0),
subset,
}
}
Array.from(subsets([1,2,3]), withStat)
[
{"length":0,"sum":0,"subset":[]},
{"length":1,"sum":1,"subset":[1]},
{"length":1,"sum":2,"subset":[2]},
{"length":2,"sum":3,"subset":[1,2]},
{"length":1,"sum":3,"subset":[3]},
{"length":2,"sum":4,"subset":[1,3]},
{"length":2,"sum":5,"subset":[2,3]},
{"length":3,"sum":6,"subset":[1,2,3]},
]
持久迭代器
上面我們使用tee多次讀取一個可迭代的值。下面我們展示iter了將生成器包裝在持久迭代器介面中，允許我們多次使用迭代器。
function *subsets(arr) {
if (arr.length === 0) return yield []
const last = arr.slice(-1)
const r = iter(subsets(arr.slice(0, -1))) // assign r
yield *r // read from r
for (const s of r) yield s.concat(last) // read from r again
}
為此，我們撰寫了一個iter抽象 -
function iter(g) {
const computed = thunk(_ => g.next())
return {
get done() {
return computed().done
},
get value() {
return computed().value
},
next: thunk(_ =>
computed() && iter(g)
),
*[Symbol.iterator]() {
let t = this
while(!t.done) yield t.value, t = t.next()
}
}
}
這取決于thunk抽象 -
function thunk(f) {
const nil = Symbol()
let computed = nil
return _ => {
if (computed === nil) computed = f()
return computed
}
}
希望您可以開始了解資料抽象如何使我們能夠撰寫更高級別的程式并控制復雜性。
function *subsets(arr) {
if (arr.length === 0) return yield []
const last = arr.slice(-1)
const r = iter(subsets(arr.slice(0, -1)))
yield *r
for (const s of r) yield s.concat(last)
}
function iter(g) {
let computed = thunk(_ => g.next())
return {
get done() {
return computed().done
},
get value() {
return computed().value
},
next: thunk(_ =>
computed() && iter(g)
),
*[Symbol.iterator]() {
let t = this
while(!t.done) yield t.value, t = t.next()
}
}
}
function thunk(f) {
const nil = Symbol()
let computed = nil
return _ => {
if (computed === nil) computed = f()
return computed
}
}
console.log(JSON.stringify(Array.from(subsets([]))))
console.log(JSON.stringify(Array.from(subsets([1]))))
console.log(JSON.stringify(Array.from(subsets([1,2]))))
console.log(JSON.stringify(Array.from(subsets([1,2,3])))).as-console-wrapper { min-height: 100%; top: 0; }[[]]
[[],[1]]
[[],[1],[2],[1,2]]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
uj5u.com熱心網友回復：
與@Scott 的答案類似的方法，不同之處在于它使用了一個rest 引數，ys并且它有條件地將 的最后一個元素添加到每個遞回級別xs的 rest 引數中，而不是有條件地附加 的第一個元素：ysxs
const subsets = (xs, ...ys) => (
xs.length === 0 ? [ys] : [
subsets(xs.slice(0, -1), ...ys),
subsets(xs.slice(0, -1), xs.at(-1), ...ys)
].flat()
);
console.log(subsets([1, 2, 3]));這是此示例的遞回樹的可視化：
([1, 2, 3])
|-------------------------------
([1, 2]) ([1, 2], 3)
|------------ |------------------
([1]) ([1], 2) ([1], 3) ([1], 2, 3)
|---- |------- |------- |----------
([]) ([], 1) ([], 2) ([], 1, 2) ([], 3) ([], 1, 3) ([], 2, 3) ([], 1, 2, 3)
| | | | | | | |
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3] [1, 2, 3]]
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/507831.html
標籤：javascript 递归
上一篇：python中的遞回排列