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
/// O(N)
pub fn permutation_rank(p: &[usize]) -> usize {
let n = p.len();
let mut s = (1usize << n) - 1;
let mut fact = 1;
let mut rank = 0;
for (i, &p) in p.iter().rev().enumerate() {
rank += (p - (s & ((1 << p) - 1)).count_ones() as usize) * fact;
s &= !(1 << p);
fact *= i + 1;
}
rank
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
let cases = vec![(vec![0, 2, 1], 1), (vec![2, 0, 1], 4)];
for (p, r) in cases {
assert_eq!(permutation_rank(&p), r);
}
}
}