重複なしにランダムに選んだ後ある特定のseed値になるようなseed値を求める

問題

次のようなN未満の非負整数を重複なくM個選ぶ手続きを考える。
擬似乱数は線形合同法とする。つまり現在のseed値(=乱数生成機の状態変数)からひとつ前のseed値がわかることを前提とする。
def take()
  list = []
  while list.length < M
    v = rand(N)
    if not list.include?(v)
      list.push(v)
    end
  end
  list
end
今、あるseed値Aが与えられているとする。
take()を実行する前のseed値がsであり、実行した後のseed値がAであるようなsをすべて求めるようなプログラムを作れ。

この問題はバトルファクトリーのツールを作っているときに実際に出会いました。そのときはM=7であり、Aの7個前のseedでtake()したらAになるか調べる、Aの8個前のseedを調べる、…と続けてAの50個前まで調べたらそこで終わるという手抜きで済ませていました。実際にすべての場合においてtake()の消費数が50個以下だと確認済みならばそれでもOKですがそれもしていませんでした。

観察

数学ガール乱択アルゴリズムという本にサイコロをすべての目が出るまで振るとき、平均何回振ればよいかという話題が取り上げられていました。そこに《幸せの階段》という図があります。

(これは筆者が模写したもの)

左から出た目を順番に描いていき、今まで出たことがない目が出るたびに段数があがって6段まできたら終了というものです。

これを参考にM=3の場合の《幸せの階段》を描いてみるとこんなふうになります。

決定列となる条件

定義：

N未満の非負整数を要素とする有限列rに対して、rが決定列であるとは、rを乱数列として与えてtake()を実行したとき過不足なくちょうどrの長さ分消費して終わることと定めます。
rを乱数列として与えてtake()を実行というのは、take()の中のrand(N)の代わりに、rの要素を先頭から順番に取り出し実行することをいいます。

このとき、rが決定列であるための必要十分条件は「rに現れる数全体がM個であり、rの末尾の数はrの中ではそこにしか現れない」となります。
(rに現れる数全体の個数というのは重複を除いた個数とする)

プログラム

求める解sの条件は、次のようなnが存在することである：

sをseedとしてn個からなる乱数列rを得たとき、終了時seedがAで、rが決定列である

ここから、「Aを終わりとするn個の乱数列が決定列であるようなすべてのnに対してAのn個前のseedを集めたもの」が解の全体となることが従います。

よって与えられたnに対して、Aを終わりとするn個の乱数列rが決定列であるかどうかを考えればよいです。
nによって「rに現れる数全体の個数」は単調増加であること、そして決定列となる条件から、nをひとつずつ増やして調べればいいことがわかります。

def solve(a)
  n = 0
  list = []
  s = a
  while true
    v = seed_to_rand_value(s, N)
    s = prev_seed(s)
    n += 1
    list.unshift(v) # listの先頭にvを挿入

    # ここでsはaのn個前のseed値に、listは終了seedをaとするn個の乱数列になっている
    if list.length >= 2 and v == list.last # 末尾の数が再び現れたら終了
      return
    end
    if count_items(list) == M
      print(s) # 解sを出力する
    end
    if count_items(list) > M # listに現れる数全体の個数がMを超えたら終了
      return
    end
  end
end

(seed_to_rand_value, prev_seed, count_itemsは名前から自然に想像できる通りの意味とする)

追記: プログラムを微修正 (2012/11/11)

追記(2012/11/11) 上では書かなかったことのメモ

バトルファクトリーでは実際には14件選ぶのだが、そのうち7件目と14件目の二つとそれ以外では違う決め方をする。だからもう一ひねりする必要があるだろう
列rを乱数列として与えたときの決定列は、rの始切片r'であり、r'に現れる数全体がM個であるもののうち長さが最小のものである。これが決定列となる必要十分条件の根拠になる。(rの始切片というのはrの先頭から途中まであるいは末尾までを取り出した列のことをいいたかったのだがぐぐってみてもこの意味での使われ方は見られない…）
乱数列のi番目, j番目を現在位置にしてtake()した後の乱数列の位置をそれぞれi'、j'とするとi ≦ jならばi' ≦ j'である (上の事実から従う)
予想: 乱数列のi番目, i+1番目をそれぞれ現在位置にして、take()を実行―ただしループ終了条件をlist.length >= Mではなく乱数列の位置がjになったときと変える―したときの結果listをそれぞれl, l'とするとl = [a] + l'.remove(a) (aはlの先頭要素)が成立している(ただしl'.remove(a)はl'からaと等しい要素を取り除いた列とする)。これはsolve()でsだけでなくtake()の結果も出力したいときに役立つだろう(実際にすべての解sについてtake()を実行する必要がなくなる)