Thread: generating binary strings

Hey folks,

I'm in need of some help finding/creating an algorithm to produce all binary strings given some length "n"

It doesn't have to be in C, but you all tend to give good answers so i thought id ask here.

My initial thought is to start at some pivot
_0_000 (pivot isolated by _ _)
and produce every 1/0 for the other bits.
_0_000
_0_001
_0_010

etc.

Translating this into actual source is proving quite difficult so I'm curious if anyone knows any permutation algorithms well suited for this problem.

Thank you!

If you need all binary strings of length n, you can simply count from 0 to 2^n - 1. For example, all 3-bit strings:
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111 <--- 2^3 - 1

If you are really interested in some permutation-related stuff, so this can extend beyond binary symbols, look at the factoradic (factorial base) number system: Factorial number system - Wikipedia, the free encyclopedia.

I'm hoping to extend this binary string stuff to a particular situation.

If I have an identifier like "abcd" I need to produce every possible split for that such that a split consists of a placement of underscores between individual characters.

so abcd could split to:
abcd
a_b_c_d
etc.

Are there any functions for converting ints to binary strings?

Not any standard functions. You can write your own easily enough, with a little loop and bit-shifting:

Code:

for (i = 1 << n-1; i > 0; i >>= 1) {
    if (num & i)  // single ampersand for bit-wise and
        putchar('1');
    else
        putchar('0');
}

To extend it for your situation, with the underscores, you could use a 1 in a given bit position to signify the presence of an underscore and a 0 to signify the lack thereof.