#[cfg(feature = "alloc")]
use alloc::vec::Vec;
pub fn decode_mut<T: Ord>(xs: &mut [T], mut p: usize) {
let n = xs.len();
let mut m = crate::factorial(n);
debug_assert!(crate::is_ordered_set(xs), "Failed precondition");
debug_assert!(p < m, "Failed precondition");
for i in 0 .. n {
m /= n - i;
let j = i + p / m;
p %= m;
xs[i ..= j].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(d: usize, p: usize, e: &[usize]) {
let mut r: Vec<_> = (0 .. d).collect();
decode_mut(&mut r, p);
assert_eq!(r, e, "p={p}");
}
test(0, 0, &[]);
test(1, 0, &[0]);
test(2, 0, &[0, 1]);
test(2, 1, &[1, 0]);
test(3, 0, &[0, 1, 2]);
test(3, 1, &[0, 2, 1]);
test(3, 2, &[1, 0, 2]);
test(3, 3, &[1, 2, 0]);
test(3, 4, &[2, 0, 1]);
test(3, 5, &[2, 1, 0]);
}
pub fn encode<T: Ord>(xs: &[T]) -> usize {
debug_assert!(crate::is_unordered_set(xs), "Failed precondition");
let n = xs.len();
let mut m = crate::factorial(n);
let mut r = 0;
for i in 0 .. n {
m /= n - i;
r += m * xs[i + 1 ..].iter().filter(|&x| x < &xs[i]).count();
}
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, 1, 2], 0);
test(&[0, 2, 1], 1);
test(&[1, 0, 2], 2);
test(&[1, 2, 0], 3);
test(&[2, 0, 1], 4);
test(&[2, 1, 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_set(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 k = self.data.len();
if k == 0 {
return true;
}
let mut i = k - 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 j = self.data[i ..].iter().position(|x| x > &self.data[i - 1]).unwrap();
self.data.swap(i - 1, i + j);
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, 1, 2], &[0, 2, 1], &[1, 0, 2], &[1, 2, 0], &[2, 0, 1], &[2, 1, 0]]);
test(&[
&[0, 1, 2, 3],
&[0, 1, 3, 2],
&[0, 2, 1, 3],
&[0, 2, 3, 1],
&[0, 3, 1, 2],
&[0, 3, 2, 1],
&[1, 0, 2, 3],
&[1, 0, 3, 2],
&[1, 2, 0, 3],
&[1, 2, 3, 0],
&[1, 3, 0, 2],
&[1, 3, 2, 0],
&[2, 0, 1, 3],
&[2, 0, 3, 1],
&[2, 1, 0, 3],
&[2, 1, 3, 0],
&[2, 3, 0, 1],
&[2, 3, 1, 0],
&[3, 0, 1, 2],
&[3, 0, 2, 1],
&[3, 1, 0, 2],
&[3, 1, 2, 0],
&[3, 2, 0, 1],
&[3, 2, 1, 0],
]);
}