☰

正規表現で数値の割り切れるかどうかをチェックする 質問する

tag-icon • tag-icon regex math
正規表現で数値の割り切れるかどうかをチェックする 質問する

10進数をN数字の列として与えられた場合、それが割り切れるかどうかをどのように確認しますか？M 正規表現のみを使用するint に変換せずに?

M=2、4、5、10 は明らかです。M=3 については、ここで興味深い洞察が得られます。正規表現フィルターの3で割り切れる数値

M=7、9、11、13 などのソリューションを提供できる人はいますか? 一般的なソリューションですか?

テスト コード (Python ですが、任意の言語を使用できます):

M = your number, e.g. 2
R = your regexp, e.g., '^[0-9]*[02468]$'

import re
for i in range(1, 2000):
    m = re.match(R, str(i))
    if i % M:
        assert not m, '%d should not match' % i
    else:
        assert m, '%d must match' % i

興味がある人のために、次の例を示しますM=3(再帰をサポートするエンジンを想定)。

^
(
    | [0369]+ (?1)
    | [147] (?1) [258] (?1)
    | [258] (?1) [147] (?1)
    | ( [258] (?1) ) {3}
    | ( [147] (?1) ) {3}
)
$

更新: 詳しい議論と例についてはこちらをご覧ください糸そこに投稿された式はバグがあることが判明しました (70*N で失敗します) が、「そこに到達する方法」の部分は非常に教育的です。

ベストアンサー1

おそらく驚くべき結果は、そのような正規表現が常に存在するということです。それほど驚くべきことではないのは、それが通常は役に立たないということです。

存在結果は、決定論的有限オートマトン(DFA)と正規表現。それでは、そのようなDFAを作ってみましょう。係数を次のように表します。いいえ（素数である必要はない）そして数値の基数を次のように表す。B、通常の10進数では10です。いいえ0からいいえ−1。初期状態は0です。DFAのシンボルは0からB−1。状態は、入力文字列の左接頭辞を整数として解釈し、それをN.エッジは、右に数字を追加したときの状態の変化を表しています。算術的には、これは状態マップです。

  ス（状態、数字) =B×州+桁（モッドいいえ）。

受け入れ状態は 0 です。余りが 0 であれば割り切れることを示します。したがって、DFA が存在します。DFA によって認識される言語は、正規表現によって認識される言語と同じであるため、DFA が存在します。したがって、これは興味深いものですが、表現を決定する方法についてはあまり説明していないため、役に立ちません。

汎用アルゴリズムが必要な場合は、実行時にそのようなDFAを構築し、直接計算によって状態テーブルにデータを入力するのは簡単です。初期化は、実行時間O(のネストされたループのペアです。ま×いいえ）。マシンによる認識は、入力文字ごとに一定の時間がかかります。これは非常に高速ですが、正規表現ライブラリが本当に必要な場合は使用されません。

実際の正規表現に近づくためには、フェルマーの小定理この定理から、

  Bいいえ−1 ≡ 1 (modいいえ）。

例えば、いいえ= 7 およびB= 10の場合、これは6桁の数字のブロックはどれも{0, …, 6}の集合内の1桁の数字と等価であるということを意味します。指数はそれより小さくなることがあります。いいえ−1; 一般的にはオイラーのトーティエント関数のN.ブロックのサイズを呼び出すだ。 があるいいえブロックの正規表現だ数字はそれぞれ、剰余の特定の同値類を表す。N.これらの式の長さは最大でO(Bだ）は大きいです。いいえ= 7 これは 100 万文字の正規表現のセットです。ほとんどの正規表現ライブラリが壊れると思います。

これは、サンプルコードの式がどのように機能するかに関係しています。式は、(?1)≡ 0 (mod 3) の文字列に一致します。これは、いいえ= 3 である。なぜなら 10 1 ≡ 1 (mod 3) であるからである。つまりあ0B≡AB(mod 3)。指数が 1 より大きい場合はより複雑になりますが、原理は同じです。(厳密に言えば、サンプル コードでは単なる正規表現以上の認識機能を使用していることに注意してください。) 式[0369]、[147]、 は、[258]モジュロ 3 式の数字 0、1、2 の正規表現です。一般化すると、同様の方法で、上記の regexp-digits を使用します。

コードを提供しないのは、この回答よりも記述に時間がかかるためであり、既知の実装で実行されるかどうかは本当に疑わしいからです。

おすすめ記事