151123(3)

Ruby


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

原点(0, 0) から点(i, j) への最短経路で対角線を超えないものが
i x j 格子点上のDyck path であったが、
y 軸方向だけ逆方向も進めるが、自身が通った点は通れないとしてみる。

この条件を満たす経路の個数をE(i, j) と書く。
このとき、
E(mn, n) = (n!)^m
ちなみに、
D(n, n) = E(n, n) = n!
となっているが、これは対称性より明らか。

# -*- 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 = 7
[move2].each{|move|
  puts "move = #{move}のとき"
  (0..M).each{|m|
    puts "m = #{m}のとき"
    (0..N).each{|n|
      # 実行時間の都合上
      break if m > 2 && n > 5
      used = Array.new((m * n + 1) * (n + 1), false)
      p search(move, 0, 0, m, n, used)
    }
  }
}

出力結果
move = [[1, 0], [0, 1], [0, -1]]のとき
m = 0のとき
1
1
1
1
1
1
1
1
m = 1のとき
1
1
2
6
24
120
720
5040
m = 2のとき
1
1
4
36
576
14400
518400
25401600
m = 3のとき
1
1
8
216
13824
1728000