18

Given a decimal number N as a string of digits, how do I check if it's divisible by M using regular expressions only, without converting to int?

M=2, 4, 5, 10 are obvious. For M=3 some interesting insights here: Regex filter numbers divisible by 3

Can anyone provide a solution for M=7, 9, 11, 13 etc? A generic one?

Testing code (in python, but feel free to use any language):

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

For those curious, here's an example for M=3 (assumes an engine with recursion support):

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

Upd: for more discussion and examples see this thread. The expression posted there turned out to be buggy (fails on 70*N), but "how to get there" part is very educative.

4

6 に答える 6

38

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

存在結果は、決定論的有限オートマトン間の対応から得られます(DFA) と正規表現。それではDFAを作ってみましょう。モジュラスを N で表し (素数である必要はありません)、基数を B で表します。通常の 10 進数では 10 です。0 から N-1 までのラベルが付いた N 個の状態を持つ DFA。初期状態は 0 です。DFA の記号は、0 から B-1 までの数字です。状態は、N で割ったときに整数として解釈される、入力文字列の左プレフィックスの残りを表します。エッジは、右に数字を追加したときの状態の変化を表します。算術的には、これは状態マップ S(state,digit) = B * state + digit (modulo N) です。0 の剰余は割り切れることを示すため、受け入れ状態は 0 です。だから私たちはDFAを持っています。DFA で認識される言語は、正規表現で認識される言語と同じであるため、存在します。これは興味深いものですが、役に立ちません。

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

実際の正規表現に近づくには、フェルマーの小定理を見る必要があります。定理から、B^(N-1) == 1 (モジュロ N) であることがわかります。たとえば、N=7 で B=10 の場合、これが意味することは、割り切れるという目的で、6 桁のすべてのブロックが 0 から 6 の範囲内の 1 桁に相当するということです。指数は N-1 より小さくてもかまいません。一般に、これは N のEuler totient 関数の因数です。ブロックのサイズを D と呼びます。D 桁のブロックには N 個の正規表現があり、それぞれが N を法とする剰余の特定の等価クラスを表します。長さ O(B^D)、これは大きいです。N=7 の場合、これは 100 万文字の長さの正規表現のセットです。ほとんどの正規表現ライブラリが壊れると思います。

これは、コード例の式がどのように機能するかに関連しています。式(?1)は、0 (mod 3) に等しい文字列に一致しています。10^1 == 1 (mod 3) であるため、これは N=3 で機能します。つまり、A0B == AB (mod 3) です。指数が 1 より大きい場合、これはより複雑になりますが、原理は同じです。(コード例では、厳密に言えば単なる正規表現以上の認識機能を使用していることに注意してください。) 式[0369]、[147]、および[258]は、モジュロ 3 式の数字 0、1、および 2 の正規表現です。一般化すると、類似の方法で上記の正規表現数字を使用できます。

（1）この回答よりも書くのに時間がかかり、（2）既知の実装で実行されるとは思えないため、コードを提供していません。

于 2012-11-04T23:08:52.967 に答える
6

数値が単項ベースの場合は、この正規表現を使用できます。s/1{divisor}//g次に、数値が空かどうかをテストします。

これがPerlのやり方です

my @divs = (2,3,5,7,11,13);
for my $num(2..26) {
    my $unary = '1'x$num; # convert num to unary
    print "\n$num can be divided by : ";
    for(@divs) {
        my $test = $unary;
        $test =~ s/1{$_}//g;
        print "$_, " unless $test;
    }
}

出力：

2 can be divided by : 2, 
3 can be divided by : 3, 
4 can be divided by : 2, 
5 can be divided by : 5, 
6 can be divided by : 2, 3, 
7 can be divided by : 7, 
8 can be divided by : 2, 
9 can be divided by : 3, 
10 can be divided by : 2, 5, 
11 can be divided by : 11, 
12 can be divided by : 2, 3, 
13 can be divided by : 13, 
14 can be divided by : 2, 7, 
15 can be divided by : 3, 5, 
16 can be divided by : 2, 
17 can be divided by : 
18 can be divided by : 2, 3, 
19 can be divided by : 
20 can be divided by : 2, 5, 
21 can be divided by : 3, 7, 
22 can be divided by : 2, 11, 
23 can be divided by : 
24 can be divided by : 2, 3, 
25 can be divided by : 5, 
26 can be divided by : 2, 13,
于 2012-09-14T11:58:00.850 に答える
2

文字列を変更して繰り返すことが許可されている場合は、一度に 1 つの長い分割を行うことができます。7 の sed 構文: 残りが得られるまで再適用します。0、1、2、3、4、5、または 6 が 1 つになったら停止します。

s/^0//
s/^7/0/
s/^8/1/
s/^9/2/
s/^([18]4|[29][18]|35|4[29]|56|63)/0/
s/^([18]5|[29][29]|36|43|5[07]|64)/1/
s/^([18]6|[29]3|3[07]|44|5[18]|65)/2/
s/^([18][07]|[29]4|3[18]|45|5[29]|66)/3/
s/^([18][18]|[29]5|3[29]|46|53|6[07])/4/
s/^([18][29]|[29]6|33|4[07]|54|6[18])/5/
s/^([18]3|[29][07]|34|4[18]|55|6[29])/6/

しかし、それは非常に弱いソースです。「正規表現」を完全に廃止し、一度に1文字ずつ読み込んで適切な状態に切り替える方が簡単です。それができない場合は、7 と 13 は運が悪いと思いますが、11 はまだ可能かもしれません。

于 2012-11-04T02:10:42.507 に答える
1

これは、一般的な単純な再帰的な力ずくの長い除算です。最適化されておらず、間違いなくエレガントではありません笑。これは JavaScript です (以下は、コードを含むテスト HTML ページです)。

<!doctype html>
<html>
<head>
<script type="text/javascript">
function isNDivisibleByM(N, M) {
    var copyN = N;
    var MLength = (""+M).length;
    var multiples = [];
    for(var x = 0; x < M; x++)
        multiples[x] = [];
    for(var i = M, x=0; i < M*10; x=0) {
        for(var j = i; j < i+M; j++, x++)
            multiples[x].push(j);
        i+=M;
    }
    var REs = [];
    for(var x = 0; x < M; x++)
        REs[x] = new RegExp("^("+multiples[x].join("|")+")");
    while(N.length >= MLength) {
        var sameLen = (N.length == MLength);
        for(var x = 0; x < M; x++)
            N = N.replace(REs[x], (x==0)?"":(""+x));            
        N = N.replace(/^0/g, "");           
        if(sameLen) break;
    }
    N = N.replace(/^0/g, "");
    var numericN = parseInt(copyN);
    if(N.length == 0) {
        if(numericN%M!=0) {
            console.error("Wrong claim: " + copyN + " NOT divisible by " + M);
        }
        return true;
    }
    if(numericN%M==0 && N.length != 0) {
        console.error("Missed claim: " + copyN + " IS divisible by " + M + " - " + N + " is: " + copyN);
    }
    return false;
}
function run() {
    alert(isNDivisibleByM((""+document.getElementById("N").value), parseInt(document.getElementById("M").value)));
}
</script>
</head>
<body>
<label>N:</label><input type="text" id="N" />
<label>M:</label><input type="text" id="M" />
<button onclick="run()">Is N divisible by M?</button>
</body>
</html>

アイデアは M = 7 の場合です (例):

while(numStr.length > 1) {
    numStr = numStr.replace(/^(14|21|35|42|56|63)/, "");
    numStr = numStr.replace(/^(15|22|36|43|50|64)/, "1");
    numStr = numStr.replace(/^(16|23|30|44|51|65)/, "2");
    numStr = numStr.replace(/^(10|24|31|45|52|66)/, "3");
    numStr = numStr.replace(/^(11|25|32|46|53|60)/, "4");
    numStr = numStr.replace(/^(12|26|33|40|54|61)/, "5");
    numStr = numStr.replace(/^(13|20|34|41|55|62)/, "6");
}
于 2012-11-08T06:04:29.833 に答える
0

この質問と同じくらい興味深いですが、あなたがリストした「明白な」もの以外は可能だとは思いません。

割り切れる規則のほとんどは、数学的操作を必要とします。

先読みを使用して、複数の要件について文字列をテストし、「明らかな」要件のペアを組み合わせることができます (2 x 3、3 x 5 など)。

を使用すると、6 文字の単語を簡単に一致させることができ\b\w{6}\bます。「cat」を含む単語の一致も同様に簡単です\b\w*cat\w*\b。

この 2 つを組み合わせると、次のようになります(?=\b\w{6}\b)\b\w*cat\w*\b。 この正規表現を RegexBuddy で分析します。簡単！これがどのように機能するかです。正規表現が試行される文字列内の各文字位置で、エンジンは最初に正の先読み内で正規表現を試行します。このサブ正規表現、つまり先読みは、文字列内の現在の文字位置が文字列内の 6 文字の単語の先頭にある場合にのみ一致します。そうでない場合、先読みは失敗し、エンジンは文字列内の次の文字位置で最初から正規表現を試行し続けます。

于 2012-09-13T10:21:30.993 に答える