Find all ways to insert zeroes into a bit pattern

Hopefully, this will make it easier to wrap your head around it (please read through this with a pen and paper in hand).

Say the number of zeroes (starting from the right) is x₁, x₂, ..., x_n. eg: if the bit pattern is 00001110001001 then x₁ = 0, x₂ = 2, x₃ = 3, x₄ = 4. n is one more than the number of blocks of ones. Observe that knowing x₁, x₂, ..., x_n is enough to figure out the bit-pattern.

Now if the total number of 1's you have is S and total number of bits you have available is M then we must have that

x₁ + x₂ + ... + x_n = M - S

and x₁ ≥ 0, x_n ≥ 0, x₂ ≥ 1, x₃ ≥ 1, ...

Let z₁ = x₁ + 1 and z_n = x_n + 1

Thus we have

z₁ + x₂ + ... x_n-1 + z_n = M - S + 2

Where z₁ ≥ 1, x₂ ≥ 1, x₃ ≥ 1, ..., z_n ≥ 1.

Now consider a partition of M-S+2 items where each partition has at least one item. Any partition corresponds to a solution of the above equation and a solution corresponds to a partition in a 1-1 fashion.

Place the M-S+2 items along a line. To get a partition, consider placing n-1 sticks in the M-S+2-1 = M-S+1 spots available, between the items.

Thus a solution (and ultimately your required bit-pattern) uniquely corresponds to a way of choosing n-1 spots among M-S+1 spots.

In case of 5 bits, and 1 bits being 1 and 1.

You have n = 3, M = 5, and S = 2.

Thus you have M-S+1 choose n-1 = 4 choose 2 = 6 possiblities.

Enumerating n choose r combinations is a standard problem and you should find a large variety of solutions (some of them very clever!) for that on the web.

For an example see here: http://compprog.files.wordpress.com/2007/10/comb1.c which seems to support a 'lazy' enumeration: next_combination and does not require huge amounts of memory.

I'm not going to give you Objective-C code mainly because:

• I only know Objective-C on a very superficial level.
• I don't have the desire to write all the memory management code required to get this working in a language like C, and it would only detract from the readability anyway.

Instead I will give you some ideas and some code showing how I would implement this in a higher language with generators and garbage collection (Python in this case) and a hint on how to do it without generators. Hopefully someone else may be able to port the code for you if you cannot do it yourself.

I would think about your problem in a slightly different way:

• How many leading zeros are there in your initial "flushed-right" pattern.
• How many ways are there to partition that number of zeros into n partitions.

In your last example you have two leading zeros and three partitions with separators '10' and '1':

2 0 0: 00101  
1 1 0: 01001   
1 0 1: 01010   
0 2 0: 10001   
0 1 1: 10010   
0 0 2: 10100

The separators are always of the form 111..10 except the last which is just 111..1 without the trailing zero.

To enumerate the above partitions use a function like the following in Python:

def partitions(n, x):
    if n == 1:
        yield [x]
    else:
        for i in range(x + 1):
            for p in partitions(n - 1, x - i):
                yield [i] + p

for p in partitions(3, 2):
    print p

Result:

[0, 0, 2]
[0, 1, 1]
[0, 2, 0]
[1, 0, 1]
[1, 1, 0]
[2, 0, 0]

Once you have these partitions it is simple to construct the patterns.

One challenge is that Objective-C doesn't have built-in support for the yield construct. The following rewrite of the above function may be easier to convert to Objective-C:

def partitions(n, x):
    if n == 1:
        return [[x]]
    else:
        result = []
        for i in range(x + 1):
            for p in partitions(n - 1, x - i):
                result.append([i] + p)
        return result

I hope that is of some use to you.