最近遇到一个这样的需求,在一组个数为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
网友评论