我想生成所有长度为n的二进制数,但有一个条件:只有k个1。即
例如对于 n = 4, k = 2,(有2个在4中的组合)
1100
1010
1001
0110
0101
0011
我卡住了,不知道如何生成这个。
private static void binSeq(int n, int k, String seq) {
if (n == 0) {
System.out.println(seq);
return;
}
if (n > k) {
binSeq(n - 1, k, seq + "0");
}
if (k > 0) {
binSeq(n - 1, k - 1, seq + "1");
}
}
private static void generate(int n, int k) {
for (int i = 0; i < Math.pow(2, n); i++) {
if (Integer.bitCount(i) != k) {
continue;
}
String binary = Integer.toBinaryString(i);
if (binary.length() < n) {
System.out.format("%0" + (n - binary.length()) + "d%s\n", 0, binary);
} else {
System.out.println(binary);
}
}
}
以下是使用递归作为Java方法的解决方案
public class NumberOfBinaryPatternsSpecificOnes {
static int[] bitArray = new int[]{0,1}; // kept binary bits in array
public static void main(String args[])
{
System.out.println("Below are the patterns\n");
int n = 4;
int k = 2;
drawBinaryPattern(n,"",k,0);
}
private static void drawBinaryPattern(int n,String seed,int numberOfOnes,int currentCount)
{
if(n==0)
{
if(currentCount==numberOfOnes){
System.out.println(seed);
}
return;
}
for(int j=0;j<bitArray.length;j++)
{
String temp = seed+bitArray[j];
int currentcountTemp = bitArray[j]==1?(currentCount+1):(currentCount);
if(currentcountTemp>numberOfOnes)
{
return;
}
drawBinaryPattern(n-1,temp,numberOfOnes,currentcountTemp);
}
}
}
int n = 4, k=2;
for (int i = 0; i < Math.pow(2,n) ; i++) {
int a = Integer.bitCount(i);
if (a == k) System.out.println(Integer.toBinaryString(i));
}
我认为这是最简单的答案。
k
位开始,然后考虑如何找到下一个数字。在每次迭代中,在至少有一个1之后找到最低的0位。设置该最低的0位,然后如果您已经计算超过m
个1,则将最低的m-1
位设置为1。 - Persixty