2026-09-28
models.rs
fn models(n: u32, clauses: &[Vec<i32>]) -> impl Iterator<Item = u32> {
}
変数 n 個の CNF の論理式 clauses を満たす割り当てを、すべて順に返す models を書いてください。割り当ては u32 の値 m で表し、変数 xk(k は 1 から n)の値を m の k - 1 ビット目とします。節 clauses[i] の要素 k は xk を、-k はその否定を表し、節の中のどれか1つが真ならその節は真です。m の小さい順に、Vec に集めずイテレータのまま返します。n は 31 以下とします。collect した結果で、models(2, &[vec![1, 2]]) → [1, 2, 3]、models(2, &[vec![1], vec![-1]]) → []、models(0, &[]) → [0]
Reference
fn models(n: u32, clauses: &[Vec<i32>]) -> impl Iterator<Item = u32> {
(0..1 << n).filter(|&m| {
clauses.iter().all(|clause| {
clause
.iter()
.any(|&lit| ((m >> (lit.unsigned_abs() - 1)) & 1 == 1) == (lit > 0))
})
})
}
0..1 << n が 2n 通りの割り当てを小さい順に並べ、filter が式を満たすものだけを残します。filter は要素を取り出されるたびに1つずつ調べるだけなので、全体をメモリに並べることはありません。変数のない models(0, &[]) は 0 だけを試し、節が1つもない式は常に真なので [0] になります。
返す値の型は Filter<Range<u32>, クロージャ> で、クロージャの型には名前がないので書けません。そこで impl Iterator<Item = u32> として返します。このクロージャは clauses の指す先を読むので、返したイテレータは引数のスライスを借りたままです。Rust 2024 では、戻り値の位置の impl Trait は関数のライフタイム引数をすべて自動でキャプチャするので、このシグネチャのままコンパイルが通ります。Rust 2021 edition までは同じコードが「隠れた型がライフタイムをキャプチャしている」というエラーになり、+ '_ を書き足す必要がありました。
クロージャが使うのは *clauses と自分の引数の m だけです。*clauses は呼び出し元が持つスライスなので、クロージャはそれを直接借ります。クロージャの中で n も読むなら、n は関数が返った時点で消えるローカル変数なので、move を付けてコピーさせないとコンパイルが通りません。
掲載したのは参考実装で、唯一の正解ではありません。1 << n は n が 32 になると u32 からあふれるので、n を 31 以下としています。