Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 1 | use alloc::vec::Vec; |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 2 | use std::fmt; |
| 3 | use std::iter::once; |
| 4 | |
| 5 | use super::lazy_buffer::LazyBuffer; |
| 6 | |
| 7 | /// An iterator adaptor that iterates through all the `k`-permutations of the |
| 8 | /// elements from an iterator. |
| 9 | /// |
| 10 | /// See [`.permutations()`](../trait.Itertools.html#method.permutations) for |
| 11 | /// more information. |
| 12 | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
| 13 | pub struct Permutations<I: Iterator> { |
| 14 | vals: LazyBuffer<I>, |
| 15 | state: PermutationState, |
| 16 | } |
| 17 | |
| 18 | impl<I> Clone for Permutations<I> |
| 19 | where I: Clone + Iterator, |
| 20 | I::Item: Clone, |
| 21 | { |
| 22 | clone_fields!(vals, state); |
| 23 | } |
| 24 | |
| 25 | #[derive(Clone, Debug)] |
| 26 | enum PermutationState { |
| 27 | StartUnknownLen { |
| 28 | k: usize, |
| 29 | }, |
| 30 | OngoingUnknownLen { |
| 31 | k: usize, |
| 32 | min_n: usize, |
| 33 | }, |
| 34 | Complete(CompleteState), |
| 35 | Empty, |
| 36 | } |
| 37 | |
| 38 | #[derive(Clone, Debug)] |
| 39 | enum CompleteState { |
| 40 | Start { |
| 41 | n: usize, |
| 42 | k: usize, |
| 43 | }, |
| 44 | Ongoing { |
| 45 | indices: Vec<usize>, |
| 46 | cycles: Vec<usize>, |
| 47 | } |
| 48 | } |
| 49 | |
| 50 | enum CompleteStateRemaining { |
| 51 | Known(usize), |
| 52 | Overflow, |
| 53 | } |
| 54 | |
| 55 | impl<I> fmt::Debug for Permutations<I> |
| 56 | where I: Iterator + fmt::Debug, |
| 57 | I::Item: fmt::Debug, |
| 58 | { |
| 59 | debug_fmt_fields!(Permutations, vals, state); |
| 60 | } |
| 61 | |
| 62 | pub fn permutations<I: Iterator>(iter: I, k: usize) -> Permutations<I> { |
| 63 | let mut vals = LazyBuffer::new(iter); |
| 64 | |
| 65 | if k == 0 { |
| 66 | // Special case, yields single empty vec; `n` is irrelevant |
| 67 | let state = PermutationState::Complete(CompleteState::Start { n: 0, k: 0 }); |
| 68 | |
| 69 | return Permutations { |
| 70 | vals, |
| 71 | state |
| 72 | }; |
| 73 | } |
| 74 | |
| 75 | let mut enough_vals = true; |
| 76 | |
| 77 | while vals.len() < k { |
| 78 | if !vals.get_next() { |
| 79 | enough_vals = false; |
| 80 | break; |
| 81 | } |
| 82 | } |
| 83 | |
| 84 | let state = if enough_vals { |
| 85 | PermutationState::StartUnknownLen { k } |
| 86 | } else { |
| 87 | PermutationState::Empty |
| 88 | }; |
| 89 | |
| 90 | Permutations { |
| 91 | vals, |
| 92 | state |
| 93 | } |
| 94 | } |
| 95 | |
| 96 | impl<I> Iterator for Permutations<I> |
| 97 | where |
| 98 | I: Iterator, |
| 99 | I::Item: Clone |
| 100 | { |
| 101 | type Item = Vec<I::Item>; |
| 102 | |
| 103 | fn next(&mut self) -> Option<Self::Item> { |
| 104 | self.advance(); |
| 105 | |
| 106 | let &mut Permutations { ref vals, ref state } = self; |
| 107 | |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 108 | match *state { |
| 109 | PermutationState::StartUnknownLen { .. } => panic!("unexpected iterator state"), |
| 110 | PermutationState::OngoingUnknownLen { k, min_n } => { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 111 | let latest_idx = min_n - 1; |
| 112 | let indices = (0..(k - 1)).chain(once(latest_idx)); |
| 113 | |
| 114 | Some(indices.map(|i| vals[i].clone()).collect()) |
| 115 | } |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 116 | PermutationState::Complete(CompleteState::Start { .. }) => None, |
| 117 | PermutationState::Complete(CompleteState::Ongoing { ref indices, ref cycles }) => { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 118 | let k = cycles.len(); |
| 119 | |
| 120 | Some(indices[0..k].iter().map(|&i| vals[i].clone()).collect()) |
| 121 | }, |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 122 | PermutationState::Empty => None |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 123 | } |
| 124 | } |
| 125 | |
| 126 | fn count(self) -> usize { |
| 127 | let Permutations { vals, state } = self; |
| 128 | |
| 129 | fn from_complete(complete_state: CompleteState) -> usize { |
| 130 | match complete_state.remaining() { |
| 131 | CompleteStateRemaining::Known(count) => count, |
| 132 | CompleteStateRemaining::Overflow => { |
| 133 | panic!("Iterator count greater than usize::MAX"); |
| 134 | } |
| 135 | } |
| 136 | } |
| 137 | |
| 138 | match state { |
| 139 | PermutationState::StartUnknownLen { k } => { |
| 140 | let n = vals.len() + vals.it.count(); |
| 141 | let complete_state = CompleteState::Start { n, k }; |
| 142 | |
| 143 | from_complete(complete_state) |
| 144 | } |
| 145 | PermutationState::OngoingUnknownLen { k, min_n } => { |
| 146 | let prev_iteration_count = min_n - k + 1; |
| 147 | let n = vals.len() + vals.it.count(); |
| 148 | let complete_state = CompleteState::Start { n, k }; |
| 149 | |
| 150 | from_complete(complete_state) - prev_iteration_count |
| 151 | }, |
| 152 | PermutationState::Complete(state) => from_complete(state), |
| 153 | PermutationState::Empty => 0 |
| 154 | } |
| 155 | } |
| 156 | |
| 157 | fn size_hint(&self) -> (usize, Option<usize>) { |
| 158 | match self.state { |
| 159 | PermutationState::StartUnknownLen { .. } | |
| 160 | PermutationState::OngoingUnknownLen { .. } => (0, None), // TODO can we improve this lower bound? |
| 161 | PermutationState::Complete(ref state) => match state.remaining() { |
| 162 | CompleteStateRemaining::Known(count) => (count, Some(count)), |
| 163 | CompleteStateRemaining::Overflow => (::std::usize::MAX, None) |
| 164 | } |
| 165 | PermutationState::Empty => (0, Some(0)) |
| 166 | } |
| 167 | } |
| 168 | } |
| 169 | |
| 170 | impl<I> Permutations<I> |
| 171 | where |
| 172 | I: Iterator, |
| 173 | I::Item: Clone |
| 174 | { |
| 175 | fn advance(&mut self) { |
| 176 | let &mut Permutations { ref mut vals, ref mut state } = self; |
| 177 | |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 178 | *state = match *state { |
| 179 | PermutationState::StartUnknownLen { k } => { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 180 | PermutationState::OngoingUnknownLen { k, min_n: k } |
| 181 | } |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 182 | PermutationState::OngoingUnknownLen { k, min_n } => { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 183 | if vals.get_next() { |
| 184 | PermutationState::OngoingUnknownLen { k, min_n: min_n + 1 } |
| 185 | } else { |
| 186 | let n = min_n; |
| 187 | let prev_iteration_count = n - k + 1; |
| 188 | let mut complete_state = CompleteState::Start { n, k }; |
| 189 | |
| 190 | // Advance the complete-state iterator to the correct point |
| 191 | for _ in 0..(prev_iteration_count + 1) { |
| 192 | complete_state.advance(); |
| 193 | } |
| 194 | |
| 195 | PermutationState::Complete(complete_state) |
| 196 | } |
| 197 | } |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 198 | PermutationState::Complete(ref mut state) => { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 199 | state.advance(); |
| 200 | |
| 201 | return; |
| 202 | } |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 203 | PermutationState::Empty => { return; } |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 204 | }; |
| 205 | } |
| 206 | } |
| 207 | |
| 208 | impl CompleteState { |
| 209 | fn advance(&mut self) { |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 210 | *self = match *self { |
| 211 | CompleteState::Start { n, k } => { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 212 | let indices = (0..n).collect(); |
| 213 | let cycles = ((n - k)..n).rev().collect(); |
| 214 | |
| 215 | CompleteState::Ongoing { |
| 216 | cycles, |
| 217 | indices |
| 218 | } |
| 219 | }, |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 220 | CompleteState::Ongoing { ref mut indices, ref mut cycles } => { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 221 | let n = indices.len(); |
| 222 | let k = cycles.len(); |
| 223 | |
| 224 | for i in (0..k).rev() { |
| 225 | if cycles[i] == 0 { |
| 226 | cycles[i] = n - i - 1; |
| 227 | |
| 228 | let to_push = indices.remove(i); |
| 229 | indices.push(to_push); |
| 230 | } else { |
| 231 | let swap_index = n - cycles[i]; |
| 232 | indices.swap(i, swap_index); |
| 233 | |
| 234 | cycles[i] -= 1; |
| 235 | return; |
| 236 | } |
| 237 | } |
| 238 | |
| 239 | CompleteState::Start { n, k } |
| 240 | } |
| 241 | } |
| 242 | } |
| 243 | |
| 244 | fn remaining(&self) -> CompleteStateRemaining { |
| 245 | use self::CompleteStateRemaining::{Known, Overflow}; |
| 246 | |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 247 | match *self { |
| 248 | CompleteState::Start { n, k } => { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 249 | if n < k { |
| 250 | return Known(0); |
| 251 | } |
| 252 | |
| 253 | let count: Option<usize> = (n - k + 1..n + 1).fold(Some(1), |acc, i| { |
| 254 | acc.and_then(|acc| acc.checked_mul(i)) |
| 255 | }); |
| 256 | |
| 257 | match count { |
| 258 | Some(count) => Known(count), |
| 259 | None => Overflow |
| 260 | } |
| 261 | } |
Joel Galenson | 6f79871 | 2021-04-01 17:03:06 -0700 | [diff] [blame] | 262 | CompleteState::Ongoing { ref indices, ref cycles } => { |
Jakub Kotur | a425e55 | 2020-12-21 17:28:15 +0100 | [diff] [blame] | 263 | let mut count: usize = 0; |
| 264 | |
| 265 | for (i, &c) in cycles.iter().enumerate() { |
| 266 | let radix = indices.len() - i; |
| 267 | let next_count = count.checked_mul(radix) |
| 268 | .and_then(|count| count.checked_add(c)); |
| 269 | |
| 270 | count = match next_count { |
| 271 | Some(count) => count, |
| 272 | None => { return Overflow; } |
| 273 | }; |
| 274 | } |
| 275 | |
| 276 | Known(count) |
| 277 | } |
| 278 | } |
| 279 | } |
| 280 | } |