competitive-hpp 0.10.21

Competitive Programming Library for AtCoder with Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

use std::collections::HashSet;

pub trait PowerSetTrait<T> {
    fn power_set(&self) -> Vec<Vec<T>>;
}

impl<T> PowerSetTrait<T> for Vec<T>
where
    T: Clone,
{
    #[inline]
    fn power_set(&self) -> Vec<Vec<T>> {
        let n = self.len();
        (0..1 << n)
            .map(|pattern| {
                (0..n)
                    .filter_map(|i| {
                        if (pattern >> i) & 1 == 1 {
                            Some(self[i].clone())
                        } else {
                            None
                        }
                    })
                    .collect::<Vec<_>>()
            })
            .collect()
    }
}

impl<K> PowerSetTrait<K> for HashSet<K>
where
    K: Clone,
{
    /// Unspecified order
    #[inline]
    fn power_set(&self) -> Vec<Vec<K>> {
        let n = self.len();
        let v: Vec<_> = self.iter().collect();
        (0..1 << n)
            .map(|pattern| {
                (0..n)
                    .filter_map(|i| {
                        if (pattern >> i) & 1 == 1 {
                            Some(v[i].clone())
                        } else {
                            None
                        }
                    })
                    .collect::<Vec<_>>()
            })
            .collect()
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn vec_test() {
        let mut test = vec![0, 1, 2];

        assert_eq!(
            vec![
                vec![],
                vec![0],
                vec![1],
                vec![0, 1],
                vec![2],
                vec![0, 2],
                vec![1, 2],
                vec![0, 1, 2]
            ],
            test.power_set()
        );

        test.push(3);
        test.push(4);

        assert_eq!(test.power_set().len(), 32);
    }

    #[test]
    fn set_test() {
        let test = maplit::hashset! { 0, 1, 2 };

        assert_eq!(
            vec![
                vec![],
                vec![0],
                vec![1],
                vec![0, 1],
                vec![2],
                vec![0, 2],
                vec![1, 2],
                vec![0, 1, 2]
            ]
            .len(),
            test.power_set().len()
        );

        let test_set = maplit::hashset! {
            vec![],
            vec![0],
            vec![1],
            vec![0, 1],
            vec![2],
            vec![0, 2],
            vec![1, 2],
            vec![0, 1, 2]
        };
        let test_power_set: HashSet<Vec<_>> = test.power_set().into_iter().collect();

        assert_eq!(test_set.len(), test_power_set.len());
        assert!(test_power_set.contains(&vec![0,]));
    }
}