Skip to main content

entropy_pool/
lib.rs

1use rand::Rng;
2use std::collections::BTreeSet;
3use wabi_tree::OSBTreeSet;
4
5pub struct EntropyPool {
6    rng: rand::rngs::ThreadRng,
7    b: u64,
8    m: u64,
9    count: u64,
10}
11
12impl EntropyPool {
13    pub fn new() -> EntropyPool {
14        let mut rng = rand::rng();
15        let b: u8 = rng.random();
16        let m: u64 = 256;
17        let count: u64 = 1;
18        EntropyPool {
19            rng,
20            b: b as u64,
21            m,
22            count,
23        }
24    }
25
26    pub fn gen_range(&mut self, n: u64) -> u64 {
27        loop {
28            while 4294967296u64 * (self.m % n) >= self.m {
29                let r: u8 = self.rng.random();
30                self.count += 1;
31                self.m *= 256;
32                self.b = self.b * 256 + r as u64;
33            }
34            let r = self.m % n;
35            let q = self.m / n;
36            if r < self.m - self.b {
37                let b = self.b;
38                self.m = q;
39                self.b = b / n;
40                return b % n;
41            } else {
42                self.b = self.m - self.b - 1;
43                self.m = r;
44            }
45        }
46    }
47
48    fn recycle(&mut self, b: u64, m: u64) {
49        self.b = self.b * m + b;
50        self.m = self.m * m;
51    }
52
53    pub fn permutation(&mut self, m: u64, n: u64) -> Vec<u64> {
54        let mut c = Vec::from_iter(0..n);
55        for i in 0..m {
56            let r = self.gen_range(n - i) + i;
57            let tmp = c[i as usize];
58            c[i as usize] = c[r as usize];
59            c[r as usize] = tmp;
60        }
61        c.truncate(m as usize);
62        c
63    }
64
65    pub fn combination(&mut self, m: u64, n: u64) -> BTreeSet<u64> {
66        let rev = 2 * m > n;
67        let m = if rev { n - m } else { m };
68        let mut s = OSBTreeSet::with_capacity(m as usize);
69        let mut c = Vec::from_iter(0..n);
70        for i in (n - m..n).rev() {
71            let r = self.gen_range(i + 1);
72            let t = c[r as usize];
73            c[r as usize] = c[i as usize];
74            s.insert(t);
75            let b = s.rank_of(&t).unwrap() as u64;
76            self.recycle(b, n - i);
77        }
78        if !rev {
79            BTreeSet::from_iter(s.into_iter())
80        } else {
81            c.truncate((n - m) as usize);
82            BTreeSet::from_iter(c.into_iter())
83        }
84    }
85}
86
87#[cfg(test)]
88mod tests {
89    use super::*;
90    use std::collections::BTreeMap;
91
92    #[test]
93    fn it_works() {
94        let mut ep = EntropyPool::new();
95        assert_eq!(ep.combination(200000, 300000).len(), 200000);
96        println!("{:#?}", ep.count);
97        ep = EntropyPool::new();
98        let mut m = BTreeMap::new();
99        for _ in 0..1000000 {
100            m.entry(ep.combination(2, 6))
101                .and_modify(|e| *e += 1)
102                .or_insert(1);
103        }
104        println!("{:#?}", m.into_values());
105    }
106}