迭代字符串枚举

Question

我正在尝试构建一个程序来枚举给定字母表中所有可能的字符串。我计划之后在算法上使用分布式和并行技术，因此递归不是一种选择。到目前为止，我尝试的是这样的：

const char alph[] = "01";

char **
generate(int size)
{
    int i, j, k;
    char str[10];

    memset(str, alph[0], size);
    str[size] = '[=10=]';

    for (i = size-2; i >= -1; --i) {
        for (j = size-1; j > i; --j) {
            for (k = 0; k < strlen(alph); k++) {                
                str[j] = alph[k];
                printf("%s\n", str);
            }
        }
    }
}

所以 generate(2) 的结果应该是 {00, 01, 10, 11}。但是在当前的实现中，我得到了 {00, 01, 00, 01, 01, 11}。我想这是索引的问题，但我找不到哪个索引。

Answer 1

尺寸 2 的简单解决方案

这是一个简单的解决方案，但它仅适用于尺寸 2：

#include <stdio.h>
#include <string.h>

const char alph[] = "01";

// Note: This only works for size 2
void generate(int size) {
  char str[10];
  str[size] = 0;
  for (int i = 0; i < strlen(alph); i++) {
    str[0] = alph[i];
    for (int j = 0; j < strlen(alph); j++) {
      str[1] = alph[j];
      printf("%s\n", str);
    }
  }
}

int main() {
  generate(2);
}

有两个嵌套循环，每个循环对应于输出字符串中的一个位置。如果你想增加输出字符串的长度，一般的想法是增加更多的循环。通常，递归用于执行此操作，但您在问题中禁止递归。

更通用的解决方案

这是一个更通用的解决方案，它做的工作更多，但更容易并行化。它首先计算输出中的行数，然后调用 print_line 打印每一行。对 print_line 的调用都可以是运行并行的，我想，只要你做一些事情来确保输出以所需的顺序打印。

#include <stdio.h>
#include <string.h>
#include <stdint.h>

const char alph[] = "01";

void print_line(uint64_t v, int size)
{
  char str[size + 1];
  str[size] = 0;
  for (int i = size - 1; i >= 0; i--)
  {
    str[i] = alph[v % strlen(alph)];
    v /= strlen(alph);
  }
  printf("%s\n", str);
}

void generate(int size) {
  uint64_t output_line_count = 1;
  for (int i = 0; i < size; i++) { output_line_count *= strlen(alph); }

  for (uint64_t v = 0; v < output_line_count; v++)
  {
    print_line(v, size);
  }
}

int main() {
  generate(3);
}

迭代字符串枚举

Iterative String Enumeration

c

iteration

enumeration

尺寸 2 的简单解决方案

更通用的解决方案