首页 > web前端 > js教程 > JavaScript求非空子集数目的实现方法

JavaScript求非空子集数目的实现方法

黄舟
发布: 2017-03-18 14:57:38
原创
2360 人浏览过

给定一个序列的元素,里面由数字或字符组成,可能有重复的值,如何求它的非空子集数目?

比如说有序列{1, 2, 3, 4},它的非空子集包括:

{{1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4},{3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}15项,而空集并没有被统计在内。

再比如说有序列{a, b, c, d, d},它内部有重复的值,但因为集合是不可重复的,因此它的非空子集包括:

{{a}, {b}, {c}, {d}, {a,b}, {a,c}, {a,d}, {b,c}, {b,d},{c,d}, {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}, {a,b,c,d}},也是15项,重复的d被去掉了。

传统的求子集方法在这个问题上可能派不上用场,因为对性能有要求,序列的长度可能达到50甚至更多,如果用递归耗费的时间就太长了。

好在我们无须求子集具体的内容,单单只需要求数目,所以可以借助一个公式。

如果一个集合(注意不是序列),它有N个元素,那么,它就有2N次方个子集。这个子集是包含空集和自身的,所以要求非空子集,就可以用2^N - 1来计算。

好了,到这里,这个问题就可以划分为2个步骤:

1.对序列进行去重

2.利用公式来计算非空子集数目

function estSubsets(arr) {
    var hash = {};
    for(var i=0;i<arr.length;i++){
        hash[arr[i]] = null;
    }
    arr = Object.keys(hash);
    return Math.pow(2,arr.length) - 1;
}
登录后复制

以上是JavaScript求非空子集数目的实现方法的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板