Java. How to generate all integers with certain number of 1's and 0's in it?

Question

What is the most efficient way to solve this problem using Java ?
For example: generate all numbers containing three 1's & two 0's

Solution:

11100
11010
10110
01110
11001
10101
01101
10011
01011
00111

Answer 1

You can use recursion:

public static void generateBits(String s, int ones, int zeros)
{
    if(ones > 0)
        generateBits(s + "1", ones - 1, zeros);
    if(zeros > 0)
        generateBits(s + "0", ones, zeros - 1);

    if(ones == 0 && zeros == 0)
        System.out.println(s);
}

The function accepts a partially completed string and a count of how many ones and zeros are left to add, then recurses for the case of adding a one and adding a zero (if any are remaining). When there are no more left to add it prints the string. This will generate each number once with no duplicates. You can parse the string into a number if you need to instead of printing it out. Call like this:

generateBits("", 3, 2);

I used the String type to allow leading zeros, while keeping it simple, however as pointed out in a comment by @Aivean, string concantenation can be expensive. Here's an alternative, more efficient solution that uses longs, and converts to a binary string representation with leading zeros when printing out the values:

public static void generateBits(long val, int ones, int zeros, int len)
{
    if(ones > 0)
        generateBits((val << 1) + 1L, ones - 1, zeros, len + 1);
    if(zeros > 0)
        generateBits(val << 1, ones, zeros - 1, len + 1);

    if(ones == 0 && zeros == 0)
        System.out.println(String.format("%"+len+"s", Long.toBinaryString(val)).replace(' ', '0'));
} 

You need to pass in 0 for the length when calling it at the top level. You would call it like this:

generateBits(0L, 3, 2, 0);

Answer 2

Here's non-recursive BitSet-based solution:

static void genCombinations(int n, int k) {
    BitSet bs = new BitSet(n);
    bs.set(0, k);
    while(true) {
        // output
        for(int i=0; i<n; i++)
            System.out.print(bs.get(i) ? "1" : "0");
        System.out.println();
        int b = bs.previousClearBit(n-1); // the last zero
        int b1 = bs.previousSetBit(b); // the last one before that zero
        if(b1 == -1)
            return;
        bs.clear(b1);
        bs.set(b1+1, b1+(n-b)+1);
        bs.clear(b1+(n-b)+1, n);
    }
}

public static void main(String[] args) {
    genCombinations(5, 3);
}

Such iterative approach sometimes more convenient as you can create an Iterable class like this:

public static class Combinations implements Iterable<String> {
    private int n;
    private int k;

    public Combinations(int n, int k) {
        this.n = n;
        this.k = k;
    }

    @Override
    public Iterator<String> iterator() {
        return new Iterator<String>() {
            BitSet bs = new BitSet(n);

            {
                bs.set(0, k);
            }

            @Override
            public boolean hasNext() {
                return bs != null;
            }

            @Override
            public String next() {
                char[] res = new char[n];
                for (int i = 0; i < n; i++)
                    res[i] = bs.get(i) ? '1' : '0';
                int b = bs.previousClearBit(n - 1);
                int b1 = bs.previousSetBit(b);
                if (b1 == -1)
                    bs = null;
                else {
                    bs.clear(b1);
                    bs.set(b1 + 1, b1 + (n - b) + 1);
                    bs.clear(b1 + (n - b) + 1, n);
                }
                return new String(res);
            }
        };
    }
}

And use it in the for loop:

for(String comb : new Combinations(5, 3)) {
    System.out.println(comb);
}

Answer 3

To get an int with leading zero's, you will have to generate it as a String. This is the fastest way without duplicates:

public final class Permutator {

  public static void main(String[] args) {
    new Permutator(3, 5);
  }

  public Permutator(int numberOfOnes, int length) {
    StringBuilder start = new StringBuilder();
    for (int x = 0; x < length; x++)
      start.append('0');
    permutate(numberOfOnes, 0, 0, length, start);
    System.exit(0);
  }

  public void permutate(int numberOfOnes, int first, int depth, int length, StringBuilder base) {
    for (int x = first; x < length; x++) {
      StringBuilder onesAndZeros = new StringBuilder(base.toString());
      onesAndZeros.setCharAt(x, '1');
      if (numberOfOnes == depth + 1)
        System.out.println(onesAndZeros.toString());
      else
        permutate(numberOfOnes, x + 1, depth + 1, length, onesAndZeros);
    }
  }
}

Answer 4

Nice puzzle, not utmost optimized, but my attempt: 0/1 for bit in int, recursion on ones only (and bit count). The number of results is (ones + zeros over ones).

    int ones = 3;
    int zeroes = 2;
    allIntsWithOnesAndZeroes(ones, zeroes);

public static void allIntsWithOnesAndZeroes(int ones, int zeroes) {
     int bitCount = ones + zeroes;
     int bits = 0;
     SortedSet<Integer> results = new TreeSet<>();
     all(results, bits, 0, bitCount, ones);

     System.out.printf("(%d over %d) = %d, #%d: %s%n",
         bitCount, ones, over(bitCount, ones), results.size(), results);
     long a = 0;
     for (int n : results) {
         System.out.println("- " + Integer.toBinaryString(n));
         a |= 1L << n;
     }
     System.out.printf("all: %s%n", Long.toBinaryString(a));
}

private static void all(Set<Integer> results, int bits, int i, int bitCount, int ones) {
    if (ones == 0) {
        results.add(bits); // Assumes ones > 0.
    }
    if (i >= bitCount) {
        return;
    }
    all(results, bits, i + 1, bitCount, ones);
    int bits2 = bits | (1 << i);
    all(results, bits2, i + 1, bitCount, ones - 1);
}

Some math:

public static long fac(long x) {
    long n = 1;
    while (x > 1) {
        n *= x;
        --x;
    }
    return n;
}

public static long over(long x, long y) {
    return fac(x) / fac(y) / fac(x - y);
}