9

配列の長さが 5 の単純な問題の場合 (実際には、配列の長さは 20.. になる可能性があります)。

AAAAB、AAABA、BAABC、BCAAAなどの定義済みのパターン セットがあります。各パターンは、入力配列と同じ長さです。任意の整数配列を入力として取り、一致するすべてのパターンを返す関数が必要です。（配列はいくつかのパターンに一致する場合があります）できるだけ速く。

" A " は、パターン内で A の位置にあるすべての数値が等しいことを意味します。たとえば、 AAAAAは単にすべての数値が等しいことを意味し、{1, 1, 1, 1, 1}はAAAAAに一致します。

" B " は、B の位置の数が A の位置の数と等しくないことを意味します (つまり、A ではない数のワイルドカード) B で表される数は、等しくなくてもかまいません。たとえば、 ABBAAは、1 番目、4 番目、5 番目の数字が x と等しく、2 番目、3 番目の数字が x と等しくないことを意味します。 {2, 3, 4, 2, 2}はABBAAに一致します。

" C " は、この位置に任意の数字 (つまり、数字のワイルドカード) を指定できることを意味します。{1, 2, 3, 5, 1}はACBBAに一致し、 {1, 1, 3, 5, 1}はACBBAにも一致します

効率的な (比較数に関して) アルゴリズムを探しています。最適である必要はありませんが、最適からそれほど悪くないはずです。決定木のようなものだと思います...

非常に単純ですが非効率的な方法は、次のようなものです。

  • 各パターンを入力と照合してみてください。{a, b, c, d, e}に対してAABCAと言います。かどうかをチェックします。(a=b=e && a!=c)

  • パターンの数がn、パターン/配列の長さがmの場合、複雑さは約O(n*m) です

アップデート：

質問を混乱させずに簡単に理解できるようにする方法がわからないため、質問のより良い表現を自由に提案してください。

理想的なアルゴリズムには、一連のパターンを決定木に変換するなど、何らかの準備が必要です。前処理後の複雑さを、いくつかの特別なパターン セットの O(log n * log m) のようなものにすることができます (推測にすぎません)。

参考になるかもしれない数字: 事前定義されたパターン セットのサイズはおよそ 30 です。一致する入力配列の数は約 1,000 万です。

たとえば、AAAAAとAAAACの両方が定義済みのパターン セットに含まれているとします。次に、AAAAAA が一致する場合、AAAACも一致します。それを認識できるアルゴリズムを探しています。

更新 2

@Gareth Rees の答えは O(n) ソリューションを提供しますが、「 C 」があまりないという仮定の下で。(そうしないと、ストレージが巨大になり、多くの不要な比較が行われます)

また、多くの「 C 」がある状況に対処する方法についてのアイデアも歓迎します。たとえば、長さ 20 の入力配列の場合、事前定義されたパターンごとに少なくとも 10 個の「C 」があります。

4

2 に答える 2

6

これは、O(2 n ) の準備とストレージを O( n ) っぽいランタイムと交換するアイデアです。配列がマシンのワード サイズより長くない場合 (典型的なサイズは 20 であることを暗示しています)、またはパターン内にCの出現回数があまり多くない場合、このアイデアはうまくいくかもしれません。（どちらの条件も満たさない場合は避けてください！）

  1. (準備ステップ、1 回実行)数字をパターンのセットにマッピングする辞書を作成します。各パターンp 、およびそのパターン内のCの出現の各サブセットSについて、パターン内の各Aに対応するセット ビットを持ち、S内のCの各出現について、nを数とします。pを一連のパターンd [ n ]に追加します。

  2. (残りの手順は、新しい配列をパターンと照合する必要があるたびに実行されます。)数値を数値にマッピングする辞書を作成します。

  3. jを配列のインデックス全体に実行させ、各jについて:

    1. iを配列のj番目の整数とします。

    2. iが辞書eにない場合は、 e [ i ] = 0に設定します。

    3. e [ i ] = e [ i ] + 2 ℓ − j − 1を設定します。ここで、ℓ は配列の長さです。

  4. ここで、 eのキーは配列内の個別の数値iであり、値e [ i ] には、配列内のiの出現ごとに対応するセット ビットがあります。ディクショナリdで見つかった各値e [ i ] について、セットd [ e [ i ]]内のすべてのパターンが配列に一致します。

(注: 実際には、ビットセットを逆に構築し、ステップ 3.3 で 2 ℓ − j − 1の代わりに 2 jを使用しますが、説明を明確にするためにこの方法でアルゴリズムを説明しました。)

例を次に示します。パターンAABBAとACBBAがあるとします。前処理ステップで、AABBAは数値 25 (2 進数で 11001) に変わり、ACBBAは数値 25 (2 進数で 11001) と 17 (2 進数で 10001) に変わります。これは、パターン内のCの発生の 2 つの可能なサブセットです。したがって、辞書dは次のようになります。

  • 17 → {アッバ}
  • 25 → {アーバ、アッバ}

配列 {1, 2, 3, 5, 1} を処理すると、e = {1 → 17, 2 → 8, 3 → 4, 5 → 2} となります。値e [1] = 17 がdにあるため、この入力はパターンACBBAと一致します。

配列 {1, 1, 2, 3, 1} を処理すると、e = {1 → 25, 2 → 4, 3 → 2} となります。値e [1] = 25 がdにあるため、この入力はパターンAABBAおよびACBBAと一致します。

于 2012-12-15T21:08:43.770 に答える
0

パターン内の最初のインデックスを取得しA、その位置の値を取得してから、位置をループします。

array配列が文字列のパターンと一致するかどうかを確認するにpatternは、結果がブール値になりmatchます。

int index = pattern.IndexOf('A');
int value = array[index];
bool match = true;
for (int i = 0; i < array.Length; i++) {
  if (pattern[i] != 'C' && i != index) {
    if ((pattern[i] == 'A') != (array[i] == value)) {
      match = false;
      break;
    }
  }
}
于 2012-12-15T18:43:54.480 に答える