Generating Binary Sequences

Question

I want to generate every possible binary sequence of numbers, where each sequence in the list is limited to a specific number of 1's and there is padding of zeros to make every list the same length.

For example, if the sequence is supposed to be 4 numbers long, and have 2 ones, all sequences would be:

1100 1010 1001 0110 0101 0011

and the zeros at the front of the number are preserved.

There is a function built into java called Integer.toBinaryString(n); — Stig Tore, Jul 03 '15 at 12:50
But how do I limit it to only the sequences with only a specific number of ones? @StigTore — Chromatica, Jul 03 '15 at 12:54
You can create a `String` of the right size, with the number of `0` and `1` you want in it (for instance `String a = "0011";`), and use the code from https://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string to generate all the permutations/anagrams. — Florent Bayle, Jul 03 '15 at 13:05

score 3 · Answer 1 · answered Jul 03 '15 at 13:05

This can be solved using recursive function calls:

public class BinarySequences {

    public static void main(String[] args) {

        final int numCount = 4; 
        final int oneCount = 2; 

        checkSubString(numCount, oneCount, "");

        for (String res : results) {
            System.out.println(res);
        }
    }

    private static List<String> results = new ArrayList<>();

    private static void checkSubString(int numCount, int oneCount, String prefix) {
        if ((numCount >= oneCount) && (oneCount >= 0)) {
            if (numCount==1) {
                if (oneCount==1) {
                    results.add(prefix + "1");
                } else {
                    results.add(prefix + "0");
                }
            } else {
                checkSubString(numCount-1, oneCount  , prefix + "0");
                checkSubString(numCount-1, oneCount-1, prefix + "1");
            }
        }
    }


}

score 2 · Answer 2 · answered Jul 03 '15 at 13:05

If you want to preserve the 0s, then just add padding:

int end = 100; //Change this
for (int i = 0; i <= end; i++) {
    String bytestring = Integer.toBinaryString(i);
    String padding = "00000000000000000000000000000000";
    bytestring = padding.substring(0, 32 - bytestring.length()) + bytestring;
    System.out.println(bytestring);
}

score 1 · Accepted Answer · edited Jul 03 '15 at 14:48

Try this:

//Edit your min and max, e.g. Integer.MAX_VALUE and Integer.MIN_VALUE
int min = 0;
int max = 10;

for(int i = min; i < max; i++){
    //Make 16 bit long binary Strings
    String s = String.format("%16s", Integer.toBinaryString(i)).replace(' ', '0');

    //Make 4 bits long chunks
    List<String> chunks = new ArrayList<>();
    Matcher matcher = Pattern.compile(".{0,4}").matcher(s);
    while (matcher.find()) {
        chunks.add(s.substring(matcher.start(), matcher.end()));
    }

    StringBuilder b = new StringBuilder();
    for (String c : chunks) {
        //Here you can count the 1 and 0 of the current chunk with c.charAt(index)
        b.append(c);
        b.append(" ");
    }
    System.out.println(b.toString());
}

f_puras · Answer 4 · 2015-07-03T13:30:22.807

Requires org.apache.commons.lang.StringUtils, but this makes it a short one:

final int digits = 4;
final int onesrequired = 2;

int maxindex = (int) Math.pow(2, digits);

for (int i = 0; i < maxindex; i++) {
    String binaryStr = Integer.toBinaryString(i);

    if (StringUtils.countMatches(binaryStr, "1") == onesrequired) {
        System.out.print(String.format("%" + digits + "s", binaryStr).replace(' ', '0') + " ");
    }
}

Generating Binary Sequences

4 Answers4