title: Find all ways to insert zeroes into a bit pattern
body: <p>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:</p>
  
  <p>000000010111101</p>
  
  <p>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):</p>
  
  <p>001011011111101</p>
  
  <p>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:</p>
  
  <p>00101
  01001
  01010
  10001
  10010
  10100</p>
  
  <p>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.</p>