#[cfg(feature = "alloc")]
use alloc::vec;
#[cfg(feature = "alloc")]
use alloc::vec::Vec;
use core::borrow::BorrowMut;
pub fn decode_mut(mut n: usize, mut k: usize, r: &mut [usize]) {
debug_assert_eq!(r.len(), k, "Failed precondition");
debug_assert!(k > 0 || n == 0, "Failed precondition");
while k > 0 {
let mut i = k;
let mut x = 1;
while x <= n {
i += 1;
x *= i;
x /= i - k;
}
x *= i - k;
x /= i;
i -= 1;
n -= x;
k -= 1;
r[k] = i;
}
}
#[cfg(feature = "alloc")]
pub fn decode(n: usize, k: usize) -> Vec<usize> {
let mut r = vec![0; k];
decode_mut(n, k, &mut r);
r
}
#[test]
fn decode_ok() {
fn test(n: usize, k: usize, r: &[usize]) {
assert_eq!(decode(n, k), r, "n={n} k={k}");
}
test(0, 0, &[]);
test(0, 1, &[0]);
test(1, 1, &[1]);
test(2, 1, &[2]);
test(0, 2, &[0, 1]);
test(1, 2, &[0, 2]);
test(2, 2, &[1, 2]);
test(3, 2, &[0, 3]);
test(0, 3, &[0, 1, 2]);
test(1, 3, &[0, 1, 3]);
test(2, 3, &[0, 2, 3]);
test(3, 3, &[1, 2, 3]);
test(4, 3, &[0, 1, 4]);
test(5, 3, &[0, 2, 4]);
test(6, 3, &[1, 2, 4]);
test(7, 3, &[0, 3, 4]);
test(8, 3, &[1, 3, 4]);
test(9, 3, &[2, 3, 4]);
test(10, 3, &[0, 1, 5]);
}
pub fn encode(xs: &[usize]) -> usize {
debug_assert!(crate::is_ordered_set(xs), "Failed precondition");
let mut r = 0;
for (i, &x) in xs.iter().enumerate() {
r += crate::combination(x, i + 1);
}
r
}
#[test]
fn encode_ok() {
fn test(xs: &[usize], r: usize) {
assert_eq!(encode(xs), r, "xs={xs:?}");
}
test(&[], 0);
test(&[0], 0);
test(&[1], 1);
test(&[0, 1], 0);
test(&[0, 2], 1);
test(&[1, 2], 2);
test(&[0, 3], 3);
test(&[0, 1, 2], 0);
test(&[0, 1, 3], 1);
test(&[0, 2, 3], 2);
test(&[1, 2, 3], 3);
test(&[0, 1, 4], 4);
test(&[0, 2, 4], 5);
test(&[1, 2, 4], 6);
test(&[0, 3, 4], 7);
test(&[1, 3, 4], 8);
test(&[2, 3, 4], 9);
test(&[0, 1, 5], 10);
}
pub struct Iter<T: BorrowMut<[usize]>> {
data: T,
}
#[cfg(feature = "alloc")]
impl Iter<Vec<usize>> {
pub fn new(k: usize) -> Iter<Vec<usize>> {
Iter { data: (0 .. k).collect() }
}
}
impl<T: BorrowMut<[usize]>> Iter<T> {
pub fn new_with_buffer(mut buffer: T) -> Iter<T> {
for (i, x) in buffer.borrow_mut().iter_mut().enumerate() {
*x = i;
}
Iter { data: buffer }
}
pub fn new_from(xs: T) -> Iter<T> {
debug_assert!(crate::is_ordered_set(xs.borrow()), "Failed precondition");
Iter { data: xs }
}
pub fn get(&self) -> &[usize] {
self.data.borrow()
}
pub fn advance(&mut self) {
let k = self.data.borrow().len();
for i in 0 .. k {
self.data.borrow_mut()[i] += 1;
if i == k - 1 || self.data.borrow()[i] < self.data.borrow()[i + 1] {
break;
}
self.data.borrow_mut()[i] = i;
}
}
}
#[test]
fn iter_ok() {
fn test(k: usize, r: &[&[usize]]) {
let mut iter = Iter::new(k);
for (i, &r) in r.iter().enumerate() {
assert_eq!(iter.get(), r);
assert_eq!(encode(r), i);
iter.advance();
}
}
test(0, &[&[]]);
test(1, &[&[0], &[1], &[2]]);
test(2, &[&[0, 1], &[0, 2], &[1, 2], &[0, 3], &[1, 3], &[2, 3]]);
test(
3,
&[
&[0, 1, 2],
&[0, 1, 3],
&[0, 2, 3],
&[1, 2, 3],
&[0, 1, 4],
&[0, 2, 4],
&[1, 2, 4],
&[0, 3, 4],
&[1, 3, 4],
&[2, 3, 4],
&[0, 1, 5],
&[0, 2, 5],
&[1, 2, 5],
],
);
}
#[test]
fn iter_new_from_ok() {
fn test(xs: &[usize], r: &[&[usize]]) {
let mut iter = Iter::new_from(xs.to_vec());
let start = encode(xs);
for (i, &r) in r.iter().enumerate() {
assert_eq!(iter.get(), r);
assert_eq!(encode(r), start + i);
iter.advance();
}
}
test(&[], &[&[]]);
test(&[2], &[&[2], &[3], &[4]]);
test(&[0, 3], &[&[0, 3], &[1, 3], &[2, 3]]);
test(
&[0, 2, 4],
&[
&[0, 2, 4],
&[1, 2, 4],
&[0, 3, 4],
&[1, 3, 4],
&[2, 3, 4],
&[0, 1, 5],
&[0, 2, 5],
&[1, 2, 5],
],
);
}