全ての選出と交換に渡る全ての敵の組み合わせを計算その6

長い間放置していたけれど久しぶりに手をつけました。だいぶ忘れているのでまずはどういう状況だったか振り返るところから。

復習メモ:

敵の手持ちを1体1体決めていくわけだが、プレイヤーの手持ちと衝突するかどうかが問題になる。プレイヤーの手持ちは未確定なのでそこで枝分かれが生じる。
枝分かれにおいてskip→skip→skip→…を繰り返す場合がとりあえず最初の問題となりそう。衝突判定がIDだけによる場合は、surely_playersがたまっていってそのループは必ず終わるので問題は起きなかったのだが。

とりあえず1戦だけを考えてprev_enemyもmaybe_playersも無視して考えることにしました。
シンプルにいくと次のようなプログラムになります。これは上で言ったような無限再帰でうまく動きません。

def predict0(prng, skipped, chosen)
  if chosen.length == nParty
    return Set.new([chosen])
  end
  prngp, x = choose_entry(prng)
  if x.collides_within?(chosen)
    # 既に採用済みの場合
    predict0(prngp, skipped, chosen)
  elsif skipped.include?(x)
    # まったく同じエントリをスキップしたことがある場合
    predict0(prngp, skipped, chosen)
  else
    result1 = predict0(prngp, skipped, chosen + [x])
    result2 = predict0(prngp, skipped + [x], chosen)
    result1 + result2
  end
end

ためしに問題を明確化してみる：

エントリーと呼ばれる物の有限集合Eが定められているとする。各エントリーには"アイテム"と"種族"という二つの属性が定められている。
二つのエントリーa, bに対して、この二つが"衝突する"とはアイテムが一致するか種族が一致するかの少なくとも一方が成立することとする。

エントリーの無限列を乱数列と呼ぶことにする。ただし、乱数列は以下の条件を満たす：
　　乱数列の先頭から有限個取り除いても、残りの列にはすべてのエントリーが登場する。

乱数列が一つ与えられているとする。
そして、あらかじめplayersという互いに衝突しないn個のエントリーの集合が決まっているとする。
ここでplayersと衝突せず、互いに衝突のないn個のエントリーenemyを乱数列から決定する。 (*)
playersの中身は伏せられているものとして、enemyの可能性をすべて出力せよ。

以下のことを認めていいものとする。
2nより小さい整数kについて、k個の互いに衝突しないエントリーを勝手に選んだとき、それらのどれとも衝突しないエントリーが存在する。 (**)

(*) ただし決定の方法は次のごく当たり前のものとする: 乱数列の先頭から順に読んでいき、playersや既に採用済みのエントリーと衝突するものはスキップ、そうでないものは採用する、というのを繰り返す。

乱数列の定義で示した条件と、最後の条件(**)から、すべてのplayersの可能性を試すしらみつぶしの方法がうまく停止することがいえます。