Clever Geek Handbook

Get all binary combination of size n, but only k 1s

So, I am trying to generate all binaries of size n, but with the condition that only k 1s. i.e

for size n = 4, k = 2 (there are 2 more than 4 combinations)

1100
1010
1001
0110
0101
0011

I am stuck and cannot figure out how to do this.

+3


source to share


4 answers


One approach is to generate all combinations of values k

from the set of n

numbers 0 .. n-1

and use those values ​​to set the appropriate bits in the output file.



This Q&A explains how to generate all combinations of items k

from n

. When using these combinations, use bitwise OR to 1 << v[c][i]

get the final result, where v[c][i]

is the i

th number from the combination number c

.

0


source


Using the basic recursive method to print the entire binary sequence, all that's left is constraint enforcement:



    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");
    }
}
0


source


Here's my non-recursive implementation of this algorithm. Since there are permutations of 2^n

binary strings, we can use a for-loop to iterate over every possible line and check if the number is greater than "1" 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);
        }
    }
}
0


source


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));
    }

I think this is the simplest answer.

-1


source






More articles:


All Articles