150502

Ruby


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

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

　　　D - 2個おいた数との差もD以上　
という条件を満たす順列を考える。

Dを固定したとき、条件を満たす順列が存在するための最小のNはいくつだろうか？

また、このとき条件を満たす順列はどんなものだろうか？

（http://www004.upp.so-net.ne.jp/s_honma/mathbun/mathbun113.htm）

def check(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 solve(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 check(d, a + [m], s)

          b += solve(d, len, a + [m])

        end

      end

    }

  end

  b

end

# Dを固定したとき、条件を満たす順列が存在するための最小のN

(2..5).each{|d|

  n = d

  while solve(d, n).size == 0

    n += 1

  end

  p n

  p solve(d, n)

}

出力結果

4

[[2, 4, 1, 3], [3, 1, 4, 2]]

9

[[3, 6, 9, 2, 5, 8, 1, 4, 7], [7, 4, 1, 8, 5, 2, 9, 6, 3]]

16

[[4, 8, 12, 16, 3, 7, 11, 15, 2, 6, 10, 14, 1, 5, 9, 13], [13, 9, 5, 1, 14, 10,

6, 2, 15, 11, 7, 3, 16, 12, 8, 4]]

25

[[5, 10, 15, 20, 25, 4, 9, 14, 19, 24, 3, 8, 13, 18, 23, 2, 7, 12, 17, 22, 1, 6,

 11, 16, 21], [21, 16, 11, 6, 1, 22, 17, 12, 7, 2, 23, 18, 13, 8, 3, 24, 19, 14,

 9, 4, 25, 20, 15, 10, 5]]