17-1 同一配置を与える置換

ビンゴバルーンのマスの定義の仕方から、{1,2,3,4,5}と{21,22,23,24,25}は180度回転を通じて同一パターンである。また最適解の組にもこの180度回転が適用できる。
このような同一パターンを見つけ出し、ビンゴバルーンの最適解の処理軽減を図りたい。
現状のプログラムでは、相当処理に軽減をする工夫を加えたもののFREE2個程度ですでに推定30時間となってしまっているためである。

まずは鏡像対称を考える。そこから90,180,270度までの回転を考える。これによってだいたい1/8くらいに軽減される。するとおやすみしているうちにFREE2個は完成するだろう。

どうすれば効率よく既に数値計算された組を見つけ出せるかが課題となる。
とりあえず各番号がどのように推移するかを考える。
例えば90度ずつ回転させると
1→16→25→10→1と循環する。ほかも同様に考えて、
2→9→24→17→2
3→15→23→11→3
これになんとか規則性を見出そうとがんばってみると、
とりあえず上の例では3つ目の数は初めのものを引数xとすると明らかに26-xである。
2つ目の数字が自明でない。その理由は同じ回転でもマスの定義の仕方と回転の相性が悪いからと思われる。そこで式にすることはあきらめて、とにかく地道に1~25まで書いていく。
がしかし、上を見てわかる通り25などは90度回転で10に移動するように、これは結局1からの回転の途中を開始としたものとみなせるので、実質

1→16→25→10→1

2→9→24→17→2

3→15→23→11→3

4→21→22→5→4

6→8→20→18→6

7→14→19→12→7

13→13

と上記7つに絞られる。

というわけで、例として5つ組{13,17,20,21,22}を考える。

すると13はいくら移動しても恒等置換なので意味がない。

17は上の推移により2というよりわかり番号へ行く。これはこの組の先頭が(=最も低い番号が)13であるため、この時点で目的は達成される。

するとこれは90度回転をすることになるので13→13、17→2、20→18、21→22、22→5となり、これを昇順に並べ替えて{2,5,13,18,22}となり、最適解も同様に移動したものが新しい組の最適解である。もちろん最高期待値も同じ。

このように順次変換をしていき、もともとの最小番号より小さいものが現れればその移動先を参照するプログラムを作ればよい、ということが分かる。

ただ、これでは組{1,3,4,7,8}のようなものは同一パターンが見つけられない。一応鏡像として{1,2,3,6,7と}という組があるが。

そこで上の話に鏡像パターンを組み込めば、とりあえず1/8くらいに処理が軽減されるのではないかと期待する。

具体的には先ほどの例{13,17,20,21,22}で鏡像を考えて{13,17,18,21,24}を得てどちらが先かをチェックする。

この場合は3番目の数が推移先のほうが若いのですでに数値は得られていることになる。

このようにして、鏡像と4回で恒等置換になるような回転の置換を考えて、その中から自分より順番が若いものを探すプログラムを作成する。順番が若い、というのは各要素の大小を順次判定しても良いが、普通に{1,2,3,…25}の5個の要素からなる部分集合族を与える関数Subsetsを利用できるため、そちらを使う予定。53130個の集合を持つ集合族なのでもしかすると要素抽出に時間がかかる恐れがあるが。

これで処理軽減はできると思うが、FREE3個以上になるとこれをもってしても厳しい可能性がある。が正直FREE3個や4個を配置できるような現場に遭遇することはたぶんあまりないし、FREE4個とか超レアなので確率は(5C3)/(25C5)で1/5313なのでほぼ0。しかもFREEが3個候補としてでるとも限らないので。

目標としてはFREE3個までを求めたいと思っている。

とりあえずはこの方法によりFREE2個の処理軽減を図ることにより、実際には、
1回あたりの処理がなんとか工夫を凝らして12秒まで減らすことができ、これを53000回繰り返すと10600分かかる。ただし、先述の対称、鏡像配置により1/8に単純に減らせると考えられる。もちろん{12,13,14,15,16}などの組は{3,7,13,19,23}が2つしかなかったりするのでこの例にはあてはまらない。
しかし、ざっくり1/8と考えてみることにすると、1325分。これは22時間程度相当。実際には上の例外があるので、たぶん1日~2日程度かかるのではないかとみている。