92842


Rustで重複のないソート済みの整数ベクタが与えられたとして、  
その中に絶対値が同じ整数のペアが存在するか？という関数を書きたいです。  
この関数をis_tautology関数と呼ぶことにします。

rubyで効率気にせず書くと以下のような感じです。

[code]

    def is_tautology(clause)
        return clause.any?{|literal| clause.include?(-literal)}
    end
    
    v=
    [
    [1,2,3],
    [-2,-1,1,3],
    [-4,-3,-1,2],
    [-10,-5,1,2,3,4,5,6,7]
    ]
    
    v.each{|clause|
        print("#{clause} #{is_tautology(clause)}\n")
    }
    
    
[/code]

効率を気にしてC++で書くと以下のような感じです。

[code]

    #include<iostream>
    #include<vector>
    
    bool is_tautology(std::vector<int> &clause)
    {
        std::vector<int>::const_iterator begin,end;
        begin=clause.begin();
        end=clause.end();
        if(begin==end)
        {
            return false;
        }
        --end;
        while(*begin<0 && *end > 0)
        {
            if(-*begin<*end)
            {
                --end;
            }
            else if(-*begin>*end)
            {
                ++begin;
            }
            else
            {
                return true;
            }
        }
        return false;
    }
        
    int main()
    {
        std::vector<std::vector<int> > v=
        {
            {1,2,3},
            {-2,-1,1,3},
            {-4,-3,-1,2},
            {-10,-5,1,2,3,4,5,6,7}
        };
        
        for(auto clause:v)
        {
            std::cout<<is_tautology(clause)<<std::endl;
        }
    }
    
[/code]

Rustで効率の良いis_tautology関数を書こうとしたのですが、  
イテレータを用意してnextの値をとってNone判定して、、、  
とやろうとしたらなんだかとても煩雑になりそうになって手が止まってしまいました。

Rustでもすっきりとした字面でis_tautology関数を書くことはできるのでしょうか？


CC BY-SA 4.0
2022-12-17T12:23:41.683
92841
2022-12-17T23:17:24.437
2022-12-17T12:57:16.807
19110
18637
question
rust
Clauseのtautology判定


> Rustで効率の良いis_tautology関数を書こうとしたのですが、  
>  イテレータを用意してnextの値をとってNone判定して、、、  
>  とやろうとしたらなんだかとても煩雑になりそうになって手が止まってしまいました。
>
> Rustでもすっきりとした字面でis_tautology関数を書くことはできるのでしょうか？

その通りにやってみたところ以下のようになりました。個人的には十分すっきりとした字面で書けたように思えますが、いかがでしょうか？

[code]

    fn is_tautology(clause: &[i32]) -> bool {
        use std::cmp::Ordering;
    
        let mut begin_iter = clause.iter();
        let mut end_iter = clause.iter().rev();
    
        let mut begin = begin_iter.next();
        let mut end = end_iter.next();
    
        if begin == end {
            return false;
        }
    
        while let (Some(&x), Some(&y)) = (begin, end) {
            match (-x).cmp(&y) {
                Ordering::Equal => return true,
                Ordering::Less => end = end_iter.next(),
                Ordering::Greater => begin = begin_iter.next(),
            }
        }
    
        false
    }
    
    fn main() {
        let v = [
            vec![1, 2, 3],
            vec![-2, -1, 1, 3],
            vec![-4, -3, -1, 2],
            vec![-10, -5, 1, 2, 3, 4, 5, 6, 7],
        ];
    
        v.into_iter().for_each(|clause| {
            println!("{:?} {}", clause, is_tautology(&clause));
        });
    }
    
[/code]

## 修正

C++コードの `while(*begin<0 && *end > 0)` にあたる部分が漏れていたため、`if`式を追加しました。

[code]

    fn is_tautology(clause: &[i32]) -> bool {
        use std::cmp::Ordering;
    
        let mut begin_iter = clause.iter();
        let mut end_iter = clause.iter().rev();
    
        let mut begin = begin_iter.next();
        let mut end = end_iter.next();
    
        if begin == end {
            return false;
        }
    
        while let (Some(&x), Some(&y)) = (begin, end) {
            if x >= 0 || y <= 0 {
                break;
            }
            match (-x).cmp(&y) {
                Ordering::Equal => return true,
                Ordering::Less => end = end_iter.next(),
                Ordering::Greater => begin = begin_iter.next(),
            }
        }
    
        false
    }
    
[/code]


CC BY-SA 4.0
2022-12-17T12:58:05.973
92842
2022-12-17T23:17:24.437
2022-12-17T23:17:24.437
14101
14101
92841
answer


`HashSet` を使う方法です。

[code]

    use std::collections::HashSet;
    
    fn is_tautology(v: &Vec<i32>) -> bool {
        if v.is_empty() { return false };
        let uniq: HashSet<i32> = v.into_iter().map(|i| i.abs()).collect();
        return v.len() != uniq.len();
    }
    
[/code]


CC BY-SA 4.0
2022-12-17T14:46:41.073
92844
2022-12-17T15:59:06.647
2022-12-17T15:59:06.647
47127
47127
92841
answer