So i'm trying to generate all binaries of a size n but with the condition that only k 1s. i.e
for size n = 4, k=2, (there is 2 over 4 combinations)
1100
1010
1001
0110
0101
0011
I'm stuck and can't figure out how to generate this.
Using the basic recursive method for printing all binary sequence all that remains is to enforce your constraints:
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");
}
}
Here's my non-recursive take on this algorithm. Because there are 2^n
permutations of binary strings, we can use a for-loop to iterate through every possible string and check if the amount of "1"s is not equal to k
:
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);
}
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With