美文网首页
算法:一组数目为n的数中选择num个

算法:一组数目为n的数中选择num个

作者: small瓜瓜 | 来源:发表于2019-05-03 16:53 被阅读0次

    最近遇到一个这样的需求,在一组个数为n的数中选择num个,计算一共有多少种选法?

    例如: 1 2 3 4 5 中选择两个数,可以是[1 2],[1 3],[1 5]等,[1 2]和[2 1]算一种

    思路:每个算都有两种可能的状态,选和不选,一共是2的5次方种,我们让1代表选,0代表不选。
    所有状态就可对应于2进制00000-11111,11000代表选择[1 2],我们将2进制数中1的个数等于num的,
    将1对应到那组数的数,即可得到结果

    具体实现代码如下:
    private static Set<String> select(String[] m, int num) {
            Set<String> result = new HashSet<>();
            int l = (int) (Math.pow(2, m.length));
            for (int i = 1; i < l; i++) {
                if (num == -1 || getOneCount(i) == num) {
                    String binaryString = Integer.toBinaryString(i);
                    int bsLen = binaryString.length();
                    StringBuilder sb = new StringBuilder();
                    int start = -1;
                    while ((start = binaryString.indexOf("1", start + 1)) != -1) {
                        sb.append(m[m.length - bsLen + start]);
                    }
                    result.add(sb.toString());
                }
            }
            return result;
        }
    
    
    private static int getOneCount(int n) {
            int count = 0;
            int i = n;
            while (i != 0) {
                if (i % 2 != 0) {
                    count++;
                }
                i = i / 2;
            }
            return count;
        }
    
    下面是python代码实现
    def select(arr, num):
        l = pow(2, len(arr))
        for i in range(1, l):
            s = bin(i)
            if num == -1 or s.count("1") == num:
                s = s[2:].zfill(4)
                sum = ""
                for i in range(len(s)):
                    if s[i] == "1":
                        sum += arr[i]
                yield sum
    

    相关文章

      网友评论

          本文标题:算法:一组数目为n的数中选择num个

          本文链接:https://www.haomeiwen.com/subject/qwkznqtx.html