Find all ways to insert zeroes into a bit pattern

Question

I've been struggling to wrap my head around this for some reason. I have 15 bits that represent a number. The bits must match a pattern. The pattern is defined in the way the bits start out: they are in the most flush-right representation of that pattern. So say the pattern is 1 4 1. The bits will be:

000000010111101

So the general rule is, take each number in the pattern, create that many bits (1, 4 or 1 in this case) and then have at least one space separating them. So if it's 1 2 6 1 (it will be random):

001011011111101

Starting with the flush-right version, I want to generate every single possible number that meets that pattern. The # of bits will be stored in a variable. So for a simple case, assume it's 5 bits and the initial bit pattern is: 00101. I want to generate:

00101 01001 01010 10001 10010 10100

I'm trying to do this in Objective-C, but anything resembling C would be fine. I just can't seem to come up with a good recursive algorithm for this. It makes sense in the above example, but when I start getting into 12431 and having to keep track of everything it breaks down.

Answer 1

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.

Answer 2

Suppose we have:

000101101

First, count the 0s (5), and count the groups of 0s surrounded by 1s (1). We can forget about the 1s for now. The number of zeros per group in any combination can be a list described as (where + means "or more"):

[0+, 1+, 1+, 0+] where the sum is 6

This is just a variation of a similar problem: find all sets of N non-negative integers that sum to K. For example:

[0+, 0+, 0+, 0+] where the sum is 6

Now, to solve this, start with N=1. The solution is obviously just [6]. With N=2, the solution is:

[0,6] [1,5] [2,4] [3,3] [4,2] [5,1] [6,0]

It's important to notice an underlying theme here: as the left side gets richer, the right side gets poorer. I'll use Haskell to describe the algorithm, as it turns out to be quite elegant for this type of thing:

sumsTo k n
    | n == 1 = [[k]]
    | n > 1  = do
        i <- [0..k]
        s <- sumsTo (k-i) (n-1)
        return (i : s)

The n == 1 case is pretty easy to understand: it just returns one combination: [k]. In the n > 1 case, there's actually a nested loop going on here. It's basically saying:

for each number i from 0 to k
    for each s in sumsTo (k-i) (n-1)
        prepend i to s

Although this algorithm doesn't quite solve your problem, it's good to know in general.

Now, we want the algorithm to operate differently to handle how the middle list items cannot be zero. For those cases, we want to use i <- [1..k] instead of i <- [0..k]. It doesn't matter for the end number since it has no free will (it depends solely on the sum of the previous items). Getting closer, we might say:

sumsTo k n
    | n == 1 = [[k]]
    | n > 1  = do
        i <- [1..k]
        s <- sumsTo (k-i) (n-1)
        return (i : s)

However, we want our first item to be able to start at zero. To patch that up, we can say:

sumsTo k n first_start
    | n == 1 = [[k]]
    | n > 1  = do
        i <- [first_start..k]
        s <- sumsTo (k-i) (n-1) 1
             -- make subsequent sumsTo calls start from 1 instead of 0
        return (i : s)

This gives us the sequences we need given K (the number of 0s) and N (the number of inner groups of 0s plus 2). All that remains is stringifying the sequences (e.g. turning [1,1,0] into "01"). We could go as far as embedding the stringification directly into our recursive algorithm.

Summing it all up, here is a solution in Haskell:

import Data.List

sumsTo k n first_start
    | n == 1 = [[k]]
    | n > 1  = do
        i <- [first_start..k]
        s <- sumsTo (k-i) (n-1) 1
        return (i : s)

-- remove any xes found at the beginning or end of list
trim x list
    = dropWhile (== x)
    $ reverse
    $ dropWhile (== x)
    $ reverse
    $ list

-- interleave [1,3,5] [2,4] = [1,2,3,4,5]
interleave xs ys = concat $ transpose [xs,ys]

solve input = solutions where
    -- pull out groups of 1s and put them in a list
    groupsOfOnes = filter ((== '1') . head) $ group input

    -- count 0s
    k = length $ filter (== '0') input

    -- trim outer 0s
    trimmed = trim '0' input

    -- count inner groups of 0s
    innerGroups = length $ filter ((== '0') . head) $ group trimmed

    -- n is number of outer groups (which is innerGroups + 2)
    n = innerGroups + 2

    -- compute our solution sequences
    -- reverse them so our answer will be in lexicographic order
    sequences = reverse $ sumsTo k n 0

    -- to transform a sequence into a group of zeros,
    -- simply make strings of the indicated number of zeros
    groupsOfZeros seq = [replicate n '0' | n <- seq]

    -- a solution for a sequence is just the zeros interleaved with the ones
    solution seq = concat $ interleave (groupsOfZeros seq) groupsOfOnes

    solutions = map solution sequences

main = do
    input <- getLine
    putStr $ unlines $ solve input

In conclusion, I recommend learning Haskell so you can prototype algorithms more quickly :-)

Answer 3

Is this a theoretical or practical problem? Do you need the optimal O(N) or reasonably good execution time? If this is a practical problem, and unless it's in the inner loop of something, just checking every 15-bit number should be fast enough. It's only 32k numbers.

Just get the partitions for your number, something like this:

void get_groups(ushort x, int* groups) {
  int change_group = 0;
  while(x) {
    if (x & 1) {
      ++(*groups);
      change_group = 1;
    } else {
      if (change_group) {
        ++groups;
        change_group = 0;
      }
    }
    x >>= 1;
  }
}

And then, for every 15-bit number, check if it produces the same groups array as your initial number.

Note: The groups array should be able to accommodate the maximum number of groups (e.g. should have size 8 for 15-bit numbers).

Answer 4

Building on @Mark Byers's and Moron's answers your task can be reformulated as follows:

Enumerate all ways to put K zeros into N places (see combinations with repetition and Stars and bars).

Example: For 15 bits and 1 2 6 1 pattern there are N=5 places (before/after the number and between 1s) to put K=2 zeros (number of leading zeros for a flush-right number). Number of ways is binomial(N + K - 1, K) i.e., binomial(5+2-1, 2) = 15.

The key functions in the code below are next_combination_counts() and comb2number().

Full program in C

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>

#define SIZE(arr) (sizeof(arr)/sizeof(*(arr)))

#define PRInumber "u"
typedef unsigned number_t;

// swap values pointed to by the pointer
static void
iter_swap(int* ia, int* ib) {
  int t = *ia;
  *ia = *ib;
  *ib = t;
}

// see boost::next_combinations_counts()
// http://photon.poly.edu/~hbr/boost/combinations.html
// http://photon.poly.edu/~hbr/boost/combination.hpp
static bool 
next_combination_counts(int* first, int* last) {
  /*
0 0 2 
0 1 1 
0 2 0 
1 0 1 
1 1 0 
2 0 0 
   */
    int* current = last;
    while (current != first && *(--current) == 0) {
    }
    if (current == first) {
        if (first != last && *first != 0)
            iter_swap(--last, first);
        return false;
    }
    --(*current);
    iter_swap(--last, current);
    ++(*(--current));
    return true;
}

// convert combination and pattern to corresponding number
// example: comb=[2, 0, 0] pattern=[1,1] => num=5 (101 binary)
static number_t 
comb2number(int comb[], int comb_size, int pattern[], int pattern_size) {
  if (pattern_size == 0)
    return 0;
  assert(pattern_size > 0);
  assert(comb_size > pattern_size);

  // 111 -> 1000 - 1 -> 2**3 - 1 -> (1 << 3) - 1
  // 111 << 2 -> 11100
  number_t num = ((1 << pattern[pattern_size-1]) - 1) << comb[pattern_size];  
  int len = pattern[pattern_size-1] + comb[pattern_size];
  for (int i = pattern_size - 1; i--> 0; ) {
    num += ((1 << pattern[i]) - 1) << (comb[i+1] + 1 + len);
    len += pattern[i] + comb[i+1] + 1;
  }  

  return num;
}

// print binary representation of number
static void 
print_binary(number_t number) {
  if (number > 0) {
    print_binary(number >> 1);
    printf("%d", number & 1);
  }
}

// print array
static void
printa(int arr[], int size, const char* suffix) {
  printf("%s", "{");
  for (int i = 0; i < (size - 1); ++i)
    printf("%d, ", arr[i]);
  if (size > 0)
    printf("%d", arr[size - 1]);
  printf("}%s", suffix);
}

static void 
fill0(int* first, int* last) {
  for ( ; first != last; ++first)
    *first = 0;
}

// generate {0,0,...,0,nzeros} combination
static void
init_comb(int comb[], int comb_size, int nzeros) {
  fill0(comb, comb + comb_size);
  comb[comb_size-1] = nzeros;
}

static int
sum(int* first, int* last) {
  int s = 0;
  for ( ; first != last; ++first)
    s += *first;
  return s;
}

// calculated max width required to print number (in PRInumber format)
static int 
maxwidth(int comb[], int comb_size, int pattern[], int pattern_size) {
  int initial_comb[comb_size];

  int nzeros = sum(comb, comb + comb_size);
  init_comb(initial_comb, comb_size, nzeros);
  return snprintf(NULL, 0, "%" PRInumber, 
                  comb2number(initial_comb, comb_size, pattern, pattern_size)); 
}

static void 
process(int comb[], int comb_size, int pattern[], int pattern_size) {
  // print combination and pattern
  printa(comb, comb_size, " ");
  printa(pattern, pattern_size, " ");
  // print corresponding number
  for (int i = 0; i < comb[0]; ++i)
    printf("%s", "0");
  number_t number = comb2number(comb, comb_size, pattern, pattern_size);
  print_binary(number);
  const int width = maxwidth(comb, comb_size, pattern, pattern_size);
  printf(" %*" PRInumber "\n", width, number);
}

// reverse the array
static void 
reverse(int a[], int n) {
  for (int i = 0, j = n - 1; i < j; ++i, --j) 
    iter_swap(a + i, a + j);  
}

// convert number to pattern
// 101101111110100 -> 1, 2, 6, 1
static int 
number2pattern(number_t num, int pattern[], int nbits, int comb[]) {
  // SIZE(pattern) >= nbits
  // SIZE(comb) >= nbits + 1
  fill0(pattern, pattern + nbits);
  fill0(comb, comb + nbits + 1);

  int i = 0;
  int pos = 0;
  for (; i < nbits && num; ++i) {
    // skip trailing zeros
    for ( ; num && !(num & 1); num >>= 1, ++pos)
      ++comb[i];
    // count number of 1s
    for ( ; num & 1; num >>=1, ++pos) 
      ++pattern[i];
  }
  assert(i == nbits || pattern[i] == 0);  
  const int pattern_size = i;  

  // skip comb[0]
  for (int j = 1; j < pattern_size; ++j) --comb[j];
  comb[pattern_size] = nbits - pos;

  reverse(pattern, pattern_size);
  reverse(comb, pattern_size+1);
  return pattern_size;
}

int 
main(void) {
  number_t num = 11769; 
  const int nbits = 15;

  // clear hi bits (required for `comb2number() != num` relation)
  if (nbits < 8*sizeof(number_t))
    num &=  ((number_t)1 << nbits) - 1;
  else
    assert(nbits == 8*sizeof(number_t));

  // `pattern` defines how 1s are distributed in the number
  int pattern[nbits];
  // `comb` defines how zeros are distributed 
  int comb[nbits+1];
  const int pattern_size = number2pattern(num, pattern, nbits, comb);
  const int comb_size = pattern_size + 1;

  // check consistency
  // . find number of leading zeros in a flush-right version
  int nzeros = nbits;
  for (int i = 0; i < (pattern_size - 1); ++i)
    nzeros -= pattern[i] + 1;
  assert(pattern_size > 0);
  nzeros -= pattern[pattern_size - 1];
  assert(nzeros>=0);

  // . the same but using combination
  int nzeros_comb = sum(comb, comb + comb_size);
  assert(nzeros_comb == nzeros);

  // enumerate all combinations 
  printf("Combination Pattern Binary Decimal\n");
  assert(comb2number(comb, comb_size, pattern, pattern_size) == num);
  process(comb, comb_size, pattern, pattern_size); // process `num`

  // . until flush-left number 
  while(next_combination_counts(comb, comb + comb_size))
    process(comb, comb_size, pattern, pattern_size);

  // . until `num` number is encounterd  
  while (comb2number(comb, comb_size, pattern, pattern_size) != num) {
    process(comb, comb_size, pattern, pattern_size);
    (void)next_combination_counts(comb, comb + comb_size);
  }

  return 0;
}

Output:

Combination Pattern Binary Decimal
{1, 0, 0, 1, 0} {1, 2, 6, 1} 010110111111001 11769
{1, 0, 1, 0, 0} {1, 2, 6, 1} 010110011111101 11517
{1, 1, 0, 0, 0} {1, 2, 6, 1} 010011011111101  9981
{2, 0, 0, 0, 0} {1, 2, 6, 1} 001011011111101  5885
{0, 0, 0, 0, 2} {1, 2, 6, 1} 101101111110100 23540
{0, 0, 0, 1, 1} {1, 2, 6, 1} 101101111110010 23538
{0, 0, 0, 2, 0} {1, 2, 6, 1} 101101111110001 23537
{0, 0, 1, 0, 1} {1, 2, 6, 1} 101100111111010 23034
{0, 0, 1, 1, 0} {1, 2, 6, 1} 101100111111001 23033
{0, 0, 2, 0, 0} {1, 2, 6, 1} 101100011111101 22781
{0, 1, 0, 0, 1} {1, 2, 6, 1} 100110111111010 19962
{0, 1, 0, 1, 0} {1, 2, 6, 1} 100110111111001 19961
{0, 1, 1, 0, 0} {1, 2, 6, 1} 100110011111101 19709
{0, 2, 0, 0, 0} {1, 2, 6, 1} 100011011111101 18173
{1, 0, 0, 0, 1} {1, 2, 6, 1} 010110111111010 11770

Answer 5

If your pattern is 00101, as in the example, then one way you can consider for generating the six patterns is:

Look at the pattern 0000 then choose two of the zeroes to change to ones. Now you'll have something like 0011. Now just insert a 0 after each 1 (except for the last one). Now you'll have 00101.

Note that you are choosing 2 out of 4 places, and there are 6 different possible ways you can do that (consistent with what you wrote). Now you just need a way to choose the two bits to flip. You can use something like the algorithm specified at this link:

http://compprog.wordpress.com/2007/10/17/generating-combinations-1/