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 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377
//! The `droprate` crate aims to be a drop-in solution for picking options from //! a weighted list of possibilities. //! //! While naive random number generation to pick from some list of traits is //! pretty easy to implement as-needed, it doesn't take long to run into scenarios //! where this solution provides suboptimal results. //! //! In a card game, you may want to simulate a deck of cards being shuffled, which //! means that the odds of each card becomes zero once it's been pulled from the //! deck. use std::collections::HashMap; extern crate rand; pub trait ProbabilityTable<T> { /// Add an option to the random table with the assigned weight value. /// /// You can chain multiple `push(...)` calls together to save a little space. /// /// The weight is stored as an `f64` value, so you don't _need_ the specify /// the odds in pure-integer ratios. Also, while you could use numbers to look /// like a "precent chance", it's important to remember that each items weight /// calculates odds against the entire table, and so if you add "more than 100%" /// then you will end up with each outcome's odds being less than you put in. /// /// In other words, it's best to think of this like a recipe with ratios: /// /// * 2 parts Option A /// * 5 parts Option B /// * 1 part Option C /// * 12 parts Option D /// * etc. /// /// # Examples /// /// ``` /// use droprate::{RandomTable, ProbabilityTable}; /// /// let mut table = RandomTable::<&'static str>::new(); /// table.push("First option", 1f64) // 1/4 = 25% chance /// .push("Second option", 1f64) // 1/4 = 25% chance /// .push("Third option", 2f64); // 2/4 = 50% chance /// /// assert_eq!(3, table.count()); /// ``` fn push(&mut self, ident: T, weight: f64) -> &mut ProbabilityTable<T>; /// Get the number of possible items in the table. /// /// # Examples /// /// ``` /// use droprate::{RandomTable, ProbabilityTable}; /// /// let mut table = RandomTable::<&'static str>::new(); /// table.push("First option", 1f64); /// assert_eq!(1, table.count()); /// /// table.push("Second option", 1f64) /// .push("Third option", 2f64); /// assert_eq!(3, table.count()); /// ``` fn count(&self) -> usize; /// Get a vector of all of the options in the list. There is no guarantee /// over the order in which items are returned. /// /// # Examples /// /// ``` /// use droprate::{RandomTable, ProbabilityTable}; /// /// let mut table = RandomTable::<&'static str>::new(); /// table.push("A", 1f64) /// .push("B", 1f64); /// /// assert_eq!(2, table.keys().len()); /// ``` fn keys(&self) -> Vec<T>; /// Choose an option from the list of options, using the supplied weights /// to map the odds. The actual odds for each trial may differ when using /// tables other than [`RandomTable`] (e.g., [`FairlyRandomTable`] tracks /// results from previous trials in order to deliver a more evenly distributed /// set of results than one would fine from a more "true" random generator) /// /// # Errors /// /// If no options have been specified (or all options added were give a weight /// less than or equal to zero), this will return an error that the generated /// value was outside the range of the table. /// /// # Examples /// /// ``` /// use droprate::{RandomTable, ProbabilityTable}; /// /// let mut table = RandomTable::<&'static str>::new(); /// assert_eq!(true, table.random().is_err()); /// /// table.push("A", 1f64) /// .push("B", 1f64); /// /// assert_eq!(false, table.random().is_err()); /// ``` fn random(&mut self) -> Result<T, String>; } /// `RandomTable` represents a table of options and their relative weights. The /// odds of any option being selected is `option's weight / all options' weights`. /// This is a typical implementation of random tables in software and games as /// each trial runs independent of other trials which may have happened in the /// past. As such, it is perfectly valid for an option with 50% odds to be /// selected many times in a row. (It's an outcome which becomes statistically /// less likely to have happened, but nevertheless if you have 5 in a row, the /// next trial is still a 50% chance.) /// /// This kind of random is useful, but it's also hard for users to understand /// and can often lead to outcomes which (in games, at least) feel unfair. pub struct RandomTable<T> { pub(crate) table: HashMap<T, f64>, pub(crate) total: f64, } /// `FairlyRandomTable` aims to create results which a human might create when /// asked to create a random sequence from a weighted table. It is human nature /// to generate a more evenly-distributed list of random values because we are /// aware of the the history of options chosen. /// /// Calling this a "random" table strains the definition -- it is certainly going /// to give you "mixed up" results, but ultimately they will be far more /// predictable. That said, they will _also_ feel much more "fair" to users who /// experience them. /// /// For example: Given a result with a 1-in-10 odds ratio, there is still a 30% /// chance that you won't get that result within 10 trials. There is a 12% chance /// that you won't even see the result within 20 trials. This is where players /// start to complain that the devs hate them. /// /// With `FairlyRandomTable`, every trial which doesn't give a certain result /// increases the probability of that result on the next trial (proportional to /// its initial probability) until it is selected, which decreases its probability /// dramatically (however it's not impossible to get multiple results in a row -- /// in fact, allowing for multiple results in a row of even unlikely options is /// a design goal; you just won't seem them as frequently). pub struct FairlyRandomTable<T> { pub(crate) base: RandomTable<T>, pub(crate) table: HashMap<T, f64>, pub(crate) total: f64, } // RandomTable impl<T: std::cmp::Eq + std::hash::Hash> RandomTable<T> { /// Create a new instance of `RandomTable` with no options. pub fn new() -> RandomTable<T> { RandomTable { table: HashMap::new(), total: 0f64, } } /// Create a new `RandomTable` from a [`HashMap`]. /// /// # Examples /// /// ``` /// use droprate::{RandomTable, ProbabilityTable}; /// use std::collections::HashMap; /// /// let map: HashMap<&'static str, f64> = /// [("A", 1f64), /// ("B", 1f64), /// ("C", 3f64)] /// .iter().cloned().collect(); /// /// let mut table = RandomTable::<&'static str>::from_map(map); /// /// assert_eq!(3, table.count()); /// ``` /// /// ``` /// use droprate::{RandomTable, ProbabilityTable}; /// use std::collections::HashMap; /// /// let mut map = HashMap::new(); /// map.insert("A", 1f64); /// map.insert("B", 1f64); /// map.insert("C", 3f64); /// /// let mut table = RandomTable::<&'static str>::from_map(map); /// /// assert_eq!(3, table.count()); /// ``` pub fn from_map(in_table: HashMap<T, f64>) -> RandomTable<T> { let mut total = 0f64; for entry in &in_table { total += entry.1 } RandomTable { table: in_table, total: total, } } } impl<T: std::cmp::Eq + std::hash::Hash + Clone> ProbabilityTable<T> for RandomTable<T> { fn push(&mut self, ident: T, weight: f64) -> &mut ProbabilityTable<T> { self.table.insert(ident, weight); self.total += weight; self } fn count(&self) -> usize { self.table.len() } fn keys(&self) -> Vec<T> { self.table.keys().cloned().collect() } fn random(&mut self) -> Result<T, String> { let r = rand::random::<f64>() * self.total; let mut comp = r; for pair in &self.table { if *pair.1 > comp { return Ok(pair.0.clone()); } comp -= pair.1; } Err("Generated random outside of possible range".to_owned()) } } // // FairlyRandomTable // impl<T: std::cmp::Eq + std::hash::Hash + Clone> FairlyRandomTable<T> { /// Create a new instance of `FairlyRandomTable` with no options. pub fn new() -> FairlyRandomTable<T> { FairlyRandomTable { base: RandomTable::new(), table: HashMap::new(), total: 0f64, } } /// Create a new `FairlyRandomTable` from a [`HashMap`]. /// /// # Examples /// /// ``` /// use droprate::{FairlyRandomTable, ProbabilityTable}; /// use std::collections::HashMap; /// /// let map: HashMap<&'static str, f64> = /// [("A", 1f64), /// ("B", 1f64), /// ("C", 3f64)] /// .iter().cloned().collect(); /// /// let mut table = FairlyRandomTable::<&'static str>::from_map(map); /// /// assert_eq!(3, table.count()); /// ``` /// /// ``` /// use droprate::{FairlyRandomTable, ProbabilityTable}; /// use std::collections::HashMap; /// /// let mut map = HashMap::new(); /// map.insert("A", 1f64); /// map.insert("B", 1f64); /// map.insert("C", 3f64); /// /// let mut table = FairlyRandomTable::<&'static str>::from_map(map); /// /// assert_eq!(3, table.count()); /// ``` pub fn from_map(in_table: HashMap<T, f64>) -> FairlyRandomTable<T> { let mut total = 0f64; for entry in &in_table { total += entry.1 } FairlyRandomTable { base: RandomTable::from_map(in_table.clone()), table: in_table, total: total, } } /// Run a trial from this as though it were a [`RandomTable`]. The table's /// results memory will not be affected, and as such future results from /// calling `random()` will not account for this trial. pub fn pure_random(&self) -> Result<T, String> { let r = rand::random::<f64>() * self.total; let mut comp = r; for pair in &self.base.table { if *pair.1 > comp { return Ok(pair.0.clone()); } comp -= pair.1; } Err("Generated random outside of possible range".to_owned()) } fn redistribute_weights(&mut self, amount: f64) { let keys = self.table.keys().cloned().collect::<Vec<T>>(); for key in keys { let original = match self.base.table.get(&key) { Some(val) => *val, None => continue, }; let local = match self.table.get_mut(&key) { Some(val) => val, None => continue, }; let ratio = original / self.base.total; *local += amount * ratio; } } } impl<T: std::cmp::Eq + std::hash::Hash + Clone> ProbabilityTable<T> for FairlyRandomTable<T> { fn push(&mut self, ident: T, weight: f64) -> &mut ProbabilityTable<T> { self.base.push(ident.clone(), weight); self.table.insert(ident, weight); self.total += weight; self } fn count(&self) -> usize { self.table.len() } fn keys(&self) -> Vec<T> { self.table.keys().cloned().collect() } fn random(&mut self) -> Result<T, String> { let r = rand::random::<f64>() * self.total; let mut comp = r; let keys = self.table.keys().cloned(); let mut match_pair: Option<(T, f64)> = None; for key in keys { let val = self.table.get(&key); if let Some(val) = val { if *val > comp { match_pair = Some((key.clone(), *val)); break; } comp -= *val; } } match match_pair { Some(pair) => { self.table.entry(pair.0.clone()).and_modify(|e| *e = 0f64); self.redistribute_weights(pair.1); return Ok(pair.0.clone()); } None => {} } Err("Generated random outside of possible range".to_owned()) } }