151123

Ruby


Dyck path とSelf-avoiding walk の融合(1)

原点(0, 0) から点(i, j) への最短経路で対角線を超えないものを
i x j 格子点上のDyck path といい、その個数をC(i, j) と書く。
一般に、
C(mn, n) = binomial((m + 1)n, n) / (mn + 1)
が成り立つ。

# -*- coding: cp932 -*-

move0 = [[1, 0], [0, 1]]
move1 = [[1, 0], [-1, 0], [0, 1]]
move2 = [[1, 0], [0, 1], [0, -1]]
move3 = [[1, 0], [-1, 0], [0, 1], [0, -1]]

# startがx, y、goalがmn, n
def search(move, x, y, m, n, used)
  return 0 if x < 0 || m * n + 1 <= x || y < 0 || m * y > x || used[x + y * (m * n + 1)]
  return 1 if x == m * n && y == n
  cnt = 0
  used[x + y * (m * n + 1)] = true
  move.each{|mo|
    cnt += search(move, x + mo[0], y + mo[1], m, n, used)
  }
  used[x + y * (m * n + 1)] = false
  return cnt
end

M = 3
N = 10
[move0].each{|move|
  puts "move = #{move}のとき"
  (0..M).each{|m|
    puts "m = #{m}のとき"
    (0..N).each{|n|
      used = Array.new((m * n + 1) * (n + 1), false)
      p search(move, 0, 0, m, n, used)
    }
  }
}

出力結果
move = [[1, 0], [0, 1]]のとき
m = 0のとき
1
1
1
1
1
1
1
1
1
1
1
m = 1のとき
1
1
2
5
14
42
132
429
1430
4862
16796
m = 2のとき
1
1
3
12
55
273
1428
7752
43263
246675
1430715
m = 3のとき
1
1
4
22
140
969
7084
53820
420732
3362260
27343888