#[cfg(feature = "alloc")]
use alloc::vec::Vec;
pub fn decode_mut<T: Ord>(xs: &mut [T], mut p: usize) {
let mut m = crate::multinomial(xs);
debug_assert!(crate::is_ordered_multiset(xs), "Failed precondition");
debug_assert!(p < m, "Failed precondition");
let n = xs.len();
for i in 0 .. n {
let mut c = i;
let mut k = 1;
for j in i + 1 .. n {
if xs[j] == xs[j - 1] {
k += 1;
continue;
}
let s = m * k / (n - i);
if p < s {
break;
}
p -= s;
c = j;
k = 1;
}
m = m * k / (n - i);
xs[i ..= c].rotate_right(1);
}
debug_assert_eq!(m, 1);
debug_assert_eq!(p, 0);
}
#[cfg(feature = "alloc")]
pub fn decode<T: Clone + Ord>(xs: &[T], p: usize) -> Vec<T> {
let mut xs = xs.to_vec();
decode_mut(&mut xs[..], p);
xs
}
#[test]
fn decode_ok() {
fn test(xs: &[usize], p: usize, e: &[usize]) {
let r = decode(xs, p);
assert_eq!(r, e, "xs={xs:?} p={p}");
}
test(&[], 0, &[]);
test(&[0], 0, &[0]);
test(&[0, 1], 0, &[0, 1]);
test(&[0, 1], 1, &[1, 0]);
test(&[0, 0], 0, &[0, 0]);
test(&[0, 0, 1], 0, &[0, 0, 1]);
test(&[0, 0, 1], 1, &[0, 1, 0]);
test(&[0, 0, 1], 2, &[1, 0, 0]);
test(&[0, 0, 1, 1], 0, &[0, 0, 1, 1]);
test(&[0, 0, 1, 1], 1, &[0, 1, 0, 1]);
test(&[0, 0, 1, 1], 2, &[0, 1, 1, 0]);
test(&[0, 0, 1, 1], 3, &[1, 0, 0, 1]);
test(&[0, 0, 1, 1], 4, &[1, 0, 1, 0]);
test(&[0, 0, 1, 1], 5, &[1, 1, 0, 0]);
test(&[0, 0, 0, 1, 1, 2], 0, &[0, 0, 0, 1, 1, 2]);
test(&[0, 0, 0, 1, 1, 2], 1, &[0, 0, 0, 1, 2, 1]);
test(&[0, 0, 0, 1, 1, 2], 2, &[0, 0, 0, 2, 1, 1]);
test(&[0, 0, 0, 1, 1, 2], 3, &[0, 0, 1, 0, 1, 2]);
test(&[0, 0, 0, 1, 1, 2], 4, &[0, 0, 1, 0, 2, 1]);
test(&[0, 0, 0, 1, 1, 2], 5, &[0, 0, 1, 1, 0, 2]);
test(&[0, 0, 0, 1, 1, 2], 6, &[0, 0, 1, 1, 2, 0]);
test(&[0, 0, 0, 1, 1, 2], 7, &[0, 0, 1, 2, 0, 1]);
test(&[0, 0, 0, 1, 1, 2], 8, &[0, 0, 1, 2, 1, 0]);
test(&[0, 0, 0, 1, 1, 2], 9, &[0, 0, 2, 0, 1, 1]);
test(&[0, 0, 0, 1, 1, 2], 10, &[0, 0, 2, 1, 0, 1]);
}
pub fn encode<T: Ord>(xs: &[T]) -> usize {
let n = xs.len();
let mut m = crate::multinomial(xs);
let mut r = 0;
for i in 0 .. n {
for j in i + 1 .. n {
if xs[j] >= xs[i] || xs[i + 1 .. j].contains(&xs[j]) {
continue;
}
let k = xs[j ..].iter().filter(|&x| x == &xs[j]).count();
r += m * k / (n - i);
}
let k = xs[i ..].iter().filter(|&x| x == &xs[i]).count();
m = m * k / (n - i);
}
debug_assert_eq!(m, 1);
r
}
#[test]
fn encode_ok() {
fn test(xs: &[usize], p: usize) {
assert_eq!(encode(xs), p, "xs={xs:?}");
}
test(&[], 0);
test(&[0], 0);
test(&[0, 1], 0);
test(&[1, 0], 1);
test(&[0, 0], 0);
test(&[0, 0, 1], 0);
test(&[0, 1, 0], 1);
test(&[1, 0, 0], 2);
test(&[0, 0, 1, 1], 0);
test(&[0, 1, 0, 1], 1);
test(&[0, 1, 1, 0], 2);
test(&[1, 0, 0, 1], 3);
test(&[1, 0, 1, 0], 4);
test(&[1, 1, 0, 0], 5);
}
pub struct Iter<'a, T> {
data: &'a mut [T],
state: IterState,
}
enum IterState {
New,
Running,
Done,
}
impl<'a, T: Ord> Iter<'a, T> {
pub fn new(xs: &mut [T]) -> Iter<T> {
debug_assert!(crate::is_ordered_multiset(xs));
Iter { data: xs, state: IterState::New }
}
#[allow(clippy::should_implement_trait)]
pub fn next(&mut self) -> Option<&[T]> {
match self.state {
IterState::New => self.state = IterState::Running,
IterState::Running => {
if self.advance() {
self.state = IterState::Done;
}
}
IterState::Done => (),
}
match self.state {
IterState::New => unreachable!(),
IterState::Running => Some(self.data),
IterState::Done => None,
}
}
fn advance(&mut self) -> bool {
let n = self.data.len();
if n == 0 {
return true;
}
let mut i = n - 1;
while i > 0 && self.data[i - 1] >= self.data[i] {
i -= 1;
}
if i == 0 {
self.data.reverse();
return true;
}
self.data[i ..].reverse();
let k = self.data[i ..].iter().position(|x| x > &self.data[i - 1]).unwrap();
self.data.swap(i - 1, i + k);
false
}
}
#[test]
fn iter_ok() {
fn test(r: &[&[usize]]) {
let mut xs = r[0].to_vec();
let mut iter = Iter::new(&mut xs);
let mut i = 0;
while let Some(xs) = iter.next() {
assert_eq!(xs, r[i]);
assert_eq!(encode(xs), i);
i += 1;
}
assert_eq!(r.len(), i);
assert_eq!(xs, r[0]);
}
test(&[&[]]);
test(&[&[0]]);
test(&[&[0, 1], &[1, 0]]);
test(&[&[0, 0, 1], &[0, 1, 0], &[1, 0, 0]]);
test(&[&[0, 1, 2], &[0, 2, 1], &[1, 0, 2], &[1, 2, 0], &[2, 0, 1], &[2, 1, 0]]);
test(&[
&[0, 0, 1, 1],
&[0, 1, 0, 1],
&[0, 1, 1, 0],
&[1, 0, 0, 1],
&[1, 0, 1, 0],
&[1, 1, 0, 0],
]);
}