javascript - 字符串双循环的组合 (JavaScript)

Question

我试图了解如何使用双循环查找字符串的所有组合，但我遇到的解决方案太复杂了，我无法理解。该函数可以满足我的需要，但我对设置单循环或双循环有初学者的了解。

我希望对正在发生的事情进行一般性的逐步解释，但对于具体问题:什么函数是“i <Math.pow(2,n)-1”，“((i & (1 << j)) == 1 << j)", and "var comb = ''; (临时存储？)"服务？

subsets = function(str) { 
      var n = str.length;
      for (var i=1; i< Math.pow(2,n)-1; i++) {
        var comb = '';
        
        for (var j=0; j<n; j++) {
          var use = ((i & (1 << j)) == 1 << j);
          if(use)comb+=str.charAt(j);
        }
        console.log(comb);
      }
    }
    
    subsets("age");

输出:a ag ae g ge e

Answer 1

要获得字符串的随机组合，我们可以设置一个 bool 数组，存储是否应显示其中一个字符，例如:

"a","g","e"
[true,false,true]
=>"ae"

所以可能的变化数是

2 /*true/false*/ ** str.length 

以旧式写法:

Math.pow(2,str.length)

所以主 for 循环遍历所有可能的组合，除了第一个(因为 i 从 1 开始)，因为那将是一个空字符串而最后一个 (-1) 将是“age”。虽然 i 是一个简单向上计数的整数，但我们也可以想象它是一个 bool 数组(按位 View ):

integer
bits
boolean array

1
001
[false,false,true]

2
010
[false,true,false]

3
011
[false,true,true]

4
100
[true,false,false]

... 
6 < 2 ** 3 -1
110
[true,true,false]

现在是内循环:

for (var j=0; j<n; j++) {
  var use = ((i & (1 << j)) == 1 << j);
  if(use)comb+=str.charAt(j);
}

只是检查我们的字母并检查 bool 标志是否为真，所以在 i = 5 时 bool 数组将是:

[true,false,true]//101

然后转换为

"ae"

按位看起来如何:

真正的(“a”):

 101 // i
&001 //1<<j where j is 0
=001
===
 001 //1<<j

一个错误的(“g”):

 101
&010 //1<<j where j is 1
=000
!==
010 //1<<j

真正的(“e”):

 101 // i
&100 //1<<j where j is 2
=100
===
 100 //1<<j

因此它检查 bool 数组 (i) 在 js 索引处是否为真，如果是则添加该字母。顺便说一句，更短:

 if(i & (1<<j))