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

use factorial::Factorial;
use std::cmp::Ord;
use std::convert::{TryFrom, TryInto};

struct PermutationCounts {
    // Each count represents the number of items positioned to the left of the value at this index
    // that are lower to that value.
    // If the original data is decreasingly sorted, these are all zero
    // Example:
    // sorted:   7, 6, 5, 4, 3, 2, 1, 0
    // shuffled: 3, 6, 5, 7, 0, 2, 1, 4
    // counts:   0, 1, 1, 3, 0, 1, 1, 4
    // permutation: 0*0! + 1*1! + 1*2! + 3*3! + 0*4! + 1*5! + 1*6! + 4*7! == 21021
    counts: Vec<usize>,
}

impl PermutationCounts {
    fn calculate_count<T: Ord>(pos: usize, x: &T, data: &[T]) -> usize {
        // Count items that are positioned to the left of this value, but are lower.
        // 0 in a descendingly sorted collection
        data.iter().take(pos).filter(|y| y < &x).count()
    }
    fn encode_count(indexed_count: (usize, usize)) -> usize {
        let (index, count) = indexed_count;
        count * index.factorial()
    }
    fn encode(&self) -> usize {
        self.counts
            .iter()
            .cloned()
            .enumerate()
            .map(Self::encode_count)
            .sum()
    }
    fn from_data<T: Ord>(data: &[T]) -> Self {
        Self {
            counts: data
                .iter()
                .enumerate()
                .map(|(index, x)| Self::calculate_count(index, x, data))
                .collect(),
        }
    }
    fn decode_count(index: usize, permutation: &mut usize) -> usize {
        let factorial = index.factorial();
        let count = permutation.div_euclid(factorial);
        *permutation = permutation.rem_euclid(factorial);
        count
    }
    fn decode(mut permutation: usize, n: usize) -> Self {
        // Must be decoded in reverse order as we'll remove parts from the permutation number
        let mut counts = (0..n)
            .rev()
            .map(|index| Self::decode_count(index, &mut permutation))
            .collect::<Vec<_>>();
        counts.reverse();
        Self { counts }
    }
    fn nth_smallest<T: Ord + Clone>(n: usize, increasing: &[T], permuted: &[T]) -> T {
        increasing
            .iter()
            .filter(|x| !permuted.contains(*x))
            .nth(n)
            .unwrap()
            .clone()
    }
    fn apply<T: Ord + Clone>(&self, data: &[T]) -> Vec<T> {
        let mut increasing = data.to_vec();
        increasing.sort();
        let mut permuted = Vec::new();
        for count in self.counts.iter().rev() {
            permuted.push(Self::nth_smallest(*count, &increasing, &permuted));
        }
        permuted.reverse();
        permuted
    }
}

/// Encode a slice's permutation from the ordered state as a single number.
///
/// From a slice of up to 20 elements, produce a unique number that represents the order of the
/// elements in that slice. This number can later be used to reconstitute the original slice
/// permutation by calling `decode_permutation`.
///
/// This is the most space-efficient way of storing that information as every bit of entropy in the
/// slice's permutation is represented by a bit in the permutation number.
/// The maximum possible output is n!, where n is the size of the slice.
/// 5! fits in a u8
/// 8! fits in a u16
/// 12! fits in a u32
/// 20! fits in a u64
pub fn encode_permutation<T: Ord, Encoded: TryFrom<usize>>(
    data: &[T],
) -> Result<Encoded, Encoded::Error> {
    PermutationCounts::from_data(data).encode().try_into()
}

/// Decode a permutation number into a unique slice's permutation
///
/// Take as input the permutation number produced by `encode_permutation` and a slice with each
/// element of the set in an arbitrary order.
///
/// Output a Vec with the data ordered in the unique permutation that matches this permutation
/// number.
pub fn decode_permutation<'a, T: Ord + Clone, ToDecode: TryInto<usize>>(
    permutation: ToDecode,
    data: &'a [T],
) -> Result<Vec<T>, ToDecode::Error> {
    Ok(PermutationCounts::decode(permutation.try_into()?, data.len()).apply(&data))
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::seq::SliceRandom;
    use rand::thread_rng;
    const SEQ: [u8; 8] = [3, 6, 5, 7, 0, 2, 1, 4];
    #[test]
    fn test_encode_permutation() {
        assert_eq!(Ok(21021), encode_permutation(&SEQ));
    }
    #[test]
    fn test_encode_permutation_fails_with_too_small_type() {
        assert!(encode_permutation::<_, u8>(&SEQ).is_err());
    }
    #[test]
    fn test_decode_permutation() {
        let seq = SEQ.to_vec();
        let mut rng = thread_rng();
        let mut shuffled = seq.clone();
        shuffled.shuffle(&mut rng);
        assert_eq!(decode_permutation(21021, &shuffled), Ok(seq));
    }
}