151122(2)

Ruby


直角二等辺三角形の形をした領域内のSelf-avoiding walk(3)

進むパターンを増やし、さらに分布も調べてみた。

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の座標の和がn - 1
def search(move, x, y, n, used)
  ary0 = Array.new(n, 0)
  return ary0 if x < 0 || n <= x || y < 0 || n <= y || used[x + y * n]
  if x + y == n - 1
    ary0[x] = 1
    return ary0
  end
  c_ary = Array.new(n, 0)
  used[x + y * n] = true
  move.each{|m|
    ary1 = search(move, x + m[0], y + m[1], n, used)
    c_ary = (0..n - 1).map{|i| c_ary[i] + ary1[i]}
  }
  used[x + y * n] = false
  return c_ary
end

# move2のとき規則性は簡単
def search_move2(n)
  ary = [1, n - 1, (n - 2) * (n - 2)]
  if n > 3
    n0 = (1..n - 2).inject(:*)
    ary += (1..n - 4).map{|i| n0 * (i + 1) / (1..i).inject(:*)}.reverse + [n0]
  end
  ary[0..n - 1]
end

# move1のときも規則性は簡単
def search_move1(n)
  search_move2(n).reverse
end

N = 10
[move0, move1, move2, move3].each{|move|
  (1..N).each{|n|
    used = Array.new(n * n, false)
    a_ary = search(move, 0, 0, n, used)
    p [a_ary.inject(:+), a_ary]
  }
}

(1..N).each{|n|
  p search_move1(n)
}

(1..N).each{|n|
  p search_move2(n)
}

出力結果
[1, [1]]
[2, [1, 1]]
[4, [1, 2, 1]]
[8, [1, 3, 3, 1]]
[16, [1, 4, 6, 4, 1]]
[32, [1, 5, 10, 10, 5, 1]]
[64, [1, 6, 15, 20, 15, 6, 1]]
[128, [1, 7, 21, 35, 35, 21, 7, 1]]
[256, [1, 8, 28, 56, 70, 56, 28, 8, 1]]
[512, [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]
[1, [1]]
[2, [1, 1]]
[4, [1, 2, 1]]
[10, [2, 4, 3, 1]]
[32, [6, 12, 9, 4, 1]]
[130, [24, 48, 36, 16, 5, 1]]
[652, [120, 240, 180, 80, 25, 6, 1]]
[3914, [720, 1440, 1080, 480, 150, 36, 7, 1]]
[27400, [5040, 10080, 7560, 3360, 1050, 252, 49, 8, 1]]
[219202, [40320, 80640, 60480, 26880, 8400, 2016, 392, 64, 9, 1]]
[1, [1]]
[2, [1, 1]]
[4, [1, 2, 1]]
[10, [1, 3, 4, 2]]
[32, [1, 4, 9, 12, 6]]
[130, [1, 5, 16, 36, 48, 24]]
[652, [1, 6, 25, 80, 180, 240, 120]]
[3914, [1, 7, 36, 150, 480, 1080, 1440, 720]]
[27400, [1, 8, 49, 252, 1050, 3360, 7560, 10080, 5040]]
[219202, [1, 9, 64, 392, 2016, 8400, 26880, 60480, 80640, 40320]]
[1, [1]]
[2, [1, 1]]
[4, [1, 2, 1]]
[12, [2, 4, 4, 2]]
[48, [6, 12, 12, 12, 6]]
[288, [30, 60, 54, 54, 60, 30]]
[2768, [254, 508, 438, 368, 438, 508, 254]]
[45408, [3750, 7500, 6484, 4970, 4970, 6484, 7500, 3750]]
[1289000, [96834, 193668, 168712, 128582, 113408, 128582, 168712, 193668, 96834]]
[63234984, [4365698, 8731396, 7629762, 5878060, 5012576, 5012576, 5878060, 7629762, 8731396, 4365698]]
[1]
[1, 1]
[1, 2, 1]
[2, 4, 3, 1]
[6, 12, 9, 4, 1]
[24, 48, 36, 16, 5, 1]
[120, 240, 180, 80, 25, 6, 1]
[720, 1440, 1080, 480, 150, 36, 7, 1]
[5040, 10080, 7560, 3360, 1050, 252, 49, 8, 1]
[40320, 80640, 60480, 26880, 8400, 2016, 392, 64, 9, 1]
[1]
[1, 1]
[1, 2, 1]
[1, 3, 4, 2]
[1, 4, 9, 12, 6]
[1, 5, 16, 36, 48, 24]
[1, 6, 25, 80, 180, 240, 120]
[1, 7, 36, 150, 480, 1080, 1440, 720]
[1, 8, 49, 252, 1050, 3360, 7560, 10080, 5040]
[1, 9, 64, 392, 2016, 8400, 26880, 60480, 80640, 40320]