文章/答案/技术大牛

发布

社区首页 >问答首页 >在JS中生成powerset

问在JS中生成powerset
EN

Code Review用户

提问于 2016-08-19 00:30:19

回答 1查看 3.1K关注 0票数 4

我遇到了一个模拟面试问题，在这个问题中，候选人被要求生成给定集合的powerset。

输入集表示为唯一的整数数组。

在这个例子中没有提供任何解决方案，所以我试着自己想出些什么。我确实努力地找到了解决方案，我并不是特别不满意，但我也不是特别满意。

我采用了递归的方法。本质上，我首先生成了一棵树，深度优先，最上层由原始集合组成，每个连续的较低级别由父节点的直接子集组成。

这是我的密码。我正在使用ES5。

    var result = generate_powerset([1, 2, 3, 4]);
    console.log(result);

    function generate_powerset(set) {
      var powerset = generate_subsets(set);
      powerset.push(set);
      return powerset;
    }

    function generate_subsets(set) {
      var subsets = [];
      set.forEach(function(element, i) {
        var immediate_subset = remove_index(set, i);
        maybe_push(subsets, immediate_subset);
        var extended_subsets = generate_subsets(immediate_subset);
        extended_subsets.forEach(function(extended_subset) {
          maybe_push(subsets, extended_subset);
        });
      });
      return subsets;
    }

    function remove_index(array, i) {
      return array.filter(function(el, j) {
        return i != j;
      });
    }

    function maybe_push(set, non_member) {
      var already_member = false;
      set.forEach(function(member) {
        if (are_identical(member, non_member)) already_member = true;
      })
      if (!already_member) set.push(non_member);
    }

    function are_identical(set1, set2) {
      return (JSON.stringify(set1.sort()) == JSON.stringify(set2.sort()));
    }

我在寻找方法：

使此算法更有效
让这段代码更容易理解
让我的代码更短

我也只是一般地好奇这种方法是正统的还是非正统的。

javascript

performance

algorithm

set

回答 1

Code Review用户

发布于 2016-08-20 21:51:55

我建议这个解决办法：

console.log(powerset([1, 2, 3, 4]));

function powerset(set, result) {
  if (!result) {
    var begin = true;
    result = [];
  }
  if (set.length) {
    result = set.reduce(function(result, current, index, array) {
      var subset = array.slice(0);
      result.push(JSON.stringify(subset.splice(index, 1)));
      powerset(subset, result);
      return result;
    }, result);
  }
  result.push(JSON.stringify(set));
  if (begin) {
    result = result
      .reduce(function(result, current) {
        if (result.indexOf(current) == -1) {
          result.push(current);
        }
        return result;
      }, [])
      .map(function(current) {
        return JSON.parse(current);
      });
  }
  return result;
}

关于你的三点：

使此算法更有效

实际上，在我建议的代码中使用的代码并不完全不同：

和您的一样，它连续地处理给定集合的每个成员，递归地子处理所有其他成员的集合。
和您的一样，它在每个结果成员上使用JSON.stringify以避免重复。

让这段代码更容易理解

以下是主要的区别：

有一个独特的函数，整个主进程部分非常紧凑:从当前集合的if (set.length) { result = set.reduce(function(result, current, index, array) { var subset = array.slice(0); result.push(JSON.stringify(subset.splice(index, 1))); powerset(subset, result); return result; }, result); } result.push(JSON.stringify(set)); ，它将其每个成员推入结果，递归地子处理所有其他成员的子集，并最终推送整个集合本身。
此外，它还推动JSON.stringified成员而不是原始成员:这样，在最终结果中将成员返回到它们的真实值之前，很容易在结束时丢弃重复的成员。

让我的代码更短

它的结果是一个更简洁的代码。值得注意的是，具有讽刺意味的是，最终的清洁过程比主过程使用更多的行！我希望这可能会得到改进，以一个更隐蔽的代码结束。

票数 3

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/139095

复制

相似问题

问在JS中生成powerset
EN

回答 1

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在JS中生成powersetEN

回答 1

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在JS中生成powerset
EN