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,]));
    }
}