找到将零插入位模式的所有方法

Question

出于某种原因,我一直在努力解决这个问题.我有15位代表一个数字.这些位必须与模式匹配.模式以比特开始的方式定义:它们处于该模式的最正确表示.所以说模式是1 4 1.这些位将是:

000000010111101

因此,一般规则是,取模式中的每个数字,创建多个位(在这种情况下为1,4或1),然后至少有一个空格将它们分开.所以,如果它是1 2 6 1(它将是随机的):

001011011111101

从刷新版本开始,我想生成满足该模式的每个可能的数字.位数将存储在变量中.因此,对于一个简单的情况,假设它是5位,初始位模式是:00101.我想生成:

00101 01001 01010 10001 10010 10100

我想在Objective-C中做这个,但任何类似C的东西都没问题.我似乎无法为此提出一个很好的递归算法.在上面的例子中它是有道理的,但是当我开始进入12431并且必须跟踪它发生故障的一切时.

Answer 1

基于@Mark Byers和Moron 的答案，您的任务可以重新表述如下：

K枚举将零放入适当位置的所有方法N（请参阅重复以及星形和条形的组合）。

示例：对于 15 位和 1 2 6 1 模式，有 N=5 个位置（数字之前/之后以及1s 之间）放置 K=2 个零（右对齐数字的前导零的数量）。路数为二项式(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, 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;
}

输出：

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