javascript - 在这个函数中使用的方法背后产生预期结果的数学推理是什么？
问题描述
我有一个函数可以生成给定字符串的所有组合；不包括排列。我相信我完全理解给定字符串如何通过函数传递产生预期结果的逻辑。我希望了解的是函数将字符串元素处理成包含所有可能组合的数组的主要方法背后的数学推理。
这是注释很多的代码，它显示了我当前对函数逻辑处理的理解。
function generateAllCombinationsOfString (str1) { //let str1 = "dog"
// convert str1 into an array
var array1 = []; // create var in order to capture elements of str1 into an array
for (var x = 0, y = 1; x < str1.length; x++,y++) {
array1[x] = str1.substring(x, y); // we will add each character to array1, in order, starting with the first then ending the loop once the last character has been included in array1
// for each iteration: x = 0, y = 1 x < str1.length x++, y++ array1[x] = str1.substring(x, y)
// iteration 1: x = 0, y = 1 yes 1 2 array1[0] = str1.substring(0, 1) = "d"
// iteration 2: x = 1, y = 2 yes 2 3 array1[1] = str1.substring(1, 2) = "o"
// iteration 3: x = 2, y = 3 yes 3 4 array1[2] = str1.substring(2, 3) = "g"
// iteration 4: x = 3, y = 4 no
// end of loop
}
// create array containing all combinations of str1
var combi = []; // create var to capture each possible combination within an array
var temp = ""; // create cache to temporarily hold elements each possible combination before adding to an array
var slent = Math.pow(2, array1.length);
for (var i = 0; i < slent; i++){
temp = "";
// for each iteration: i = 0 i < slent i++ var combi = []; temp = ""; var slent = Math.pow(2, array1.length)
// iteration 1: i = 0 yes 1 var combi = []; temp = ""; var slent = Math.pow(2, 3) = 8
// iteration 2: i = 1 yes 2 var combi = [d]; temp = ""; var slent = Math.pow(2, 3) = 8
// iteration 3: i = 2 yes 3 var combi = [d, o]; temp = ""; var slent = Math.pow(2, 3) = 8
// iteration 4: i = 3 yes 4 var combi = [d, o, do]; temp = ""; var slent = Math.pow(2, 3) = 8
// iteration 5: i = 4 yes 5 var combi = [d, o, do, g]; temp = ""; var slent = Math.pow(2, 3) = 8
// iteration 6: i = 5 yes 6 var combi = [d, o, do, g, dg]; temp = ""; var slent = Math.pow(2, 3) = 8
// iteration 7: i = 6 yes 7 var combi = [d, o, do, g, dg, og]; temp = ""; var slent = Math.pow(2, 3) = 8
// iteration 8: i = 7 yes 8 var combi = [d, o, do, g, dg, og, dog]; temp = ""; var slent = Math.pow(2, 3) = 8
// iteration 9: i = 8 no
// end of loop
for (var j = 0; j < array1.length; j++) {
if ((i & Math.pow(2, j))) {
temp += array1[j];
// for each iteration: j = 0 j < array1.length j++ if((i & Math.pow(2, j)))? {temp += array1[j]}
// iteration 1-1: j = 0 yes 1 if((0 & Math.pow(2, 0)))? => if((0 & 1))? // false
// iteration 1-2: j = 1 yes 2 if((0 & Math.pow(2, 1)))? => if((0 & 2))? // false
// iteration 1-3: j = 2 yes 3 if((0 & Math.pow(2, 2)))? => if((0 & 4))? // false
// iteration 1-4: j = 3 no
// end of loop
// iteration 2-1: j = 0 yes 1 if((1 & Math.pow(2, 0)))? => if((1 & 1))? // true // {temp += array1[0]} => temp = "d"}
// iteration 2-2: j = 1 yes 2 if((1 & Math.pow(2, 1)))? => if((1 & 2))? // false
// iteration 2-3: j = 2 yes 3 if((1 & Math.pow(2, 2)))? => if((1 & 4))? // false
// iteration 2-4: j = 3 no
// end of loop
// iteration 3-1: j = 0 yes 1 if((2 & Math.pow(2, 0)))? => if((2 & 1))? // false
// iteration 3-2: j = 1 yes 2 if((2 & Math.pow(2, 1)))? => if((2 & 2))? // true // {temp += array1[1] => temp = "o"}
// iteration 3-3: j = 2 yes 3 if((2 & Math.pow(2, 2)))? => if((2 & 4))? // false
// iteration 3-4: j = 3 no
// end of loop
// iteration 4-1: j = 0 yes 1 if((3 & Math.pow(2, 0)))? => if((3 & 1))? // true // {temp += array1[0] => temp = "d"}
// iteration 4-2: j = 1 yes 2 if((3 & Math.pow(2, 1)))? => if((3 & 2))? // true // {temp += array1[1] => temp = "do"}
// iteration 4-3: j = 2 yes 3 if((3 & Math.pow(2, 2)))? => if((3 & 4))? // false //
// iteration 4-4: j = 3 no
// end of loop
// iteration 5-1: j = 0 yes 1 if((4 & Math.pow(2, 0)))? => if((4 & 1))? // false //
// iteration 5-2: j = 1 yes 2 if((4 & Math.pow(2, 1)))? => if((4 & 2))? // false //
// iteration 5-3: j = 2 yes 3 if((4 & Math.pow(2, 2)))? => if((4 & 4))? // true // {temp += array1[2] => temp = "g"}
// iteration 5-4: j = 3 no
// end of loop
// iteration 6-1: j = 0 yes 1 if((5 & Math.pow(2, 0)))? => if((5 & 1))? // true // {temp += array1[0] => temp = "d"}
// iteration 6-2: j = 1 yes 2 if((5 & Math.pow(2, 1)))? => if((5 & 2))? // false //
// iteration 6-3: j = 2 yes 3 if((5 & Math.pow(2, 2)))? => if((5 & 4))? // true // {temp += array1[2] => temp = "dg"}
// iteration 6-4: j = 3 no
// end of loop
// iteration 7-1: j = 0 yes 1 if((6 & Math.pow(2, 0)))? => if((6 & 1))? // false //
// iteration 7-2: j = 1 yes 2 if((6 & Math.pow(2, 1)))? => if((6 & 2))? // true // {temp += array1[1] => temp = "o"}
// iteration 7-3: j = 2 yes 3 if((6 & Math.pow(2, 2)))? => if((6 & 4))? // true // {temp += array1[2] => temp = "og"}
// iteration 7-4: j = 3 no
// end of loop
// iteration 8-1: j = 0 yes 1 if((7 & Math.pow(2, 0)))? => if((7 & 1))? // true // temp += array1[0] => temp = "d"}
// iteration 8-2: j = 1 yes 2 if((7 & Math.pow(2, 1)))? => if((7 & 2))? // true // temp += array1[1] => temp = "do"}
// iteration 8-3: j = 2 yes 3 if((7 & Math.pow(2, 2)))? => if((7 & 4))? // true // temp += array1[2] => temp = "dog"}
// iteration 8-4: j = 3 no
// end of loop
}
}
if (temp !== "") { // if var temp is not an empty string then we add elements of var temp to end of the array var combi at the end of each loop cycle
combi.push(temp);
// for each iteration if(temp !== "")?
// iteration 1: if(temp !== "")? // false //
// iteration 2: if(temp !== "")? // true // combi.push(temp) => combi.push("d")
// iteration 3: if(temp !== "")? // true // combi.push(temp) => combi.push("o")
// iteration 4: if(temp !== "")? // true // combi.push(temp) => combi.push("do")
// iteration 5: if(temp !== "")? // true // combi.push(temp) => combi.push("g")
// iteration 6: if(temp !== "")? // true // combi.push(temp) => combi.push("dg")
// iteration 7: if(temp !== "")? // true // combi.push(temp) => combi.push("og")
// iteration 8: if(temp !== "")? // true // combi.push(temp) => combi.push("dog")
}
}
// join array of combinations while seperating each by a new line
console.log(combi.join("\n"))
/* expected output if str1 = "dog"
d
o
do
g
dg
og
dog
*/
}
以下部分包含我想进一步了解背后原因的部分。
var combi = [];
var temp = "";
var slent = Math.pow(2, array1.length);
for (var i = 0; i < slent; i++){
temp = "";
for (var j = 0; j < array1.length; j++) {
if ((i & Math.pow(2, j))) {
temp += array1[j];
}
}
if (temp !== "") {
combi.push(temp);
}
}
具有上述定义的变量“slent”如何为我们提供了在将最后可能的组合添加到 var combi 之后整个循环在正确时刻停止的确切条件？
此外，该部分中的第二个 FOR 循环还包含一个类似的条件，该条件与 j= 0 的初始表达式以及 IF 语句中包含的条件一起工作，该条件似乎可以完美地处理每个可能的组合并将其推送到变量“combi " 同时避免在每次迭代中添加不正确的元素。这个函数中使用的 Math.pow() 方法是如何产生预期结果的？
上述关键点背后的原因是什么？我觉得我完全理解该功能的“如何”工作，但我想知道“为什么”该方法有效。怎么知道这些方法一起将允许函数返回所需的内容？
我觉得它与组合的数学定义有关，但我不熟悉这个特定主题，所以我想知道如果我以一种有意义的方式构造了这个问题，是否有人可以启发我？
解决方案
一般来说，按顺序取n个不同的字符，有的取不取，有2^n个字符集的可能性（包括空集，例程小心不要添加）。这些与可能的 n 位基数为 2 的数字相关联，范围从 0 到 2^n-1。循环遍历这些数字，对于每个数字，代码检查与每个字符关联的位，如果该位为 1，则包含该字符，如果为 0，则不包含该字符。
推荐阅读
- android-studio - 检测长按 RecyclerView 适配器的项目
- c++ - std::scoped_lock - 互斥体向量？
- c# - 只允许 {'delete' , 'backspace' , 一个 '.' , '-' , numbers '0 to 9'} 在文本框 C#/winforms
- python - 如何在python中的for循环中使用线程
- javascript - 如何将数组字符串转换为数组？
- machine-learning - 你能在Detectron2中同时运行人体姿态估计和物体检测吗
- android - 为什么在我的 android 项目中生成 3 个构建文件夹？
- python - 如何在列表中添加倍数？
- ruby-on-rails - 在 netlify 上托管
- reactjs - 如何将组件传递给助手？