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

前回の記事の要約:

N未満の非負整数を乱数を使って重複なくM個選ぶ手続きがあり、これを実行したあとの乱数列のインデックスがある特定の値になるような、開始インデックスをすべて求めるプログラムを書けという問題。これは無事に解けた。
でも、当初のきっかけのバトルファクトリーのトレーナー決定は、14件中7件目と14件目の二つとそれ以外では違う決め方をするので、そのまま使えない。

バトルファクトリーのトレーナーへの応用は思っていた以上に難しいです。

まず前回のようにi≦j ⇒ i'≦j'というのも成り立ちません。これが成り立てば一個ずつさかのぼっていって与えた列が余るようになったところでループ終了とできたのですが。
その代わりいろいろ考えているうちに、jを決めたときi

定義 (RとSeg_k)

a..bを整数の集合{n: a≦n≦b}と定める。

Rを選択対象の数の集合を要素とする列とする。
Rのインデックスkの要素は、ランダムに選ぶk件目を決めるときの値の範囲を表す。

R = Seg_1 + ... + Seg_m と分割する。
ただし Seg_k = [r_k] * n_k, r_kは選択対象の集合 (k ∈ 1..m)であり、{r_k : k ∈ 1..m}の各元には重なりがない。

例1

今回の目的の場合、r = 0..98, r' = 100..118 とするとき R = [r,r,r,r,r,r,r',r,r,r,r,r,r,r']となる。
このときSeg_1 = [r] * 6, Seg_2 = [r'] * 1, Seg_3 = [r] * 6, Seg_4 = [r'] * 1としてR = Seg_1 + Seg_2 + Seg_3 + Seg_4となる。

i≦j ⇒ i'≦j'が成り立たない例

Rが14件では多すぎてこの例には向かないのでR = [r, r', r]で考える。
{rand[n]}を乱数列としrand[n]の値をもとにして決まるr, r'の範囲の値をそれぞれrand[n] % r, rand[n] % r'と書くことにして乱数列が以下のようになっている場合を考える。

n	0	1	2	3	4	5
rand[n] % r	-	a	b	a	a	b
rand[n] % r'	-	-	A	A	-	-

a, bはrに属する異なる数、Aはr'に属する数。どうでもいい場所は-で埋めた。
i=0とおくと決定列は[a, A, a, a, b]となりi' = 5
j=1とおくと決定列は[b, A, a]となりj' = 4

こんな表を書くのはめんどいので実際に調査していたときはこんな図を描いて済ませた:

定義 (s_k, t_k, EndOf)

i < jなる乱数列のインデックスi, jを任意にとり固定する。
iをそれぞれ開始地点とした決定列のうちSeg_kに関する部分をs_kとおく。
s_kの終わりが位置する乱数列のインデックスをEndOf(s_k)とする。

(決定列とは選択を実行したとき乱数列のその間に使われる部分のこと)

例2:
乱数列が表の通り与えられていて、このときのi=0の決定列を書いた。Rは例1と同じである。

EndOf(s_1) = 8, EndOf(s_2) = 9, EndOf(s_3) = 15, EndOf(s_4) = 16となる。

定義 (StepTake, M_k)

乱数列のインデックスpと選択対象の数の集合rと整数nについて、StepTake(p, r, n)をpを開始地点としてrの要素を重複なくn個選んだときの終了時インデックスとする。

後にEndOf(s_k)の上界となることを示す、M_kを定める。
　　M_0 = j
　　M_k = StepTake(M_{k-1}, r_k, N_k) (k ∈ 1..m)

ただしN_kはl∈1..k, r_l = r_kとなるようなすべてのlに対するn_lの総和とする。

例

上の例で出た14件のRで考える。
このときi'の上界となる(といいたい)M_mは次のようなインデックスになる。

インデックスjからスタートして
rで6件重複なく選んで
r'で1件重複なく選んで
rで12件重複なく選んで
r'で2件重複なく選んだ直後のインデックス。

この各ステップでは既出の値の共有はしない。

補題: 任意の乱数列のインデックスi, j (i≦j)についてStepTake(i, r, n)≦StepTake(j, r, n)

これは前回の記事でいったi≦j ⇒ i'≦j'のことである。

命題: EndOf(s_k) ≦ M_k (k∈1..m)

証明:
kについての帰納法で証明する。
k = 1のとき、EndOf(s_1) = StepTake(i, r_1, n_1), M_1 = StepTake(j, r_1, n_1)であり補題により成立。
k∈1..mをとり、k-1については成立しているとする。
M_kの定義から、乱数列のM_{k-1}+1からM_kまでにはr_kで見たとき異なるN_k個の値が含まれている。
s_{k-1}までで得られたr_kの要素N_{k-1}個を除いても少なくともn_k個ある。
また、帰納法の仮定からEndOf(s_{k-1}) ≦ M_{k-1}であった。

よってs_kの先頭からインデックスM_kまでの列には今までに出たことのない異なるn_k個のr_kの要素がある。ゆえにs_kはインデックスM_kに達するまでの間に終わっている。
つまりEndOf(s_k) ≦ M_kとなる。
よって示された。 □

プログラム

上界が目標のインデックスより小さくなった時点でループを終了すればいい。

r1 = 0..98
r2 = 100..118
Segments = [[r1, 6], [r2, 1], [r1, 6], [r2, 1]]
R = Segments.flat_map{|(r,n)| [r] * n }

# take_multiしたあとのインデックスがprng.iになるようなインデックスをすべて求める
def solve(prng)
  prng = prng.dup
  target = prng.i
  ret = []
  while true
    p = prng.dup
    take_multi(p, R)
    if p.i == target
      ret.push(prng.i) # 解を得た
    end
    if upper_bound(prng) < target # 上界が目標のインデックスより小さくなった
      break
    end
    prng.pred!
  end
  ret
end

# prng.i以下のすべてのインデックスについてそこからtake_multi(p, R)した後のインデックスが常に
# M以下となるようなMのひとつを求める
def upper_bound(prng)
  prng = prng.dup
  n_sum = Hash.new(0)
  Segments.each do |(r, n)|
    n_sum[r] += n
    take_multi(prng, [r] * n_sum[r])
  end
  prng.i
end

# ランダムな選択を実行する
def take_multi(prng, rs)
  list = []
  i = 0
  while i < rs.length
    v = prng.rand(rs[i])
    if not list.include?(v)
      list.push(v) 
      i += 1
    end
  end
  list
end

# 乱数生成機。現在のインデックスiを保持する
class PRNG
  def initialize(seed)
    @seed = seed
    @i = 0
  end

  attr_reader :seed, :i

  def rand(r)
    r = r.to_a
    r[rand_num(r.size)]
  end

  def rand_num(n)
    succ!
    get_value() % n
  end
  
  def succ!
    @seed = (@seed * 0x41c64e6d + 0x6073) & 0xffffffff
    @i += 1
  end

  def pred!
    @seed = (@seed * 0xeeb9eb65 + 0xa3561a1) & 0xffffffff
    @i -= 1
  end

  def get_value
    @seed >> 16
  end
end

雑感

説明や定義が足りていない部分がありますが、気が向けば直します。
また、このままでは効率が悪いのでもっと良い方法も気が向けば探します。

追記(2012/11/13): 前回の記事の要約、具体例と図を追加

追記 (2014/8/23)

1個seedを戻るたびに上界のチェックをするのは効率が悪いのでもっと良い方法を考えました。
たとえば記事に出てくるR=[r]*6+[r']+[r]*6+[r']の場合、最後のseedから乱数列を逆向きにして次のように選んでいきます:

r'で2件重複なく選ぶ
rで12件重複なく選ぶ
r'で1件重複なく選ぶ
rで6件重複なく選ぶ

この異なるステップ同士では既出の値の共有はしません。

こうしたときの乱数列のインデックスが、開始地点の下界になっています。