150503(2)

Ruby


3 6 9 2 5 8 1 4 7 (2)

１からNまでのN個の整数で、
　１）隣り合う２数の差はD以上、１個おいた数との差もD以上、… 、

　　　D - 2個おいた数との差もD以上　
という条件を満たす順列を考える。
D、Nが与えられたとき、条件を満たす順列の個数を求める。

N = 11
D1 = 4

def check1(d, a, i)
  return true if i == 0
  j = 1
  d_max = [i, d - 1].min
  while (a[i] - a[i - j]).abs >= d && j < d_max
    j += 1
  end
  (a[i] - a[i - j]).abs >= d
end

def solve1(d, len, a = [])
  b = []
  if a.size == len
    b << a
  else
    (1..len).each{|m|
      s = a.size
      if s == 0 || (s > 0 && !a.include?(m))
        if check1(d, a + [m], s)
          b += solve1(d, len, a + [m])
        end
      end
    }
  end
  b
end

(2..D1).each{|d1|
  (d1..N).each{|b|
    p [d1, b, solve1(d1, b).size]
  }
}

出力結果
[2, 2, 0]
[2, 3, 0]
[2, 4, 2]
[2, 5, 14]
[2, 6, 90]
[2, 7, 646]
[2, 8, 5242]
[2, 9, 47622]
[2, 10, 479306]
[2, 11, 5296790]
[3, 3, 0]
[3, 4, 0]
[3, 5, 0]
[3, 6, 0]
[3, 7, 0]
[3, 8, 0]
[3, 9, 2]
[3, 10, 40]
[3, 11, 792]
[4, 4, 0]
[4, 5, 0]
[4, 6, 0]
[4, 7, 0]
[4, 8, 0]
[4, 9, 0]
[4, 10, 0]
[4, 11, 0]

１からNまでのN個の整数で、
　２）D - 2個おいた数との差がD以外
という条件を満たす順列を考える。

D、Nが与えられたとき、条件を満たす順列の個数を求める。

N = 11
D2 = 3

def check2(d, a, i)
  return true if i < d
  !((a[i] - a[i - d]).abs == d)
end

def solve2(d, len, a = [])
  b = []
  if a.size == len
    b << a
  else
    (1..len).each{|m|
      s = a.size
      if s == 0 || (s > 0 && !a.include?(m))
        if check2(d, a + [m], s)
          b += solve2(d, len, a + [m])
        end
      end
    }
  end
  b
end

(1..D2).each{|d2|
  (1..N).each{|b|
    p [d2, b, solve2(d2, b).size]
  }
}

出力結果
[1, 1, 1]
[1, 2, 0]
[1, 3, 0]
[1, 4, 2]
[1, 5, 14]
[1, 6, 90]
[1, 7, 646]
[1, 8, 5242]
[1, 9, 47622]
[1, 10, 479306]
[1, 11, 5296790]
[2, 1, 1]
[2, 2, 2]
[2, 3, 4]
[2, 4, 16]
[2, 5, 44]
[2, 6, 200]
[2, 7, 1288]
[2, 8, 9512]
[2, 9, 78652]
[2, 10, 744360]
[2, 11, 7867148]
[3, 1, 1]
[3, 2, 2]
[3, 3, 6]
[3, 4, 20]
[3, 5, 80]
[3, 6, 384]
[3, 7, 2240]
[3, 8, 15424]
[3, 9, 123456]
[3, 10, 1110928]
[3, 11, 11287232]

赤の部分が一致するのは、明らかだろう。

また、
条件２）を満たす順列の個数は
1 ≦ i ≦ N - D に対し、| σ(i + D) - σ(D) | ≠ D を満たすσの個数　…①

と言い換えられる。

①についてシグマで表された式がある。

（http://www.kurims.kyoto-u.ac.jp/EMIS/journals/INTEGERS/papers/g11/g11.pdf）

よって、条件２）を満たす順列の個数についてシグマで表された式があると言える。