問題： 給定一個字串's'，使用遞回生成字串的所有子序列。輸出應該以某種方式（應該首先列印“a”的所有子序列，然后是“b”的子序列，依此類推）。
給定字串 's' = abcd 的示例輸出
a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d
我一開始沒能解決這個問題，但我得到了一些幫助，然后就解決了。下面是它的代碼，但我無法得到的是為什么我們在遞回呼叫中傳遞i 1而為什么不傳遞index 1？我試過這樣做，顯然它給出了錯誤的輸出。我認為這與將i 1傳遞給它是一樣的，因為無論哪種方式我們都在增加索引，對吧？
function allSubseq(new_str, str, index) {
if (new_str.length !== 0) {
console.log(new_str.join(""));
}
if (index === str.length) {
return;
}
for (let i = index; i < str.length; i ) {
new_str.push(str[i]);
allSubseq(new_str, str, i 1);
new_str.pop(); // Backtracking step
}
}
let str = "abcd";
new_str = [];
allSubseq(new_str, str, 0);uj5u.com熱心網友回復：
這是否按您的預期作業？我剛刪了i。
let str = "abcd";
let new_str = [];
function allSubseq(new_str, str, index) {
if (new_str.length !== 0) {
console.log(new_str.join(""));
}
if (index === str.length) {
return;
}
for (; index < str.length; index ) { // notice now we use index instead of i
new_str.push(str[index]);
allSubseq(new_str, str, index 1);
new_str.pop(); // Backtracking step
}
}
你可能不應該在變數名中使用下劃線，除非它是一個常量，并且在這種情況下它是大寫的。
如果您保留i并僅替換allSubseq(new_str, str, i 1);為，allSubseq(new_str, str, index 1);那么您仍然只增加 i 而不是您傳遞給 allSubseq 的下一次呼叫的索引。
// we begin with the first call
function allSubseq(new_str, str, index) {
if (new_str.length !== 0) {
console.log(new_str.join(""));
}
if (index === str.length) {
return;
}
// we begin first loop, here index is 0, i is 0.
for (let i = index; i < str.length; i ) {
new_str.push(str[i]);
// we call this function second time
allSubseq(new_str, str, i 1);
new_str.pop();
}
}
// we call this function second time
// inside this scope index is 1
function allSubseq(new_str, str, index) {
if (new_str.length !== 0) {
console.log(new_str.join(""));
}
if (index === str.length) {
return;
}
// we begin second loop, here index is 1, i is 1.
for (let i = index; i < str.length; i ) {
new_str.push(str[i]);
/* now lets pretend that this loop finished it's work with i and index as 1,
let's also pretend that function exited without further recursion calls. */
allSubseq(new_str, str, i 1);
new_str.pop();
}
}
// we come back to our first function call to the for loop
function allSubseq(new_str, str, index) {
if (new_str.length !== 0) {
console.log(new_str.join(""));
}
if (index === str.length) {
return;
}
for (let i = index; i < str.length; i ) {
new_str.push(str[i]);
allSubseq(new_str, str, i 1); /* <- we finished this step,
inside that function call i and index were 1.
we now come back to this for loop that we began,
here index and i are still 0. */
new_str.pop();
}
/* we will now update i to be i 1 (because of i inside loop)
and begin next step of loop where i will be a bigger number than it used to be on last step,
however if we use index instead of i at `allSubseq(new_str, str, i 1);`,
then we didn't update it (index) inside this loop and it will be the same number, on each step of the loop,
it will only change inside recursion because we pass index 1. */
}
uj5u.com熱心網友回復：
至少有兩種很好的方法可以分析這個問題。首先是啟動除錯器。1 這通常是最好的方法。但您也可以添加日志記錄以跟蹤正在發生的事情。以下是使用較短輸入添加日志記錄2"abc"的結果，首先是
i 1
allSubseq ([], "abc", 0)
allSubseq ([a], "abc", 1)
> console .log ("a")
allSubseq ([a,b], "abc", 2)
> console .log ("ab")
allSubseq ([a,b,c], "abc", 3)
> console .log ("abc")
allSubseq ([a,c], "abc", 3)
> console .log ("ac")
allSubseq ([b], "abc", 2)
> console .log ("b")
allSubseq ([b,c], "abc", 3)
> console .log ("bc")
allSubseq ([c], "abc", 3)
> console .log ("c")
然后對于
index 1
allSubseq ([], "abc", 0)
allSubseq ([a], "abc", 1)
> console .log ("a")
allSubseq ([a,b], "abc", 2)
> console .log ("ab")
allSubseq ([a,b,c], "abc", 3)
> console .log ("abc")
allSubseq ([a,c], "abc", 2)
> console .log ("ac")
allSubseq ([a,c,c], "abc", 3)
> console .log ("acc")
allSubseq ([b], "abc", 1)
> console .log ("b")
allSubseq ([b,b], "abc", 2)
> console .log ("bb")
allSubseq ([b,b,c], "abc", 3)
> console .log ("bbc")
allSubseq ([b,c], "abc", 2)
> console .log ("bc")
allSubseq ([b,c,c], "abc", 3)
> console .log ("bcc")
allSubseq ([c], "abc", 1)
> console .log ("c")
allSubseq ([c,b], "abc", 2)
> console .log ("cb")
allSubseq ([c,b,c], "abc", 3)
> console .log ("cbc")
allSubseq ([c,c], "abc", 2)
> console .log ("cc")
allSubseq ([c,c,c], "abc", 3)
> console .log ("ccc")
這些應該有助于弄清楚發生了什么，以及為什么你不想繼續通過 fixed index 1。
但我還想指出一個更簡單的實作：
const call = (fn, ...args) =>
(fn (...args))
const subseqs = ([c, ...cs]) =>
c == undefined
? ['']
: call ((ss = subseqs (cs)) => ss .flatMap (s => c s) .concat (ss))
const allSubseq = (s) =>
subseqs (s) .filter (Boolean) // remove empty string
console .log (allSubseq ('abcd')).as-console-wrapper {max-height: 100% !important; top: 0}這里主要的遞回函式是subseqs. 我們將其包裝起來allSubseq以洗掉在 中生成的空字串subseqs。如果你想保留那個空字串，那么它仍然更簡單。
我們將call其用作一種ss在僅包含運算式而不包含陳述句的函式體中定義、計算、然后使用和重用變數的方法。如果這令人困惑，我們可以跳過呼叫并使用陳述句和區域變數來實作相同的目的，如下所示：
const subseqs = ([c, ...cs]) => {
if (c == undefined) return ['']
const ss = subseqs (cs)
return ss .flatMap (s => c s) .concat (ss)
}
無論哪種情況，我們的基本情況是輸入字串為空，并且我們回傳一個僅包含空字串的陣列。如果不是，我們計算字串尾部的子序列（除第一個字符之外的所有字符），并首先回傳以第一個字符為前綴的新子序列，然后直接回傳這些子序列。
請注意，此函式不會將您的結果列印到控制臺，只是回傳它們。這顯然更加靈活。如果要單獨列印它們，可以執行類似console .log (allSubseq ('abcd') .join ('\n'))或的操作allSubseq ('abcd') .forEach (console .log)。
1請參閱如何除錯小程式和什么是除錯器以及它如何幫助我診斷問題？
2i 1您可以查看調整后的源代碼index 1
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/520458.html
上一篇：如何實作可變數量的for回圈？