質問の線形代数の行列の問題を Ruby で

質問の線形代数の行列の問題をPythonで解いてみた。 - rscの日記
rsc さんが Python でやっているのを、Ruby でやってみました。

元の問題はこれです。自力では解けませんでした。組み合わせの数を劇的に減らすのがコツですね。

ans = []
target = [12, 20, 25, 32, 37]
(1..40).each do |x1|
  (x1..40).each do |x2|
    (x2..40).each do |x3|
      (x3..40).each do |x4|
        flag = Array.new(5, 0)
        target.each_with_index do |t, i|
          [-1, 0, 1].repeated_permutation(4) do |ar|
            flag[i] = 1 if t == x1 * ar[0] + x2 * ar[1] + x3 * ar[2] + x4 * ar[3]
          end 
        end
        ans << [x1, x2, x3, x4] if flag.inject(:+) == 5
      end
    end
  end
end
p ans
p ans.size

結果は

[[1, 2, 9, 26], [1, 2, 9, 31], [1, 2, 11, 23], …
 …  [28, 32, 33, 40], [28, 32, 35, 40], [28, 32, 37, 40]]
6304

という感じです。最後の 6304 は解の個数です。

かかった時間は僕の環境で17秒ほどでした。
なお、メソッド Array#repeated_permutation(n) は、試行錯誤の過程で見つけたものです。重複順列を与えます。