「もっとプログラム脳を鍛える数学パズル」_Q61 (code:Ruby) -> Rust (& SQL)

「もっとプログラマ脳を鍛える数学パズル」をRustで書き直すのは、ボケ防止にちょうど良いかもしれない、と思った。

Q61:互い違いに並べ替え

Ruby

q61_2.rb

N = 20

z = Hash.new(0)
z[[0,0]] = 1
1.upto(N) do |n|
    1.upto(N) do |k|
        z[[n,k]] = z[[n, k - 1]] + z[[n - 1, n - k]]
    end
end
puts 2 * z[[N, N]]

なんとなく、書籍p.287のコードは、RubyとJavaScriptで内側ループの範囲が違ってませんかね・・・Rubyでは正しい結果が出てますが、たまたま0で初期化してるからではないか。

Rust

main.rs

fn main() {
    println!("{}", q61());
}

pub fn q61() -> i64 {
    let mut z = [[0i64; 21]; 21];
    z[0][0] = 1;
    for n in 1..=20 {
        for k in 1..=n {
            let un = n as usize;
            let uk = k as usize;
            z[un][uk] = z[un][uk - 1] + z[un - 1][un - uk];
        }
    }
    return z[20][20] * 2;
}

配列のサイズを変数指定できないので、とりあえずベタうち。
Rustは何かあるとpanickedになるのがむしろありがたい。パズルを解いていると、境界値を認識していてくれるのは安心できる。

SQL

ところで、数学パズルでは「パターンは何件あるか」という問題に対して数学的に答える問題が多い。実際の業務では、パターン数計算は見積りには使えても、「いや私は展開されたパターン自体が欲しいんですけど」という状況の方が多い。一番の理由は「テストデータを作りたい」といったところか。
本問の"交代順列"も、もしかしたらテストデータ作成に役立つかも、ということで、SQL版を書いた。

q61.sql

SELECT
    *
FROM
    (SELECT 1 AS v UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4) AS c1,
    (SELECT 1 AS v UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4) AS c2,
    (SELECT 1 AS v UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4) AS c3,
    (SELECT 1 AS v UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4) AS c4
WHERE
    (c1.v <> c2.v AND c1.v <> c3.v AND c1.v <> c4.v) AND
    (c2.v <> c3.v AND c2.v <> c4.v) AND
    (c3.v <> c4.v)
    AND (
    (c1.v < c2.v AND c2.v > c3.v AND c3.v < c4.v) OR
    (c1.v > c2.v AND c2.v < c3.v AND c3.v > c4.v))

実行するとこんな感じ。

+---+---+---+---+
| v | v | v | v |
+---+---+---+---+
| 4 | 2 | 3 | 1 |
| 3 | 2 | 4 | 1 |
| 3 | 4 | 1 | 2 |
| 4 | 1 | 3 | 2 |
| 3 | 1 | 4 | 2 |
| 2 | 4 | 1 | 3 |
| 1 | 4 | 2 | 3 |
| 2 | 1 | 4 | 3 |
| 2 | 3 | 1 | 4 |
| 1 | 3 | 2 | 4 |
+---+---+---+---+
10 rows in set (0.00 sec)

SQLは集合論で考えられるので、「ありうる集合から、条件に一致する要素を抽出する」という極めて単純な考え方でデータが取り出せる。