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

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 到 1 1 1 1 的所有 16 个 4 位数字，并且， 例如：

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 位。它很快就枚举了所有 24 位字符串8 位，大约只有 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;
  }
 }