プログラミングパズルに関心のある人は雑談しましょう！
ご無沙汰しています。塗り壁です。 現在の状況をアップさせてもらいます。 以下，（３、２）型のロト問題について一般論を考察する。 Ｏ（Ｎ）（Ｎ＞＝６）でＮ次の最適解全体を表わすとき、最終目標はＯ（Ｎ）の構造の決定（要するに，Ｎ次の最適解の分類） である。分類するためには，その基準としての同値関係を定めることが通例であるが，本問題の同値関係として下記の3つを考える。 交換同値：二つの最適解は，数字の適当な交換により一方から他方が得られるとき交換同値であると言うことにする。なお、最適解に対し，その数字を任意に交換したものが最適解になることは明らかである。例えば6次の場合｛［１２３］［４５６］｝ と｛［１３５］［２４６］｝は交換同値である。交換同値である二つの解は本質的には同じ解と考えることができる。 頻度同値：最適解Ｘが与えられたときα（１）はＸが含む３−集合（（Ｎ，３）型の組合せ）で１を含むものの個数、・・・α（Ｎ） はＸが含む３−集合でＮを含むものの個数とすると多重集合｛α（１）・・・α（Ｎ）｝が定まる。これを頻度集合と言うこ とにする。二つの最適解が頻度同値であるとは同一の頻度集合を持つ事とする。定義から明らかに，交換同値ならば頻度同 値である。言い換えれば、頻度同値の関係は交換同値の関係より粗い。 成分同値：最適解Ｘにより連結成分分割（三吉氏定義のもの）が得られる。この分割の型（例えば，Ｎ＝７のときは３＋４型等） が同じであるとき成分同値であると言う。成分同値の関係も交換同値の関係より粗い。三吉氏の考察より、成分数は２個以 下である。即ち、成分同値の同値類の数は項数が高々２のＮの自然数分割で各項が３以上のものの個数が上限となる。 上記同値関係により、Ｏ（Ｎ）を分類することが当面の課題になる。 ・６次の場合 最適解は共通点を持たない二つの３−集合の対である。従って、全ての最適解は交換同値であり、その個数はＣ（６，３）＝２０個になる。交換同値ならば頻度同値且つ成分同値であるから６次の場合は完全解決ができた。 ・７次の場合 一つの最適解は｛［１２３］［４５６］［４６７］［５６７］｝である。この頻度集合は｛１１１２２２３｝であり、成分分割の型は３＋４である。 逆にこの頻度集合を実現するには、頻度３の数字は７通り、残りの６個の中から頻度２の数字３個の選び方はＣ（６，３）＝２０通り。都合１４０通りの最適解があり、それらは交換同値である。従って、頻度同値類は一般的には複数の交換同値類を 含む（と思われる）が、今の場合には交換同値類と一致（且つ成分同値類とも一致）していることが分かる。 成分数が１個の場合が存在するかどうかを確認する。プログラムで探して次の解が見つかった。 ｛［１２３］［１２４］［３４５］［５６７］｝これの頻度集合は｛１１２２２２２｝である。 結論として、７次の場合は２種類の交換同値類があり共に成分同値類、頻度同値類と一致していることがわかり７次の場合も解決した。 ８次以上は現在調査中。分かり次第投稿します。
> ３個から２個以上の場合、連結成分２個からなる最小解がかならず存在する 連結成分２個からなる最小解を持つ n の無限の系列 (n = 2^h - 1) が存在するという意味ですね。 ちなみに nC2 のペアを生成する組の個数の最小値については 上界： n*(n+1)/4 - [(n+1)/2] （[] はガウス記号） 下界： n が奇数のとき n*(n-1)/6 （n = 2^h - 1 のときは一致） n が偶数のとき n^2/6 上界の分母の４をどこまで大きくできるか興味があります。
> ３個から２個以上の場合、連結成分２個からなる最小解がかならず存在する 残念ながらそこまでは言えてないです。 連結成分２個に近い構造を持つということが言えた程度です。
三吉さん、有難うございました。 やっと、理解できました。 この結果は、３個から２個以上の場合、連結成分２個からなる最小解がかならず存在する ことを保証するもので、大きな意味があります。 しつこく、こだわったのはこの点を気にしていたからです。ご容赦あれ。 本当にありがとうございました。これをもとに５個から３個以上の場合を 考えてみます。
書くもでもないと思いますが、つっこまれる前に。 > (1,5,i) 1<=i<=7 が解と２個以上共通するためには 1<=i<=9 でした。(;_;)
訂正です。 > 56789側に生成されているペアの数は ２成分にわかれているわけではないのでこの書き方はまずかったですね。 ペア (i,j) と (j,i) を別物として数えたとしてのペアの総数は x*(x-1) + (n-x)*(n-x-1) 以上で、別物としなければその半分 なのでペアの個数は (x*(x-1) + (n-x)*(n-x-1))/2 以上。 と書くべきでした。（値は変わりません）
> 後半（ｎ−ｘ）の部分は、一般には保証できていないのではないでしょうか。 n=9 の例で説明を続けます。 要素 1 と直接つながっていない例えば 5 をとってきます。 (1,5,i) 1<=i<=7 が解と２個以上共通するためには（1 と 5 は 直接つながっていないので）1 と i か 5 と i が直接つながって いなければいけません。1 の方から直接つながっている 1234 の ４個が提供されるので少なくとも残りの 56789 の５個 (= 9 - 4 = n - x) は 5 の方から提供されないといけません。事実 5 の 列を見ると 56789 が並んでいます。（9 の場合はさらにおまけの 34 がついた 3456789 が並んでいます） 5以外の 1 と直接つながっていない 6789 についても同様なので 56789側の縦の長さはすべて 5 (= 9 - 4 = n - x)以上になります。 よって 56789側に生成されているペアの数は少なくとも 5*4/2 = (n-x)*(n-x-1)/2 になります。 > 以下の５個から３個の場合のＮ＝１３の例でやってみていただけませんか？ まだやってませんが上記の話は「３個から２個以上」という制約を 使っての話なので「５個から３個以上」の場合にどうなるかはわか りません。
三吉さん、丁寧な解説ありがとうございました。 ＞Re: 簡易ロト問題、３個から２個以上 投稿者：三吉 投稿日：03月04日(金)04時25分28秒 ＞n=9 の連結成分１個の解 {123,124,349,567,589,689,789} について ＞１行目に１〜９、その下に直接つながっている要素を縦に並べて ＞表に書いてみます。 ＞123456789 ＞211165553 ＞332277664 ＞444388875 ＞__9999996 ＞________7 ＞________8 ＞x というのはこの表の列（縦）の長さの最小値のことです。 ＞この例で言えば要素が 1 または 2 のとき最小値 4 をとります。 ＞例えば最小値 4 をとる要素 p として 1 の方を選べば（2 を ＞選んでも結果は同じですが）グループＡは 1 と直接つながって ＞いる 1234、グループＢは それ以外の 56789、ＡとＢは 9 を ＞通して連結しています。 ｘの理解がまるで、違っていました。しかし、この方法では、 以前に提示された式 「x*(x-1)/2 + (n-x)(n-x-1)/2 以上」の前半は理解できますが、 後半（ｎ−ｘ）の部分は、一般には保証できていないのではないでしょうか。 ｘ＋１〜ｎまでのｎ−ｘ個に関する任意のペアが存在することは言えてないと思います。 以下の５個から３個の場合のＮ＝１３の例でやってみていただけませんか？ ==== (13, 8, 3) ==== 1 2 3 4 5 6 7 8 9 a b c d --------------------------- s1 1 1 1 1 1 . . . . . . . . s2 1 1 1 . . 1 . . . . . . 1 s3 1 1 1 . . . 1 1 . . . . . s4 . . . 1 1 1 . 1 1 . . . . s5 . . . 1 1 . 1 . 1 . . . 1 s6 . . . . . 1 1 . . 1 1 1 . s7 . . . . . . . 1 . 1 1 1 1 s8 . . . . . . . . 1 1 1 1 1 もちろん、私もやりますが。
> (4) n = 2^h - 1の場合は nC2/3個の組から重複なく nC2個のペアを > 生成できるだろう。 が解決しました。 a と b の排他的論理和が c となるような組 (a,b,c) すべてからなる 集合から nC2個のペアが無駄なく生成できるようです。
n=9 の連結成分１個の解 {123,124,349,567,589,689,789} について １行目に１〜９、その下に直接つながっている要素を縦に並べて 表に書いてみます。 123456789 211165553 332277664 444388875 __9999996 ________7 ________8 x というのはこの表の列（縦）の長さの最小値のことです。 この例で言えば要素が 1 または 2 のとき最小値 4 をとります。 例えば最小値 4 をとる要素 p として 1 の方を選べば（2 を 選んでも結果は同じですが）グループＡは 1 と直接つながって いる 1234、グループＢは それ以外の 56789、ＡとＢは 9 を 通して連結しています。 以下、余談です。 この例では 9 でつながらないように解の中の組 349 を 234 などと 入れ替えれば 123456789 211165555 332277666 444388877 ____99998 となって 1234 と 5678 の２成分からなる解になります。 このように１成分の解を２成分の解に変形する方法がないかと 考えていますが思いつきません。