次の問題を考えています。
(http://www004.upp.so-net.ne.jp/s_honma/mathbun/mathbun113.htm)
1からNまでのN個の整数で、
ア)隣り合う2数の差は3以上、1つおいた数との差も3以上
という条件を満たす順列は、何通りあるだろうか?
ただし、順番を逆にしたものもそれぞれ1つずつ数えるものとします。
(より一般的には次のような問題です。
1からNまでのN個の整数で、
イ)隣り合う2数の差はD以上、1個おいた数との差もD以上、… 、D - 2個おいた数との差もD以上
という条件を満たす順列は、何通りあるだろうか?
例えば、N = 9、D = 3 のとき、
[3, 6, 9, 2, 5, 8, 1, 4, 7]
[7, 4, 1, 8, 5, 2, 9, 6, 3]
の2通りあります。)
この問題の答えを速く求めるコードを考えてください。
以下、答えを求めるのが大変遅いコードです。
N = 11
D = 3
def check(a, i)
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
(D..N).each{|n|
cnt = 0
(1..n).to_a.permutation{|a|
i = 1
while check(a, i) && i < n - 1
i += 1
end
if check(a, i)
cnt += 1
end
}
p [n, cnt]
}
出力結果
[3, 0]
[4, 0]
[5, 0]
[6, 0]
[7, 0]
[8, 0]
[9, 2]
[10, 40]
[11, 792]
(追記)
D = 3 のとき、N = 12 までならすぐ求まるコードを
回答に載せました。
permutation
は枝刈りが出来ないので自前で並べ替えるべきかと思います。