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}