algorithm - 枚举所有满足给定限制的字符串

Question

我正在寻找以下一类问题的名称，以便我可以通过谷歌搜索有效的算法和更多信息。

我有一个包含三个字符 {-1, 0, 1} 的字母表。

我需要有效地生成所有长度为 24 的字符串，这些字符串主要是 {0}，但有零到八个 {1,-1} 字符以某些模式分布。（模式涉及对 {-1} 的数量和配对的限制）。符合我标准的字符串总数非常少：大约 128,000。

那么这类问题/算法的名称是什么？

Answer 1

我不确定这是否有一个定义明确的“算法类”；这只是组合学的练习。您可以分三步进行生成：

1. 生成设置了 8 位或更少位的所有 24 位数字（如果您预先计算一些查找表，您可以加快速度）
2. 对于每个设置了 n 位的 24 位数字，迭代所有 n 位数字
3. 如果 n 位数的第 k 位为 0，则 24 位数的第 k 个设置位打印为 -1，否则打印为 1

为了更好地解释步骤 2-3，说您的 24 位数字设置了 4 位，看起来像

0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0

0 0 0 0然后，我们从到遍历所有 16 个 4 位数字1 1 1 1，例如：

0 0 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 0
0 1 1 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0 -1 0 0 0 0
0 1 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1 -1 0 0 0 0 0 -1 0 0 0 0
1 1 1 1 gives the string  0 0 0  1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0  1 0 0 0 0

Answer 2

如果您只需要解决一次，也许您可​​以暴力破解它并将结果放入应用程序的查找表中。要检查的 0,1,-1 的 24 位序列不到一万亿个。

如果我的数学计算有误，或者您需要在运行时动态解决问题，我会将问题视为一个由 24 个变量组成的系统，每个变量限制为 -1, 0 ,1 并将其视为约束满足问题，假设您可以以某种方式枚举您的约束。然而，我担心的是，由于您需要查看所有解决方案而不仅仅是一个子集，您可能仍然会被困在详尽地搜索问题空间中。

这篇论文似乎正合您的胃口：枚举约束满足问题的所有解决方案。虽然我无法访问论文的全文以查看它是否有帮助。

我可能一起叫错了树，但也许这是一个起点

Answer 3

与我上一个完全不同的答案，因为工作代码往往胜过研究论文的链接，我在物理论坛上找到了这段代码，我自己不能相信它，我只是把它修好了，所以它在 g++ 下编译并更改为常量在 24 中查找 8 位。它非常快速地枚举所有 8 位的 24 位字符串，其中只有大约 735,000 个。这些“模板”显示非零字符的唯一有效模式。然后，您必须获取这 735,000 个答案中的每一个，并抛出 -/+ 符号并确定每个答案是否符合您的标准，但这样您就从 735,000 个可能的解决方案开始，而不是 2000 亿个。

#include <stdio.h>

 int main()
 {
 int size = 24;
 int pop = 8;

 int n = ((1 << pop) - 1) << (size - pop);

 while(true) {
    printf( "%x\n",n);

    int lowest = n & -n;

     if(lowest > 1) {
        n = n ^ lowest ^ (lowest >> 1);
        continue;
     }

     int high = n & (n + lowest);
     if(high == 0) break;

     int low = n ^ high;

     low = (low << 2) + 3;

     while((low & high) == 0) low <<= 1;
     n = high ^ low;
  }
 }