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