5

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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
Abdiabdisson
  • 67
  • 6
  • 1
    You should at least be able to come up with a basic brute force approach – Androbin Apr 11 '17 at 20:43
  • There's actually a nice iterative method in Knuth but I don't have time to implement it here. Start with the lowest `k` bits set and then think about how to find the next number. At each iteration find the lowest 0 bit after a least one 1. Set that lowest 0 bit and then if you've counted over `m` 1s set the lowest `m-1` bits to 1. – Persixty Apr 11 '17 at 21:04

5 Answers5

1

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");
    }
}
Sagie Levy
  • 357
  • 3
  • 12
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);
        }
    }
}
Jacob G.
  • 28,856
  • 5
  • 62
  • 116
0

One approach is to generate all combinations of k values from the set of n numbers 0..n-1, and use these values to set the corresponding bits in the output.

This Q&A explains how to generate all combinations of k elements from n. With these combinations in hand, use bitwise OR of 1 << v[c][i] to produce the final result, where v[c][i] represents i-th number from combination number c.

Community
  • 1
  • 1
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
0

Below is the solution using Recursion as an approach in 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);
        }
    }
}
Anish Kumar
  • 11
  • 1
-1

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.

Abdiabdisson
  • 67
  • 6