場合の数でループする

.groovy

inamori 氏の ある確率 - 桃の天然水 を実装してみた*1。

8つのコップがあって、ボールをランダムに16個コップに入れる。
そのとき全てのコップに2個ずつボールが入る確率は？

ボールを入れるコップでループする

どのコップに入れたかで処理すると 8^16 回処理しないといけないので返ってこない

// 実行しても返ってこないので注意
count = 0L
def rec0(int ball, int[] cup) {
  if (ball == 0) {
    count++
    return
  }
  for (i in 0..<cup.size()) {
    // ball がコップに 2 つ以上ある場合は枝刈り
    if (cup[i] < 2) {
      cup[i]++
      rec0(ball-1, cup)
      cup[i]--
    }
  }
}

int[] cup = new int[8]
rec0(16, cup)
println count
ボールの数の組合せでループ
all2  = 0L  // すべてのコップにボールが 2 個ずつ入る場合の数
total = 0L  // 全体の数

def rec1(int ball, int[] comb, long n) {
  if (ball == 0) {
    if (comb[2] == 8) all2 += n
    total += n
    return
  }
  for (i in 0..<comb.size()) {
    // コップのボールは 1 個ずつしか増えない
    def c = comb[i]
    if (c > 0) {
      comb[i]--
      comb[i+1]++
      rec1(ball-1, comb, n*c)
      comb[i+1]--
      comb[i]++
    }
  }
}

// 最初はボールが 0 個のコップが 8 つ
rec1(16, [8]+[0]*16 as int[], 1L)

nf = java.text.NumberFormat.percentInstance
nf.minimumFractionDigits = 3
println "$all2 / $total = ${nf.format(all2/total)}"

場合の数で再帰すると結果が返ってくる。
4つ目のコップまで手計算で樹形図を書いてみたがすぐに書けた。
ちょっとした違いなんだけど効果がすごい。

81729648000 / 281474976710656 = 0.029%

16! / 2^8 / 8^16 で多分あっている

もう一つの問題

8つのコップがあり8人がボールを2つずつその中に入れる。
ただし、一人が同じコップに2つボールを入れてはいけない。
そのとき全てのコップに2個ずつボールが入る確率は？

all2  = 0L  // すべてのコップにボールが 2 個ずつ入る場合の数
total = 0L  // 全体の数

def rec2(int ball, int[] comb, long n, int prev) {
  if (ball == 0) {
    if (comb[2] == 8) all2 += n
    total += n
    return
  }
  for (i in 0..<comb.size()) {
    def c = comb[i]
    // 同じコップに2つボールを入れてはいけない
    if (i == prev && ball % 2 != 0) c--
    // コップのボールは 1 個ずつしか増えない
    if (c > 0) {
      comb[i]--
      comb[i+1]++
      rec2(ball-1, comb, n*c, i+1)
      comb[i+1]--
      comb[i]++
    }
  }
}

// 最初はボールが 0 個のコップが 8 つ
rec2(16, [8]+[0]*8 as int[], 1L, -1)

def nf = java.text.NumberFormat.percentInstance
nf.minimumFractionDigits = 3
println "$all2 / $total = ${nf.format(all2/total)}"

先程のコードに2個目のボールの条件を1行追加した。
引数も変更したがほぼそれだけ。

48007895040 / 96717311574016 = 0.050%

連続して入れない場合 = すべての場合 - 連続して入れた場合 だが式がたてられなかった。
でも答えと一致したのであっていると思う。

*1:配列を使ったけど