あみだくじの横線（Ruby）

アルゴリズム・パズルです。

問題：
1 ~ 7 の数字を並べてあみだくじを作ることを考えます。引く横線の数を 10本とするとき、下に得られる数字の並びは何とおりになるでしょうか。ただし、下に得られる数字の並びが 10本より少ない横線のあみだくじで既に得られる場合、それは除くことにします。

　
Ruby で解いてみました。
q57.rb

require 'set'

N = 7
List = "1234567"

def exchange(i, ls, num)
  ls[i], ls[i + 1] = ls[i + 1], ls[i]
  if num == 10
    @result << ls
  else
    @store << ls
    (N - 1).times do |j|
      next if i == j
      exchange(j, ls.dup, num + 1)
    end
  end
end

@store = Set[List]
@result = Set.new
(N - 1).times {|i| exchange(i, List.dup, 1)}
puts (@result - @store).size    #=>573

答えはいちおう 573通りと求められたのですが、時間が約 16秒もかかってしまいました。exchange() の呼び出しは 14648436回もあります。力任せのやり方で、これではダメですね。

模範解答の一。

v, h = 7, 10
total = 0

[*0..v - 1].permutation do |final|
  cnt = 0
  v.times do |i|
    cnt += final.take_while {|j| j != i}.count {|k| k > i}
  end
  total += 1 if cnt == h
end
puts total