指定された制限を満たすすべての文字列を列挙する

Question

次のクラスの問題の名前を探しているので、効果的なアルゴリズムや詳細をグーグルで検索できます。

3つの文字{-1、0、1}のアルファベットがあります。

長さ24のすべての文字列を効果的に生成する必要があります。ほとんどの文字列は{0}ですが、特定のパターンで0〜8個の{1、-1}文字が分布しています。 （パターンには、{-1}の数と組み合わせの制限が含まれます）。私の基準を満たす文字列の総数はかなり控えめで、約128,000です。

では、このクラスの問題/アルゴリズムの名前は何ですか？

Answer 1

明確に定義された「アルゴリズムクラス」があるかどうかわかりません。このために;それは組み合わせ論の演習です。生成は3つのステップで実行できます。

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ビットシーケンスは1兆未満です。

おそらく間違った計算をしている場合、または実行時に動的に問題を解決する必要がある場合、問題をそれぞれ-1、0、1に制限された24個の変数のシステムと見なし、<何らかの方法で制約を列挙できる場合、a href = "http://en.wikipedia.org/wiki/Constraint_satisfaction_problem" rel = "nofollow noreferrer">制約充足問題。ただし、私の懸念は、サブセットだけでなくすべてのソリューションを見ることを必要とするため、問題のあるスペースを徹底的に検索することに固執する可能性があることです。

この論文は、あなたの路地のすぐ上にあるようです。論文の全文にアクセスして、それが役立つかどうかを確認することはできません。

間違ったツリーをまとめてbarえているかもしれませんが、おそらくこれが出発点です

Answer 3

作業コードは研究論文へのリンクを切り捨てる傾向があるので、私の最後とは完全に別の答えです。このコードは Physics Forum は自分で信用できないため、修正してg ++でコンパイルし、定数を24の8ビットを探すように変更しました。 8ビットがオンのビット文字列で、これらのうち約735,000のみです。これらの「テンプレート」には、ゼロ以外の文字に有効なパターンのみが表示されます。その後、これらの735,000の回答をそれぞれ取り、-/ +記号を回して、それぞれが基準を満たしているかどうかを判断する必要がありますが、この方法では、2,000億ではなく735kの可能なソリューションから始めています。

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