列举的所有串的会议给予的限制

Question

我在寻找名的以下一类问题，所以，我可以google为有效的算法和更多的信息。

我有一个字母三个字{-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

如果你仅仅需要解决这一次，也许你可以仅仅是暴力，它并将结果放在一个查询表，在你的申请。还有不到一万亿美元的24位序列为0,1,-1检查。

如果也许是我在做我的数学是错误的或者你需要动态解决的问题在运行时，我会考虑的问题，如系统的24的变量，每一个局限于-1,0,1和方法，它作为一个 约束满意的问题, 假设你可以列举你的限制在某些方面。我的关切，但是，那是因为你需要看到 所有 解决方案和不仅仅是一个子集，您可能仍会坚持彻底搜索该问题的空间。

本文似乎对你的胡同: 列举的所有解决方案的满意度约束的问题.虽然我没有访问的全文纸，看看是否有帮助。

我可以叫了错误的树都在一起，但也许这是一个开始的地方

Answer 3

我的上一个完全独立的答案，因为工作代码往往胜过研究论文的链接，我在物理论坛并且我自己不能把它归功于它，我只是修复了它，所以它在g ++下编译并改为常量来寻找24位的8位。它很快就列举了所有24 8位的位串，并且只有大约735,000个。这些“模板”显示非零字符的唯一有效模式。然后你必须采取这些735,000个答案中的每一个并抛出 - / +符号并确定每个符号是否符合你的标准，但这样你就可以从735k可能的解决方案开始，而不是200亿。

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