toolbox_rs/
enumerative_source_coding.rs

1use crate::math::choose;
2
3/// Implementation of Cover's algorithm to enumerate of sequences of weight w, cf.
4/// "Enumerative Source Encoding". Thomas M. Cover.
5/// Appears in IEEE Transactions on Information Theory. Vol 19, Issue: 1, Jan 1973
6///
7/// The implementation corresponds to Section "Example 2 - Enumeration of Sequences of Weight w".
8///
9/// # Examples
10///
11/// ```
12/// use toolbox_rs::enumerative_source_coding::decode_u64;
13///
14/// // 0th number with 3 bits set in a 64 bit number
15/// assert_eq!(decode_u64(3, 0), 0b000_0111);    
16/// ```
17pub fn decode_u64(mut ones: u64, mut ordinal: u64) -> u64 {
18    debug_assert!(ordinal < choose(64, ones));
19    let mut result = 0;
20    for bit in (0..64).rev() {
21        let n_ck = choose(bit, ones);
22        if ordinal >= n_ck {
23            ordinal -= n_ck;
24            result |= 1 << bit;
25            ones -= 1;
26        }
27    }
28    result
29}
30
31#[cfg(test)]
32mod tests {
33    use crate::enumerative_source_coding::decode_u64;
34
35    #[test]
36    fn paper_examples() {
37        // 0th number with 3 bits set
38        assert_eq!(decode_u64(3, 0), 0b0000_0111);
39        // 1st number with 3 bits set
40        assert_eq!(decode_u64(3, 1), 0b0000_1011);
41        // 21st number with 3 bits set
42        assert_eq!(decode_u64(3, 21), 0b0100_0101);
43        // 34th number with 3 bits set
44        assert_eq!(decode_u64(3, 34), 0b0111_0000);
45        // 41663th (last) number with 3 bits set
46        assert_eq!(
47            decode_u64(3, 41663),
48            0b1110_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000
49        );
50    }
51}
toolbox_rs/enumerative_source_coding.rs

toolbox_rs/
enumerative_source_coding.rs
