なんかのスレから静岡県警警察官犯罪スレの3種類の数字からなる4桁の10進数は何通りあるかの議論にリンク張られていた。
(COBOLスレからかと思って見直したけど見つからなかった)(追記:数学用大規模言語モデルスレだった。)
住居侵入に当たって指紋の残ったキーから4桁の暗証番号を割り出すにあたっての試行回数が、表題の議論として行われていた。
スレには36通り説と64通り説があったが自分で計算したら18通り 36通りだった。
ただこれも考えを進めていく内に72通り→54通りと減り、最終的に計算機で算出した18通りとした。(その後再計算して36通りとした。)
当初4桁の数を作るに際し手順を三分割して考えていた。
(1)3つの異なる数字を用いて3桁の数を作る(6通り)
(2)3つの数字の中から重複させたい数字を選ぶ(3通り)
(3)(2)で選んだ数を3桁の数の先頭、末尾または中間2か所のいずれかに差し込む(4通り)
としてこの積をとれば72通りではあるが、問題は(3)の手順が(2)と完全に分離できていない。
例えば、132という3桁の数の左端の1の左側に1を挿入した1132と132の1の右側に1を挿入した1132が重複する。
つまり重複を許すことで挿入位置候補が縮退して(3)は4通りではなく常に3通りとなる。
以上から6×3×3=54通りと考えた。
ただこの時気がかりとして、この縮退を織り込んだ手順(3)の文言が思い浮かばなかった。
「(2)で選んだ数と注目している桁が同じ数だったら右側への桁への挿入動作を省く」みたいな条件分岐をすればいいのか?等々考えたが上手くいかなかった。
また3種の数字で作る4桁の数を今後発展させて行ってm種の数字で作るn桁の数としていったときにn-mが大きくなるにつれて縮退の度合いが強まり、この方法では手に負えなくなる気がした。
実際2種の数字で作る4桁の数を考える場合でも割と場合分けが面倒臭くなる。
なんにせよ実験で確かめれば済むことなのでPerlでスクリプトを書くことにした。
substrとか使ってちまちま書くのはやる気が出ないので、一気に候補の文字列を生成してからgrepで濾し取る方法で行くことにした。
四重ループを一行で書く技を使えば重複を許して4種の文字いずれかを用いた4桁の数を出力するワンライナは以下のように書ける。
perl -e "print join qq/\n/, <@{['{1,2,3,4}' x 4]}>"
3種の数字いずれかを用いて作られる4桁の数の場合はこれを少し変えて、
perl -e "print join qq/\n/, <@{['{1,2,3}' x 4]}>
とする。ここにgrepでフィルタを付加していくが、PCREにおける後方参照(\1,\2,...)と否定先読み(?!)を用いれば以下の3つの正規表現で書ける。
((?!\1)(?!\2).で\1にも\2にもマッチしない文字。否定先読みはゼロ幅なので続けて書くことで論理積がとれる。)
/(.)\1(?!\1)(.)(?!\1)(?!\2)./ #1123, 1132, 2213, ...にマッチ
/(.)(?!\1)(.)\1(?!\1)(?!\2)./ #1213, 1312, 2123, ...にマッチ
/(.)(?!\1)(.)(?!\1)(?!\2).\1/ #1231, 1321, 2132, ...にマッチ
これらがそれぞれ6つずつ、合計18通りの文字列を受け付けることが分かった。
先ほど考えた54通りの1/3となったが、これまで過大に数え上げたいたのは132に2を挿入した1232と123の後尾に2を付加した1232を区別できていないからのように思える。
これらの3つの正規表現を|(論理和)でつないでいけば目的のフィルタが得られるかというとそうではなく今回後方参照を使うためにグループ化で捕捉(キャプチャ)しているが、これが論理和をとる度にインデックスがずれ、\1や\2が意図した位置からずれていく。
論理和をクラスタ(非補足グループ)として捕捉を括りだしたり名前付きキャプチャ等も試したが上手く書き下せず、posや(*MARK)や(*SKIP)といったバックトラック制御動詞を駆使しなければいけない問題かと悩んでいたが、結局ブランチリセットグループ(?|)を使うことで解決した。
perldocを何度も読んできたつもりだったがPerl 5.10から使えるこの機能を今回初めて知った。
論理和で括る際に非捕捉グループ(?:A|B)ではなくこのブランチリセットグループ(?|A|B)で括ることでORの分岐の際に後方参照で用いられるグループのインデックス番号がリセットされる。
長々説明したが、結局のところ3種の数字を用いた4桁の数を組み合わせを出力するワンライナは以下のようになる。
perl -e "print join qq/\n/, grep{/(?|(.)\1(?!\1)(.)(?!\1)(?!\2).|(.)(?!\1)(.)\1(?!\1)(?!\2).|(.)(?!\1)(.)(?!\1)(?!\2).\1)/}<@{['{1,2,3}' x 4]}>"
1123
1132
1213
1231
1312
1321
2123
2132
2213
2231
2312
2321
3123
3132
3213
3231
3312
3321
また2種の文字を用いてできる4桁の数は14通りとなる。
perl -e "print join qq/\n/, grep{/(.)\1{0,2}(?!\1)./}<@{['{1,2}' x 4]}>"
まともに考えると7つの正規表現の論理和をとらなければならなくなるが数の生成部で1か2しか出力せず(排中律)、長さも4桁と決まっているのでありえない入力を弾く正規表現を書かずに済むため短くできたように思う。
/(.)\1\1(?!\1)./
/(.)\1(?!\1).\1/
/(.)(?!\1).\1\1/
/(.)\1(?!\1).(?!\1)./
/(.)(?!\1).\1(?!\1)./
/(.)(?!\1).(?!\1).\1/
/(.)(?!\1).(?!\1).(?!\1)./
なんか偉そうに書きながら今気づいたが排中律をうんぬんするなら「ゾロ目を受け付けない正規表現」でもいいわけでこの場合もっと短く書ける。
ただそういった正規表現の外側の条件を前提にすると一般化していった時に混乱しそうではある。
m種の数字で作るn桁の数(m<n)を受け付ける正規表現を書き下す為の一般的な方策とかも考えられるだろうか。
最大m-1個の後方参照が必要になりそう。
そんなわけで静岡県警部補の犯罪を契機にブランチリセットグループを新しく知り、PCREの否定先読みの使い方が少し上手くなった。