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

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

希望这会让您更容易理解它（请用手中的笔和纸阅读本文）。

假设零的数量（从右侧开始）为 x₁、x₂、...、x_n。例如：如果位模式为 00001110001001，则 x₁ = 0、x₂ = 2、x₃ = 3、x₄ = 4。n 比 1 的块数多 1。请注意，知道 x₁、x₂、...、x_n 就足以找出位模式。

现在，如果 1 的总数为 S，可用位数为 M，那么我们必须有

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

且 x₁ ≥ 0，x_n ≥ 0，x₂ ≥ 1， x₃ ≥ 1, ...

设 z₁ = x₁ + 1
和 z_n = x_n + 1

因此我们有

z₁ + x₂ + ... x< sub>n-1 + z_n = M - S + 2

其中 z₁ ≥ 1，x₂ ≥ 1， x₃ ≥ 1, ..., z_n ≥ 1。

现在考虑 M-S+2 个项目的分区，其中每个分区至少有一个项目。任何分区都对应于上式的一个解，并且解对应于 1-1 方式的分区。

将 M-S+2 个物品沿一条线放置。要获得分区，请考虑将 n-1 根棍子放置在物品之间的 M-S+2-1 = M-S+1 可用位置中。

因此，解决方案（以及最终您所需的位模式）唯一对应于在 M-S+1 个点中选择 n-1 个点的方式。

在 5 位的情况下，1 位为 1 和 1。

您有 n = 3、M = 5 和 S = 2。

因此您有 M-S+1 选择 n-1 = 4 选择 2 = 6 种可能性。

枚举 n 选择 r 组合是一个标准问题，您应该在网络上找到各种各样的解决方案（其中一些非常聪明！）。

有关示例，请参见此处： http://compprog.files.wordpress.com/ 2007/10/comb1.c 似乎支持“惰性”枚举：next_combination 并且不需要大量内存。

Answer 2

我不会向您提供 Objective-C 代码，主要是因为：

• 我对 Objective-C 的了解非常肤浅。
• 我不想用 C 这样的语言编写所需的所有内存管理代码，而且无论如何它只会降低可读性。

相反，我会给你一些想法和一些代码，展示如何使用生成器和垃圾收集（在本例中为 Python）以更高级的语言实现这一点，并提示如何在没有生成器的情况下实现这一点。如果您自己做不到，希望其他人能够为您移植代码。

我会以稍微不同的方式思考你的问题：

• 在你最初的“右对齐”模式中有多少个前导零。
• 有多少种方法可以将该数量的零划分为 n 个分区。

在上一个示例中，您有两个前导零和三个带有分隔符“10”和“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

分隔符始终采用 111..10 形式，最后一个分隔符仅为 111 ..1 没有尾随零。

要枚举上述分区，请使用 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

结果：

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

一旦有了这些分区，构建模式就很简单。

一项挑战是 Objective-C 没有对 Yield 构造的内置支持。对上述函数进行以下重写可能会更容易转换为 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

我希望这对您有用。

Answer 3

基于 @Mark Byers 的 和 白痴的答案你的任务可以重新表述如下：枚举

将K个零放入N个位置的所有方法（参见重复组合和星星和酒吧）。

示例：对于 15 位和 1 2 6 1 模式，有 N=5 个位置（数字之前/之后以及 1 之间）放置 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

Answer 4

假设我们：

000101101

首先，计算 0 (5)，并计算 1 包围的 0 组 (1)。我们现在可以忘记 1。任何组合中每组零的数量可以是一个描述为的列表（其中 + 表示“或更多”）：

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

这只是类似问题的变体：找到 N 个非负的所有集合总和为 K 的整数。例如：

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

现在，要解决此问题，请从 N=1 开始。解决方案显然就是[6]。当 N=2 时，解决方案是：

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

重要的是要注意这里的潜在主题：随着左侧变得更富有，右侧变得更贫穷。我将使用 Haskell 来描述该算法，因为事实证明它对于此类事情非常优雅：

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

n == 1 情况非常容易理解：它只返回一个组合：<代码>[k]。在n>中1 情况，这里实际上发生了一个嵌套循环。它基本上是在说：

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

虽然这个算法并不能完全解决你的问题，但总体上了解一下还是有好处的。

现在，我们希望算法以不同的方式运行，以处理中间列表项不能为零的情况。对于这些情况，我们希望使用 i <- [1..k] 而不是 i <- [0..k]。结束数字并不重要，因为它没有自由意志（它仅取决于前面项目的总和）。更接近的是，我们可能会说：

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

但是，我们希望我们的第一个项目能够从零开始。为了修补这个问题，我们可以说：

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)

给定 K（0 的数量）和 N（内部 0 组的数量加上 2），这为我们提供了所需的序列）。剩下的就是对序列进行字符串化（例如将 [1,1,0] 转换为“01”）。我们甚至可以将字符串化直接嵌入到我们的递归算法中。

总而言之，这是 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

总之，我建议学习 Haskell，以便您可以更快地构建算法原型:-)

Answer 5

这是理论问题还是实践问题？您是否需要最优的 O(N) 或相当好的执行时间？如果这是一个实际问题，并且除非它在某些内容的内部循环中，否则只需检查每个 15 位数字就应该足够快了。只有 32k 个数字。

只需获取您的数字的分区，如下所示：

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;
  }
}

然后，对于每个 15 位数字，检查它是否生成与您的初始数字相同的组数组。

注意：groups 数组应该能够容纳最大数量的组（例如，15 位数字的大小应该为 8）。

Answer 6

如果您的模式是 00101（如示例所示），那么您可以考虑生成六个模式的一种方法是：

查看模式 0000，然后选择两个零来生成更改为 。现在您将得到类似于 0011 的内容。现在只需在每个 1 之后插入一个 0（最后一个除外）。现在您将拥有 00101。

请注意，您正在从四个位置中选择两个，并且有六种不同的可能方法可以做到这一点（与您所写的一致）。现在您只需要一种方法来选择要翻转的两位。您可以使用类似于此链接中指定的算法：生成组合< /a>