betting/
utils.rs

1// Distribute integer quantities of a total according to un-normalized parts,
2// minimizing the error incurred by rounding
3// https://en.wikipedia.org/wiki/Largest_remainder_method
4pub fn lrm(total: u64, parts: &Vec<u64>) -> Vec<u64> {
5    let norm = parts.iter().fold(0, |i, a| i + *a);
6    if norm == 0 {
7        return vec![0; parts.len()];
8    }
9    let parts: Vec<_> = parts
10        .into_iter()
11        .map(|part| *part as f32 / norm as f32)
12        .collect();
13    // compute the ideal gains (real number)
14    let fgains: Vec<f32> = parts.iter().map(|part| total as f32 * part).collect();
15    // attribute the rounded down gains to everyone
16    let mut gains: Vec<u64> = fgains.iter().map(|fgain| fgain.floor() as u64).collect();
17    // compute the remaining quantity to distribute (guaranteed to be less than gains.len())
18    let total = total - gains.iter().fold(0, |init, gain| init + gain);
19    // give +1 to the largest remainders to distribute the remaining quantity
20    let mut fgains_idx = fgains.iter().enumerate().collect::<Vec<_>>();
21    fgains_idx.sort_unstable_by(|(_i1, fgain1), (_i2, fgain2)| {
22        (**fgain1 - fgain1.floor())
23            .partial_cmp(&(**fgain2 - fgain2.floor()))
24            .unwrap()
25    });
26    fgains_idx.reverse();
27    for (i, _) in fgains_idx.into_iter().take(total as usize) {
28        gains[i] += 1;
29    }
30    gains
31}