5 use super::lazy_buffer
::LazyBuffer
;
7 /// An iterator adaptor that iterates through all the `k`-permutations of the
8 /// elements from an iterator.
10 /// See [`.permutations()`](crate::Itertools::permutations) for
12 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
13 pub struct Permutations
<I
: Iterator
> {
15 state
: PermutationState
,
18 impl<I
> Clone
for Permutations
<I
>
19 where I
: Clone
+ Iterator
,
22 clone_fields
!(vals
, state
);
25 #[derive(Clone, Debug)]
26 enum PermutationState
{
34 Complete(CompleteState
),
38 #[derive(Clone, Debug)]
50 enum CompleteStateRemaining
{
55 impl<I
> fmt
::Debug
for Permutations
<I
>
56 where I
: Iterator
+ fmt
::Debug
,
59 debug_fmt_fields
!(Permutations
, vals
, state
);
62 pub fn permutations
<I
: Iterator
>(iter
: I
, k
: usize) -> Permutations
<I
> {
63 let mut vals
= LazyBuffer
::new(iter
);
66 // Special case, yields single empty vec; `n` is irrelevant
67 let state
= PermutationState
::Complete(CompleteState
::Start { n: 0, k: 0 }
);
75 let mut enough_vals
= true;
77 while vals
.len() < k
{
84 let state
= if enough_vals
{
85 PermutationState
::StartUnknownLen { k }
87 PermutationState
::Empty
96 impl<I
> Iterator
for Permutations
<I
>
101 type Item
= Vec
<I
::Item
>;
103 fn next(&mut self) -> Option
<Self::Item
> {
106 let &mut Permutations { ref vals, ref state }
= self;
109 PermutationState
::StartUnknownLen { .. }
=> panic
!("unexpected iterator state"),
110 PermutationState
::OngoingUnknownLen { k, min_n }
=> {
111 let latest_idx
= min_n
- 1;
112 let indices
= (0..(k
- 1)).chain(once(latest_idx
));
114 Some(indices
.map(|i
| vals
[i
].clone()).collect())
116 PermutationState
::Complete(CompleteState
::Start { .. }
) => None
,
117 PermutationState
::Complete(CompleteState
::Ongoing { ref indices, ref cycles }
) => {
118 let k
= cycles
.len();
120 Some(indices
[0..k
].iter().map(|&i
| vals
[i
].clone()).collect())
122 PermutationState
::Empty
=> None
126 fn count(self) -> usize {
127 let Permutations { vals, state }
= self;
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");
139 PermutationState
::StartUnknownLen { k }
=> {
140 let n
= vals
.len() + vals
.it
.count();
141 let complete_state
= CompleteState
::Start { n, k }
;
143 from_complete(complete_state
)
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 }
;
150 from_complete(complete_state
) - prev_iteration_count
152 PermutationState
::Complete(state
) => from_complete(state
),
153 PermutationState
::Empty
=> 0
157 fn size_hint(&self) -> (usize, Option
<usize>) {
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
)
165 PermutationState
::Empty
=> (0, Some(0))
170 impl<I
> Permutations
<I
>
175 fn advance(&mut self) {
176 let &mut Permutations { ref mut vals, ref mut state }
= self;
178 *state
= match *state
{
179 PermutationState
::StartUnknownLen { k }
=> {
180 PermutationState
::OngoingUnknownLen { k, min_n: k }
182 PermutationState
::OngoingUnknownLen { k, min_n }
=> {
184 PermutationState
::OngoingUnknownLen { k, min_n: min_n + 1 }
187 let prev_iteration_count
= n
- k
+ 1;
188 let mut complete_state
= CompleteState
::Start { n, k }
;
190 // Advance the complete-state iterator to the correct point
191 for _
in 0..(prev_iteration_count
+ 1) {
192 complete_state
.advance();
195 PermutationState
::Complete(complete_state
)
198 PermutationState
::Complete(ref mut state
) => {
203 PermutationState
::Empty
=> { return; }
209 fn advance(&mut self) {
210 *self = match *self {
211 CompleteState
::Start { n, k }
=> {
212 let indices
= (0..n
).collect();
213 let cycles
= ((n
- k
)..n
).rev().collect();
215 CompleteState
::Ongoing
{
220 CompleteState
::Ongoing { ref mut indices, ref mut cycles }
=> {
221 let n
= indices
.len();
222 let k
= cycles
.len();
224 for i
in (0..k
).rev() {
226 cycles
[i
] = n
- i
- 1;
228 let to_push
= indices
.remove(i
);
229 indices
.push(to_push
);
231 let swap_index
= n
- cycles
[i
];
232 indices
.swap(i
, swap_index
);
239 CompleteState
::Start { n, k }
244 fn remaining(&self) -> CompleteStateRemaining
{
245 use self::CompleteStateRemaining
::{Known, Overflow}
;
248 CompleteState
::Start { n, k }
=> {
253 let count
: Option
<usize> = (n
- k
+ 1..n
+ 1).fold(Some(1), |acc
, i
| {
254 acc
.and_then(|acc
| acc
.checked_mul(i
))
258 Some(count
) => Known(count
),
262 CompleteState
::Ongoing { ref indices, ref cycles }
=> {
263 let mut count
: usize = 0;
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
));
270 count
= match next_count
{
271 Some(count
) => count
,
272 None
=> { return Overflow; }