javascript - 通过克隆 n-1 并将 n 添加到克隆中，递归地查找集合 Powerset 的所有子集

Question

有了集合 {a,b,c} 我想以递归方式找到所有子集。 我已经使用位掩码解决了这个问题，但我想了解一个人在这个 youtube 视频中所说的方式 here

关于这个问题还有其他 stackoverflow 线程，但我还没有找到任何可以解决她在视频中所说的方式的线程，她说，

“获取 a 和 b 的子集，克隆它们，然后将 c 添加到所有克隆中”

我无法想象实现此目的的“简单”递归方法。递归方法是否在耗尽后拥有 A、B 的所有子集和 A、B 的克隆(此时重复)，然后向上传播，仅将 C 添加到克隆？

换句话说，我从集合上的一个 for 循环开始，我调用我的递归函数，然后我做一个 n-1 的 for 循环并在那个 for 循环中调用我的递归方法，我看不出我怎么能得到C 将添加到正在使用递归构建的数组中的现有子集克隆。

    function SubsetBuilder(set) {
        this.set = set;

    }

    SubsetBuilder.prototype.getSubsetsRecursive = function () {

        //Set = {a,b,c} 
        //take the subsets of a and b, clone them and then add c to all the clones
        //subsets of {a,b}=
        //{}
        //{a}
        //{b}
        //{a,b}
        var n = this.set.length;
        var result = [];
        
        var recurseForSubsets = function (prefix, index) {
            for (var i = index; i < n -1; i ++) {
                result.push(prefix + this.set[i]);
                recurseForSubsets(prefix + this.set[i], i + 1);
            }
        }

        for (var j = 0; j < n; j++) {
            recurseForSubsets("", j);
        }

        return result;
    }

    SubsetBuilder.prototype.printSubsets = function () {
        var self = this;

        if (!self.set)
            return;

        var n = this.set.length;
        for (var i = 0; i < (1 << n) ; i++) {
            var subset = [];
            for (var j = 0; j < n; j++) {
                if (((i >> j) & 1) === 1) { // bit j is on
                    subset.push(this.set[j]);
                }
            }
            console.log(subset);
        }
    }

    var set = ['a', 'b', 'c'];
    var obj = new SubsetBuilder(set);
    //obj.printSubsets();
    console.log(obj.getSubsetsRecursive());

Answer 1

我试了一下，想出了

function getSubsets(inp) {
  if (inp.length == 1) {
      // return the single item set plus the empty set
      return [inp, []];
  } else {
      var e = inp.pop();
      var s = getSubsets(inp);
      // duplicate the elements of s into s1 without creating references.  
      // this might not be the best technique
      var s1 = s.concat(JSON.parse(JSON.stringify(s)));
      // add e to the second group of duplicates
      for (var i=s.length; i < s1.length; i++) {
          s1[i].push(e);
      }
      return s1;
  }    
}

var set = ['a', 'b', 'c'];
var list = getSubsets(set);
console.log(list);

// result
//  [["a"], [], ["a", "b"], ["b"], ["a", "c"], ["c"], ["a", "b", "c"], ["b", "c"]]

视频中的女士说 {a,b,c} 的所有子集都可以通过获取 {a,b} 的所有子集并附加c 到每一个。不完全准确({a,b,c} 的有效子集不必包含 c)，但算法的起点。我将规则更改为 {a,b,c} 的所有子集可以通过获取 {a,b} 子集的两个副本并附加 来形成c 到第二个副本的每个元素。

我认为我可以去掉或简化 if，因为基本上第二个代码块与第一个代码块的作用相同，所以它并不理想。

对我来说，算法在 O(2^n) 中运行是有意义的，因为结果以相同的方式变化(输入数组中的 3 个元素 = 输出数组中的 2^3 个元素) - 你可能不得不原谅我使用 JSON 来假设这种复杂性。我会找到一种更好的方法来深度克隆阵列，即便如此，这可能会增加更多的复杂性。