枚举将K零点放入N个位置的所有方法(参见combinations with repetition和Stars and bars).

示例：对于15位和1 2 6 1模式,存在N = 5个位置(数字之前/之后以及1之间)以使K = 2个零(正确数字的前导零数).方式的数量是binomial(N K-1,K),即二项式(5 2-1,2)= 15.

以下代码中的关键功能是next_combination_counts()和comb2number().

完整的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] 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,...,nzeros} combination
static void
init_comb(int comb[],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 pattern_size) {
  int initial_comb[comb_size];

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

static void 
process(int comb[],int pattern_size) {
  // print combination and pattern
  printa(comb," ");
  printa(pattern,pattern_size," ");
  // print corresponding number
  for (int i = 0; i < comb[0]; ++i)
    printf("%s","0");
  number_t number = comb2number(comb,pattern_size);
  print_binary(number);
  const int width = maxwidth(comb,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 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,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,pattern_size) == num);
  process(comb,pattern_size); // process `num`

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

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

  return 0;
}

输出：

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