Namaran

Code daily. Without assist.

2026-09-28

count_models.rs

fn satisfies(clauses: &[Vec<i32>], assign: &[bool]) -> bool {
    clauses.iter().all(|clause| {
        clause
            .iter()
            .all(|&lit| assign[lit.unsigned_abs() as usize - 1] == (lit > 0))
    })
}

fn count_models(n: usize, clauses: &[Vec<i32>]) -> usize {
    (0..1u32 << n)
        .filter(|m| {
            let assign: Vec<bool> = (0..n).map(|i| (m >> i) & 1 == 1).collect();
            satisfies(clauses, &assign)
        })
        .count()
}

CNF の論理式を満たす割り当ての個数を、すべての割り当てを試して数える count_models です。節は整数のリストで、k は変数 xk を、-k はその否定を表します。count_models(3, &[vec![1, 2], vec![-1, 3]]) を出力すると、いまは 0 ですが、本来は 4 です。どこを直せばよいでしょうか?

Answer

satisfies の内側の .all(|&lit| …) を .any(|&lit| …) に変えます。

CNF は節の論理積で、1つの節はリテラルの論理和です。外側の all は「すべての節が真」を正しく調べていますが、内側も all なので、節の中のリテラルがすべて真であることまで求めています。その結果、節 [1, 2] は x1 と x2 の両方が真、節 [-1, 3] は x1 が偽であることを要求し、x1 について矛盾するので、どの割り当ても通りません。

内側を any にすると、節の中のどれか1つが真なら節が真になります。x1 が偽なら最初の節のために x2 が真で、x3 はどちらでもよいので2通り、x1 が真なら2番目の節のために x3 が真で、x2 はどちらでもよいので2通りです。合わせて 4 になります。