javascript - 产生预期结果的函数中使用的方法背后的数学推理是什么？

Question

我有一个函数可以生成给定字符串的所有组合；不包括排列。我相信我完全理解给定字符串如何通过函数传递并产生所需结果的逻辑。我想要了解的是主要方法背后的数学推理，函数通过这些方法将字符串的元素处理成包含所有可能组合的数组。

这里是大量注释的代码，显示了我目前对函数逻辑处理的理解。

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); 
            }
        }

在将最后可能的组合添加到 var combi 之后，具有上述定义的变量“slent”如何为我们提供整个循环在正确时刻停止的确切条件？

此外，该部分中的第二个 FOR 循环还包含一个类似的条件，它与 j= 0 的初始表达式以及 IF 语句中包含的条件一起工作，该条件似乎可以完美地处理并将每个可能的组合插入变量“combi”，同时避免在每次迭代中添加不正确的元素。此函数中使用的 Math.pow() 方法如何产生所需的结果？

上述要点背后的原因是什么？我觉得我完全理解该功能“如何”工作，但我想知道该方法“为什么”有效。人们如何知道这些方法一起将允许函数返回所需的内容？

我觉得它与组合的数学定义有关，但我不熟悉这个特定主题，所以我想知道如果我以有意义的方式构建这个问题，是否有人可以启发我？

Answer 1

一般来说，n 个不同的字符按顺序取用，一些取用或不取用，有 2^n 种可能的字符集(包括空集，例程注意不要添加)。这些与范围从 0 到 2^n-1 的可能的 n 位基数 2 相关联。循环遍历这些数字，对于每个数字，代码检查与每个字符关联的位，如果该位为 1，则包括该字符，如果为 0，则不包括该字符。