| 1 |
use alloc::boxed::Box; |
| 2 |
use alloc::vec::Vec; |
| 3 |
use std::fmt; |
| 4 |
use std::iter::FusedIterator; |
| 5 |
|
| 6 |
use super::lazy_buffer::LazyBuffer; |
| 7 |
use crate::adaptors::checked_binomial; |
| 8 |
|
| 9 |
/// An iterator to iterate through all the `n`-length combinations in an iterator, with replacement. |
| 10 |
/// |
| 11 |
/// See [`.combinations_with_replacement()`](crate::Itertools::combinations_with_replacement) |
| 12 |
/// for more information. |
| 13 |
#[derive(Clone)] |
| 14 |
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 15 |
pub struct CombinationsWithReplacement<I> |
| 16 |
where |
| 17 |
I: Iterator, |
| 18 |
I::Item: Clone, |
| 19 |
{ |
| 20 |
indices: Box<[usize]>, |
| 21 |
pool: LazyBuffer<I>, |
| 22 |
first: bool, |
| 23 |
} |
| 24 |
|
| 25 |
impl<I> fmt::Debug for CombinationsWithReplacement<I> |
| 26 |
where |
| 27 |
I: Iterator + fmt::Debug, |
| 28 |
I::Item: fmt::Debug + Clone, |
| 29 |
{ |
| 30 |
debug_fmt_fields!(CombinationsWithReplacement, indices, pool, first); |
| 31 |
} |
| 32 |
|
| 33 |
/// Create a new `CombinationsWithReplacement` from a clonable iterator. |
| 34 |
pub fn combinations_with_replacement<I>(iter: I, k: usize) -> CombinationsWithReplacement<I> |
| 35 |
where |
| 36 |
I: Iterator, |
| 37 |
I::Item: Clone, |
| 38 |
{ |
| 39 |
let indices = alloc::vec![0; k].into_boxed_slice(); |
| 40 |
let pool: LazyBuffer<I> = LazyBuffer::new(iter); |
| 41 |
|
| 42 |
CombinationsWithReplacement { |
| 43 |
indices, |
| 44 |
pool, |
| 45 |
first: true, |
| 46 |
} |
| 47 |
} |
| 48 |
|
| 49 |
impl<I> CombinationsWithReplacement<I> |
| 50 |
where |
| 51 |
I: Iterator, |
| 52 |
I::Item: Clone, |
| 53 |
{ |
| 54 |
/// Increments indices representing the combination to advance to the next |
| 55 |
/// (in lexicographic order by increasing sequence) combination. |
| 56 |
/// |
| 57 |
/// Returns true if we've run out of combinations, false otherwise. |
| 58 |
fn increment_indices(&mut self) -> bool { |
| 59 |
// Check if we need to consume more from the iterator |
| 60 |
// This will run while we increment our first index digit |
| 61 |
self.pool.get_next(); |
| 62 |
|
| 63 |
// Work out where we need to update our indices |
| 64 |
let mut increment = None; |
| 65 |
for (i, indices_int) in self.indices.iter().enumerate().rev() { |
| 66 |
if *indices_int < self.pool.len() - 1 { |
| 67 |
increment = Some((i, indices_int + 1)); |
| 68 |
break; |
| 69 |
} |
| 70 |
} |
| 71 |
match increment { |
| 72 |
// If we can update the indices further |
| 73 |
Some((increment_from, increment_value)) => { |
| 74 |
// We need to update the rightmost non-max value |
| 75 |
// and all those to the right |
| 76 |
self.indices[increment_from..].fill(increment_value); |
| 77 |
false |
| 78 |
} |
| 79 |
// Otherwise, we're done |
| 80 |
None => true, |
| 81 |
} |
| 82 |
} |
| 83 |
} |
| 84 |
|
| 85 |
impl<I> Iterator for CombinationsWithReplacement<I> |
| 86 |
where |
| 87 |
I: Iterator, |
| 88 |
I::Item: Clone, |
| 89 |
{ |
| 90 |
type Item = Vec<I::Item>; |
| 91 |
|
| 92 |
fn next(&mut self) -> Option<Self::Item> { |
| 93 |
if self.first { |
| 94 |
// In empty edge cases, stop iterating immediately |
| 95 |
if !(self.indices.is_empty() || self.pool.get_next()) { |
| 96 |
return None; |
| 97 |
} |
| 98 |
self.first = false; |
| 99 |
} else if self.increment_indices() { |
| 100 |
return None; |
| 101 |
} |
| 102 |
Some(self.pool.get_at(&self.indices)) |
| 103 |
} |
| 104 |
|
| 105 |
fn nth(&mut self, n: usize) -> Option<Self::Item> { |
| 106 |
if self.first { |
| 107 |
// In empty edge cases, stop iterating immediately |
| 108 |
if !(self.indices.is_empty() || self.pool.get_next()) { |
| 109 |
return None; |
| 110 |
} |
| 111 |
self.first = false; |
| 112 |
} else if self.increment_indices() { |
| 113 |
return None; |
| 114 |
} |
| 115 |
for _ in 0..n { |
| 116 |
if self.increment_indices() { |
| 117 |
return None; |
| 118 |
} |
| 119 |
} |
| 120 |
Some(self.pool.get_at(&self.indices)) |
| 121 |
} |
| 122 |
|
| 123 |
fn size_hint(&self) -> (usize, Option<usize>) { |
| 124 |
let (mut low, mut upp) = self.pool.size_hint(); |
| 125 |
low = remaining_for(low, self.first, &self.indices).unwrap_or(usize::MAX); |
| 126 |
upp = upp.and_then(|upp| remaining_for(upp, self.first, &self.indices)); |
| 127 |
(low, upp) |
| 128 |
} |
| 129 |
|
| 130 |
fn count(self) -> usize { |
| 131 |
let Self { |
| 132 |
indices, |
| 133 |
pool, |
| 134 |
first, |
| 135 |
} = self; |
| 136 |
let n = pool.count(); |
| 137 |
remaining_for(n, first, &indices).unwrap() |
| 138 |
} |
| 139 |
} |
| 140 |
|
| 141 |
impl<I> FusedIterator for CombinationsWithReplacement<I> |
| 142 |
where |
| 143 |
I: Iterator, |
| 144 |
I::Item: Clone, |
| 145 |
{ |
| 146 |
} |
| 147 |
|
| 148 |
/// For a given size `n`, return the count of remaining combinations with replacement or None if it would overflow. |
| 149 |
fn remaining_for(n: usize, first: bool, indices: &[usize]) -> Option<usize> { |
| 150 |
// With a "stars and bars" representation, choose k values with replacement from n values is |
| 151 |
// like choosing k out of k + n − 1 positions (hence binomial(k + n - 1, k) possibilities) |
| 152 |
// to place k stars and therefore n - 1 bars. |
| 153 |
// Example (n=4, k=6): ***|*||** represents [0,0,0,1,3,3]. |
| 154 |
let count = |n: usize, k: usize| { |
| 155 |
let positions = if n == 0 { |
| 156 |
k.saturating_sub(1) |
| 157 |
} else { |
| 158 |
(n - 1).checked_add(k)? |
| 159 |
}; |
| 160 |
checked_binomial(positions, k) |
| 161 |
}; |
| 162 |
let k = indices.len(); |
| 163 |
if first { |
| 164 |
count(n, k) |
| 165 |
} else { |
| 166 |
// The algorithm is similar to the one for combinations *without replacement*, |
| 167 |
// except we choose values *with replacement* and indices are *non-strictly* monotonically sorted. |
| 168 |
|
| 169 |
// The combinations generated after the current one can be counted by counting as follows: |
| 170 |
// - The subsequent combinations that differ in indices[0]: |
| 171 |
// If subsequent combinations differ in indices[0], then their value for indices[0] |
| 172 |
// must be at least 1 greater than the current indices[0]. |
| 173 |
// As indices is monotonically sorted, this means we can effectively choose k values with |
| 174 |
// replacement from (n - 1 - indices[0]), leading to count(n - 1 - indices[0], k) possibilities. |
| 175 |
// - The subsequent combinations with same indices[0], but differing indices[1]: |
| 176 |
// Here we can choose k - 1 values with replacement from (n - 1 - indices[1]) values, |
| 177 |
// leading to count(n - 1 - indices[1], k - 1) possibilities. |
| 178 |
// - (...) |
| 179 |
// - The subsequent combinations with same indices[0..=i], but differing indices[i]: |
| 180 |
// Here we can choose k - i values with replacement from (n - 1 - indices[i]) values: count(n - 1 - indices[i], k - i). |
| 181 |
// Since subsequent combinations can in any index, we must sum up the aforementioned binomial coefficients. |
| 182 |
|
| 183 |
// Below, `n0` resembles indices[i]. |
| 184 |
indices.iter().enumerate().try_fold(0usize, |sum, (i, n0)| { |
| 185 |
sum.checked_add(count(n - 1 - *n0, k - i)?) |
| 186 |
}) |
| 187 |
} |
| 188 |
} |