Repository: rust-itertools/itertools (rust)

Issue:
Permutation
Hi,

Thank you for making this awesome library. It would be great if you can support [permutate function like in python](https://docs.python.org/2/library/itertools.html#itertools.permutations)

Thanks!

Pull request description:
Permutations
Fixes #285.

This implementation is based on the Python implementation specified in the issue. There are quite a few points which should be considered.

## Method name, _k_-less form

The adaptor function is called `permutations`, for user familiarity. However, since the size of the output can be specified, a more mathematically accurate name would probably be `k_permutations`. Perhaps two adaptor functions would be better: `.k_permutations(k: usize)` and `.permutations()` (which just sets `k = vals.len()`)?

## Item value ordering/distinctness

Input items are not inspected in any way; they are treated purely by their initial index. This means that:

  1. Permutations are yielded in lexicographical order of the index, not by any `PartialOrd` implementation of the items.
  2. Identical items will not be detected, and will result in some identical permutations.

__1__ can be achieved by the user by collecting-and-sorting their input.

__2__ is a little trickier, but can be achieved by filtering the output. However, I think there is a more efficient algorithm to avoid duplicated. Maybe we should provide this option?

## Permutations from source buffer/indices

In addition to the iterator adaptor, I've added `Permutations::from_vals`, to create directly from a `Vec` or a slice. This saves some cloning compared to using `source.[into_]iter().permutations(k)`.

There is also `Permutations::new(n, k)`, which is functionally equivalent to `(0..n).permutations(k)`, but a little faster (about 0.6x the run time).

But perhaps you would consider these unnecessary additions to the API?

## `PermutationSource` trait

These different implementations (from `Vec`/slice/just indices) are achieved with the trait `PermutationSource`. It's visible to the user to implement for other structures if they wish, but this is probably of limited value. There's not much harm in allowing the user to access it, but again, maybe it's just API bloat. (or a future breaking change when it's removed/changed...)

On the other hand, perhaps there are other places in the library which could benefit from taking a source generically? Any adaptor where input elements are used more than once will need to store them, and it might be more efficient to allow users to supply the memory directly. This could be done in another PR.

For completeness, I also made full implementations of the three variations, without the trait, for benchmarking. The pure-indices implementation is about 10% slower using the trait, but `Vec`s and slices are unaffected (or even a little faster...).

## `Combinations` changes

I've made small changes to the `Combinations` documentation to match `Permutations` - most significantly, replacing the letter `n` with `k`. I've also changed all uses of the variable `n` to `k` in the implementation... but maybe this is considered commit noise :)

There are some other potential changes which would bring `Combinations` and `Permutations` more in line with one another.

As mentioned above, `Combinations` might benefit from using a `_____Source` trait, to allow direct memory buffers.

My `Permutations` implementations doesn't make use of `LazyBuffer`. Perhaps the buffer is useful for iterators which never complete, and have a very small `k` value. Has any benchmarking been done?

Either way, it makes sense for both adaptors to either use or not use `LazyBuffer`. Maybe it could be integrated into the `_______Source` trait if it's useful?

---

Let me know what you think when you have the chance. (Sorry for submitting two reasonably big PRs at once. I hope you get a chance to go through it all eventually!)

Patch:
diff --git a/benches/bench1.rs b/benches/bench1.rs
index 7e328da..f035b99 100644
--- a/benches/bench1.rs
+++ b/benches/bench1.rs
@@ -7,10 +7,11 @@ use test::{black_box};
 use itertools::Itertools;
 
 use itertools::free::cloned;
+use itertools::Permutations;
 
 use std::iter::repeat;
 use std::cmp;
-use std::ops::Add;
+use std::ops::{Add, Range};
 
 mod extra;
 
@@ -762,3 +763,44 @@ fn all_equal_default(b: &mut test::Bencher) {
 
     b.iter(|| xs.iter().dedup().nth(1).is_none())
 }
+
+const PERM_COUNT: usize = 6;
+
+#[bench]
+fn permutations_iter(b: &mut test::Bencher) {
+    struct NewIterator(Range<usize>);
+
+    impl Iterator for NewIterator {
+        type Item = usize;
+
+        fn next(&mut self) -> Option<Self::Item> {
+            self.0.next()
+        }
+    }
+
+    b.iter(|| {
+        for _ in NewIterator(0..PERM_COUNT).permutations(PERM_COUNT) {
+
+        }
+    })
+}
+
+#[bench]
+fn permutations_range(b: &mut test::Bencher) {
+    b.iter(|| {
+        for _ in (0..PERM_COUNT).permutations(PERM_COUNT) {
+
+        }
+    })
+}
+
+#[bench]
+fn permutations_slice(b: &mut test::Bencher) {
+    let v = (0..PERM_COUNT).collect_vec();
+
+    b.iter(|| {
+        for _ in v.as_slice().iter().permutations(PERM_COUNT) {
+
+        }
+    })
+}
diff --git a/src/combinations.rs b/src/combinations.rs
index 95f2bef..61833ce 100644
--- a/src/combinations.rs
+++ b/src/combinations.rs
@@ -2,12 +2,12 @@ use std::fmt;
 
 use super::lazy_buffer::LazyBuffer;
 
-/// An iterator to iterate through all the `n`-length combinations in an iterator.
+/// An iterator to iterate through all the `k`-length combinations in an iterator.
 ///
 /// See [`.combinations()`](../trait.Itertools.html#method.combinations) for more information.
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 pub struct Combinations<I: Iterator> {
-    n: usize,
+    k: usize,
     indices: Vec<usize>,
     pool: LazyBuffer<I>,
     first: bool,
@@ -17,27 +17,27 @@ impl<I> fmt::Debug for Combinations<I>
     where I: Iterator + fmt::Debug,
           I::Item: fmt::Debug,
 {
-    debug_fmt_fields!(Combinations, n, indices, pool, first);
+    debug_fmt_fields!(Combinations, k, indices, pool, first);
 }
 
 /// Create a new `Combinations` from a clonable iterator.
-pub fn combinations<I>(iter: I, n: usize) -> Combinations<I>
+pub fn combinations<I>(iter: I, k: usize) -> Combinations<I>
     where I: Iterator
 {
-    let mut indices: Vec<usize> = Vec::with_capacity(n);
-    for i in 0..n {
+    let mut indices: Vec<usize> = Vec::with_capacity(k);
+    for i in 0..k {
         indices.push(i);
     }
     let mut pool: LazyBuffer<I> = LazyBuffer::new(iter);
 
-    for _ in 0..n {
+    for _ in 0..k {
         if !pool.get_next() {
             break;
         }
     }
 
     Combinations {
-        n: n,
+        k: k,
         indices: indices,
         pool: pool,
         first: true,
@@ -52,18 +52,18 @@ impl<I> Iterator for Combinations<I>
     fn next(&mut self) -> Option<Self::Item> {
         let mut pool_len = self.pool.len();
         if self.pool.is_done() {
-            if pool_len == 0 || self.n > pool_len {
+            if pool_len == 0 || self.k > pool_len {
                 return None;
             }
         }
 
         if self.first {
             self.first = false;
-        } else if self.n == 0 {
+        } else if self.k == 0 {
             return None;
         } else {
             // Scan from the end, looking for an index to increment
-            let mut i: usize = self.n - 1;
+            let mut i: usize = self.k - 1;
 
             // Check if we need to consume more from the iterator
             if self.indices[i] == pool_len - 1 && !self.pool.is_done() {
@@ -72,7 +72,7 @@ impl<I> Iterator for Combinations<I>
                 }
             }
 
-            while self.indices[i] == i + pool_len - self.n {
+            while self.indices[i] == i + pool_len - self.k {
                 if i > 0 {
                     i -= 1;
                 } else {
@@ -84,14 +84,14 @@ impl<I> Iterator for Combinations<I>
             // Increment index, and reset the ones to its right
             self.indices[i] += 1;
             let mut j = i + 1;
-            while j < self.n {
+            while j < self.k {
                 self.indices[j] = self.indices[j - 1] + 1;
                 j += 1;
             }
         }
 
         // Create result vector based on the indices
-        let mut result = Vec::with_capacity(self.n);
+        let mut result = Vec::with_capacity(self.k);
         for i in self.indices.iter() {
             result.push(self.pool[*i].clone());
         }
diff --git a/src/combinations_with_replacement.rs b/src/combinations_with_replacement.rs
index 7af6d4e..499ccf7 100644
--- a/src/combinations_with_replacement.rs
+++ b/src/combinations_with_replacement.rs
@@ -11,7 +11,7 @@ where
     I: Iterator,
     I::Item: Clone,
 {
-    n: usize,
+    k: usize,
     indices: Vec<usize>,
     // The current known max index value. This increases as pool grows.
     max_index: usize,
@@ -24,7 +24,7 @@ where
     I: Iterator + fmt::Debug,
     I::Item: fmt::Debug + Clone,
 {
-    debug_fmt_fields!(Combinations, n, indices, max_index, pool, first);
+    debug_fmt_fields!(Combinations, k, indices, max_index, pool, first);
 }
 
 impl<I> CombinationsWithReplacement<I>
@@ -39,16 +39,16 @@ where
 }
 
 /// Create a new `CombinationsWithReplacement` from a clonable iterator.
-pub fn combinations_with_replacement<I>(iter: I, n: usize) -> CombinationsWithReplacement<I>
+pub fn combinations_with_replacement<I>(iter: I, k: usize) -> CombinationsWithReplacement<I>
 where
     I: Iterator,
     I::Item: Clone,
 {
-    let indices: Vec<usize> = vec![0; n];
+    let indices: Vec<usize> = vec![0; k];
     let pool: LazyBuffer<I> = LazyBuffer::new(iter);
 
     CombinationsWithReplacement {
-        n,
+        k,
         indices,
         max_index: 0,
         pool: pool,
@@ -66,7 +66,7 @@ where
         // If this is the first iteration, return early
         if self.first {
             // In empty edge cases, stop iterating immediately
-            return if self.n == 0 || self.pool.is_done() {
+            return if self.k == 0 || self.pool.is_done() {
                 None
             // Otherwise, yield the initial state
             } else {
diff --git a/src/lazy_buffer.rs b/src/lazy_buffer.rs
index b9bf421..09a8cd9 100644
--- a/src/lazy_buffer.rs
+++ b/src/lazy_buffer.rs
@@ -2,7 +2,7 @@ use std::ops::Index;
 
 #[derive(Debug, Clone)]
 pub struct LazyBuffer<I: Iterator> {
-    it: I,
+    pub it: I,
     done: bool,
     buffer: Vec<I::Item>,
 }
@@ -54,14 +54,15 @@ where
     }
 }
 
-impl<I> Index<usize> for LazyBuffer<I>
+impl<I, J> Index<J> for LazyBuffer<I>
 where
     I: Iterator,
     I::Item: Sized,
+    Vec<I::Item>: Index<J>
 {
-    type Output = I::Item;
+    type Output = <Vec<I::Item> as Index<J>>::Output;
 
-    fn index<'b>(&'b self, _index: usize) -> &'b I::Item {
+    fn index(&self, _index: J) -> &Self::Output {
         self.buffer.index(_index)
     }
 }
diff --git a/src/lib.rs b/src/lib.rs
index 1e0af6d..5f3eb72 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -117,6 +117,8 @@ pub mod structs {
     pub use multipeek_impl::MultiPeek;
     pub use pad_tail::PadUsing;
     pub use peeking_take_while::PeekingTakeWhile;
+    #[cfg(feature = "use_std")]
+    pub use permutations::Permutations;
     pub use process_results_impl::ProcessResults;
     #[cfg(feature = "use_std")]
     pub use put_back_n_impl::PutBackN;
@@ -182,6 +184,8 @@ mod minmax;
 mod multipeek_impl;
 mod pad_tail;
 mod peeking_take_while;
+#[cfg(feature = "use_std")]
+mod permutations;
 mod process_results_impl;
 #[cfg(feature = "use_std")]
 mod put_back_n_impl;
@@ -1135,7 +1139,7 @@ pub trait Itertools : Iterator {
         adaptors::tuple_combinations(self)
     }
 
-    /// Return an iterator adaptor that iterates over the `n`-length combinations of
+    /// Return an iterator adaptor that iterates over the `k`-length combinations of
     /// the elements from an iterator.
     ///
     /// Iterator element type is `Vec<Self::Item>`. The iterator produces a new Vec per iteration,
@@ -1150,7 +1154,7 @@ pub trait Itertools : Iterator {
     ///     vec![1, 2, 4],
     ///     vec![1, 3, 4],
     ///     vec![2, 3, 4],
-    ///     ]);
+    /// ]);
     /// ```
     ///
     /// Note: Combinations does not take into account the equality of the iterated values.
@@ -1164,16 +1168,15 @@ pub trait Itertools : Iterator {
     ///     vec![2, 2],
     /// ]);
     /// ```
-    ///
     #[cfg(feature = "use_std")]
-    fn combinations(self, n: usize) -> Combinations<Self>
+    fn combinations(self, k: usize) -> Combinations<Self>
         where Self: Sized,
               Self::Item: Clone
     {
-        combinations::combinations(self, n)
+        combinations::combinations(self, k)
     }
 
-    /// Return an iterator that iterates over the `n`-length combinations of
+    /// Return an iterator that iterates over the `k`-length combinations of
     /// the elements from an iterator, with replacement.
     ///
     /// Iterator element type is `Vec<Self::Item>`. The iterator produces a new Vec per iteration,
@@ -1190,15 +1193,60 @@ pub trait Itertools : Iterator {
     ///     vec![2, 2],
     ///     vec![2, 3],
     ///     vec![3, 3],
-    ///     ]);
+    /// ]);
     /// ```
     #[cfg(feature = "use_std")]
-    fn combinations_with_replacement(self, n: usize) -> CombinationsWithReplacement<Self>
+    fn combinations_with_replacement(self, k: usize) -> CombinationsWithReplacement<Self>
     where
         Self: Sized,
         Self::Item: Clone,
     {
-        combinations_with_replacement::combinations_with_replacement(self, n)
+        combinations_with_replacement::combinations_with_replacement(self, k)
+    }
+
+    /// Return an iterator adaptor that iterates over all k-permutations of the
+    /// elements from an iterator.
+    ///
+    /// Iterator element type is `Vec<Self::Item>` with length `k`. The iterator
+    /// produces a new Vec per iteration, and clones the iterator elements.
+    ///
+    /// If `k` is greater than the length of the input iterator, the resultant
+    /// iterator adaptor will be empty.
+    ///
+    /// ```
+    /// use itertools::Itertools;
+    ///
+    /// let perms = (5..8).permutations(2);
+    /// itertools::assert_equal(perms, vec![
+    ///     vec![5, 6],
+    ///     vec![5, 7],
+    ///     vec![6, 5],
+    ///     vec![6, 7],
+    ///     vec![7, 5],
+    ///     vec![7, 6],
+    /// ]);
+    /// ```
+    ///
+    /// Note: Permutations does not take into account the equality of the iterated values.
+    ///
+    /// ```
+    /// use itertools::Itertools;
+    ///
+    /// let it = vec![2, 2].into_iter().permutations(2);
+    /// itertools::assert_equal(it, vec![
+    ///     vec![2, 2], // Note: these are the same
+    ///     vec![2, 2], // Note: these are the same
+    /// ]);
+    /// ```
+    ///
+    /// Note: The source iterator is collected lazily, and will not be
+    /// re-iterated if the permutations adaptor is completed and re-iterated.
+    #[cfg(feature = "use_std")]
+    fn permutations(self, k: usize) -> Permutations<Self>
+        where Self: Sized,
+              Self::Item: Clone
+    {
+        permutations::permutations(self, k)
     }
 
     /// Return an iterator adaptor that pads the sequence to a minimum length of
diff --git a/src/permutations.rs b/src/permutations.rs
new file mode 100644
index 0000000..a942337
--- /dev/null
+++ b/src/permutations.rs
@@ -0,0 +1,272 @@
+use std::fmt;
+use std::iter::once;
+
+use super::lazy_buffer::LazyBuffer;
+
+/// An iterator adaptor that iterates through all the `k`-permutations of the
+/// elements from an iterator.
+///
+/// See [`.permutations()`](../trait.Itertools.html#method.permutations) for
+/// more information.
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
+pub struct Permutations<I: Iterator> {
+    vals: LazyBuffer<I>,
+    state: PermutationState,
+}
+
+#[derive(Debug)]
+enum PermutationState {
+    StartUnknownLen {
+        k: usize,
+    },
+    OngoingUnknownLen {
+        k: usize,
+        min_n: usize,
+    },
+    Complete(CompleteState),
+    Empty,
+}
+
+#[derive(Debug)]
+enum CompleteState {
+    Start {
+        n: usize,
+        k: usize,
+    },
+    Ongoing {
+        indices: Vec<usize>,
+        cycles: Vec<usize>,
+    }
+}
+
+enum CompleteStateRemaining {
+    Known(usize),
+    Overflow,
+}
+
+impl<I> fmt::Debug for Permutations<I>
+    where I: Iterator + fmt::Debug,
+          I::Item: fmt::Debug,
+{
+    debug_fmt_fields!(Permutations, vals, state);
+}
+
+pub fn permutations<I: Iterator>(iter: I, k: usize) -> Permutations<I> {
+    let mut vals = LazyBuffer::new(iter);
+
+    if k == 0 {
+        // Special case, yields single empty vec; `n` is irrelevant
+        let state = PermutationState::Complete(CompleteState::Start { n: 0, k: 0 });
+
+        return Permutations {
+            vals,
+            state
+        };
+    }
+
+    let mut enough_vals = true;
+
+    while vals.len() < k {
+        if !vals.get_next() {
+            enough_vals = false;
+            break;
+        }
+    }
+
+    let state = if enough_vals {
+        PermutationState::StartUnknownLen { k }
+    } else {
+        PermutationState::Empty
+    };
+
+    Permutations {
+        vals,
+        state
+    }
+}
+
+impl<I> Iterator for Permutations<I>
+where
+    I: Iterator,
+    I::Item: Clone
+{
+    type Item = Vec<I::Item>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.advance();
+
+        let &mut Permutations { ref vals, ref state } = self;
+
+        match state {
+            &PermutationState::StartUnknownLen { .. } => panic!("unexpected iterator state"),
+            &PermutationState::OngoingUnknownLen { k, min_n } => {
+                let latest_idx = min_n - 1;
+                let indices = (0..(k - 1)).chain(once(latest_idx));
+
+                Some(indices.map(|i| vals[i].clone()).collect())
+            }
+            &PermutationState::Complete(CompleteState::Start { .. }) => None,
+            &PermutationState::Complete(CompleteState::Ongoing { ref indices, ref cycles }) => {
+                let k = cycles.len();
+
+                Some(indices[0..k].iter().map(|&i| vals[i].clone()).collect())
+            },
+            &PermutationState::Empty => None
+        }
+    }
+
+    fn count(self) -> usize {
+        let Permutations { vals, state } = self;
+
+        fn from_complete(complete_state: CompleteState) -> usize {
+            match complete_state.remaining() {
+                CompleteStateRemaining::Known(count) => count,
+                CompleteStateRemaining::Overflow => {
+                    panic!("Iterator count greater than usize::MAX");
+                }
+            }
+        }
+
+        match state {
+            PermutationState::StartUnknownLen { k } => {
+                let n = vals.len() + vals.it.count();
+                let complete_state = CompleteState::Start { n, k };
+
+                from_complete(complete_state)
+            }
+            PermutationState::OngoingUnknownLen { k, min_n } => {
+                let prev_iteration_count = min_n - k + 1;
+                let n = vals.len() + vals.it.count();
+                let complete_state = CompleteState::Start { n, k };
+
+                from_complete(complete_state) - prev_iteration_count
+            },
+            PermutationState::Complete(state) => from_complete(state),
+            PermutationState::Empty => 0
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        match self.state {
+            PermutationState::StartUnknownLen { .. } |
+            PermutationState::OngoingUnknownLen { .. } => (0, None), // TODO can we improve this lower bound?
+            PermutationState::Complete(ref state) => match state.remaining() {
+                CompleteStateRemaining::Known(count) => (count, Some(count)),
+                CompleteStateRemaining::Overflow => (::std::usize::MAX, None)
+            }
+            PermutationState::Empty => (0, Some(0))
+        }
+    }
+}
+
+impl<I> Permutations<I>
+where
+    I: Iterator,
+    I::Item: Clone
+{
+    fn advance(&mut self) {
+        let &mut Permutations { ref mut vals, ref mut state } = self;
+
+        *state = match state {
+            &mut PermutationState::StartUnknownLen { k } => {
+                PermutationState::OngoingUnknownLen { k, min_n: k }
+            }
+            &mut PermutationState::OngoingUnknownLen { k, min_n } => {
+                if vals.get_next() {
+                    PermutationState::OngoingUnknownLen { k, min_n: min_n + 1 }
+                } else {
+                    let n = min_n;
+                    let prev_iteration_count = n - k + 1;
+                    let mut complete_state = CompleteState::Start { n, k };
+
+                    // Advance the complete-state iterator to the correct point
+                    for _ in 0..(prev_iteration_count + 1) {
+                        complete_state.advance();
+                    }
+
+                    PermutationState::Complete(complete_state)
+                }
+            }
+            &mut PermutationState::Complete(ref mut state) => {
+                state.advance();
+
+                return;
+            }
+            &mut PermutationState::Empty => { return; }
+        };
+    }
+}
+
+impl CompleteState {
+    fn advance(&mut self) {
+        *self = match self {
+            &mut CompleteState::Start { n, k } => {
+                let indices = (0..n).collect();
+                let cycles = ((n - k)..n).rev().collect();
+
+                CompleteState::Ongoing {
+                    cycles,
+                    indices
+                }
+            },
+            &mut CompleteState::Ongoing { ref mut indices, ref mut cycles } => {
+                let n = indices.len();
+                let k = cycles.len();
+
+                for i in (0..k).rev() {
+                    if cycles[i] == 0 {
+                        cycles[i] = n - i - 1;
+
+                        let to_push = indices.remove(i);
+                        indices.push(to_push);
+                    } else {
+                        let swap_index = n - cycles[i];
+                        indices.swap(i, swap_index);
+
+                        cycles[i] -= 1;
+                        return;
+                    }
+                }
+
+                CompleteState::Start { n, k }
+            }
+        }
+    }
+
+    fn remaining(&self) -> CompleteStateRemaining {
+        use self::CompleteStateRemaining::{Known, Overflow};
+
+        match self {
+            &CompleteState::Start { n, k } => {
+                if n < k {
+                    return Known(0);
+                }
+
+                let count: Option<usize> = (n - k + 1..n + 1).fold(Some(1), |acc, i| {
+                    acc.and_then(|acc| acc.checked_mul(i))
+                });
+
+                match count {
+                    Some(count) => Known(count),
+                    None => Overflow
+                }
+            }
+            &CompleteState::Ongoing { ref indices, ref cycles } => {
+                let mut count: usize = 0;
+
+                for (i, &c) in cycles.iter().enumerate() {
+                    let radix = indices.len() - i;
+                    let next_count = count.checked_mul(radix)
+                        .and_then(|count| count.checked_add(c));
+
+                    count = match next_count {
+                        Some(count) => count,
+                        None => { return Overflow; }
+                    };
+                }
+
+                Known(count)
+            }
+        }
+    }
+}
\ No newline at end of file


Test patch:
diff --git a/tests/adaptors_no_collect.rs b/tests/adaptors_no_collect.rs
new file mode 100644
index 0000000..4da6fcf
--- /dev/null
+++ b/tests/adaptors_no_collect.rs
@@ -0,0 +1,49 @@
+extern crate itertools;
+
+use itertools::Itertools;
+
+struct PanickingCounter {
+    curr: usize,
+    max: usize,
+}
+
+impl Iterator for PanickingCounter {
+    type Item = ();
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.curr += 1;
+
+        if self.curr == self.max {
+            panic!(
+                "Input iterator reached maximum of {} suggesting collection by adaptor",
+                self.max
+            );
+        }
+
+        Some(())
+    }
+}
+
+fn no_collect_test<A, T>(to_adaptor: T)
+    where A: Iterator, T: Fn(PanickingCounter) -> A
+{
+    let counter = PanickingCounter { curr: 0, max: 10_000 };
+    let adaptor = to_adaptor(counter);
+
+    for _ in adaptor.take(5) {}
+}
+
+#[test]
+fn permutations_no_collect() {
+    no_collect_test(|iter| iter.permutations(5))
+}
+
+#[test]
+fn combinations_no_collect() {
+    no_collect_test(|iter| iter.combinations(5))
+}
+
+#[test]
+fn combinations_with_replacement_no_collect() {
+    no_collect_test(|iter| iter.combinations_with_replacement(5))
+}
\ No newline at end of file
diff --git a/tests/quick.rs b/tests/quick.rs
index 95c1ba8..7767447 100644
--- a/tests/quick.rs
+++ b/tests/quick.rs
@@ -12,7 +12,8 @@ use std::default::Default;
 
 use quickcheck as qc;
 use std::ops::Range;
-use std::cmp::Ordering;
+use std::cmp::{max, min, Ordering};
+use std::collections::HashSet;
 use itertools::Itertools;
 use itertools::{
     multizip,
@@ -248,6 +249,43 @@ impl<HK> qc::Arbitrary for ShiftRange<HK>
     }
 }
 
+fn correct_count<I, F>(get_it: F) -> bool
+where
+    I: Iterator,
+    F: Fn() -> I
+{
+    let mut counts = vec![get_it().count()];
+
+    'outer: loop {
+        let mut it = get_it();
+
+        for _ in 0..(counts.len() - 1) {
+            if let None = it.next() {
+                panic!("Iterator shouldn't be finished, may not be deterministic");
+            }
+        }
+
+        if let None = it.next() {
+            break 'outer;
+        }
+
+        counts.push(it.count());
+    }
+
+    let total_actual_count = counts.len() - 1;
+
+    for (i, returned_count) in counts.into_iter().enumerate() {
+        let actual_count = total_actual_count - i;
+        if actual_count != returned_count {
+            println!("Total iterations: {} True count: {} returned count: {}", i, actual_count, returned_count);
+
+            return false;
+        }
+    }
+
+    true
+}
+
 fn correct_size_hint<I: Iterator>(mut it: I) -> bool {
     // record size hint at each iteration
     let initial_hint = it.size_hint();
@@ -625,6 +663,88 @@ quickcheck! {
         let size = a.clone().count();
         a.collect_tuple::<(_, _, _)>().is_some() == (size == 3)
     }
+
+    fn correct_permutations(vals: HashSet<i32>, k: usize) -> () {
+        // Test permutations only on iterators of distinct integers, to prevent
+        // false positives.
+
+        const MAX_N: usize = 5;
+
+        let n = min(vals.len(), MAX_N);
+        let vals: HashSet<i32> = vals.into_iter().take(n).collect();
+
+        let perms = vals.iter().permutations(k);
+
+        let mut actual = HashSet::new();
+
+        for perm in perms {
+            assert_eq!(perm.len(), k);
+
+            let all_items_valid = perm.iter().all(|p| vals.contains(p));
+            assert!(all_items_valid, "perm contains value not from input: {:?}", perm);
+
+            // Check that all perm items are distinct
+            let distinct_len = {
+                let perm_set: HashSet<_> = perm.iter().collect();
+                perm_set.len()
+            };
+            assert_eq!(perm.len(), distinct_len);
+
+            // Check that the perm is new
+            assert!(actual.insert(perm.clone()), "perm already encountered: {:?}", perm);
+        }
+    }
+
+    fn permutations_lexic_order(a: usize, b: usize) -> () {
+        let a = a % 6;
+        let b = b % 6;
+
+        let n = max(a, b);
+        let k = min (a, b);
+
+        let expected_first: Vec<usize> = (0..k).collect();
+        let expected_last: Vec<usize> = ((n - k)..n).rev().collect();
+
+        let mut perms = (0..n).permutations(k);
+
+        let mut curr_perm = match perms.next() {
+            Some(p) => p,
+            None => { return; }
+        };
+
+        assert_eq!(expected_first, curr_perm);
+
+        while let Some(next_perm) = perms.next() {
+            assert!(
+                next_perm > curr_perm,
+                "next perm isn't greater-than current; next_perm={:?} curr_perm={:?} n={}",
+                next_perm, curr_perm, n
+            );
+
+            curr_perm = next_perm;
+        }
+
+        assert_eq!(expected_last, curr_perm);
+
+    }
+
+    fn permutations_count(n: usize, k: usize) -> bool {
+        let n = n % 6;
+
+        correct_count(|| (0..n).permutations(k))
+    }
+
+    fn permutations_size(a: Iter<i32>, k: usize) -> bool {
+        correct_size_hint(a.take(5).permutations(k))
+    }
+
+    fn permutations_k0_yields_once(n: usize) -> () {
+        let k = 0;
+        let expected: Vec<Vec<usize>> = vec![vec![]];
+        let actual = (0..n).permutations(k).collect_vec();
+
+        assert_eq!(expected, actual);
+    }
 }
 
 quickcheck! {
diff --git a/tests/test_std.rs b/tests/test_std.rs
index 054ac94..4f48c55 100644
--- a/tests/test_std.rs
+++ b/tests/test_std.rs
@@ -585,12 +585,6 @@ fn combinations() {
     it::assert_equal((0..1).combinations(1), vec![vec![0]]);
     it::assert_equal((0..2).combinations(1), vec![vec![0], vec![1]]);
     it::assert_equal((0..2).combinations(2), vec![vec![0, 1]]);
-
-    // Infinite iterator should work, even though it doesn't really make sense
-    let mut infinite_combinations = (0..).combinations(2);
-    assert_eq!(infinite_combinations.next(), Some(vec![0, 1]));
-    assert_eq!(infinite_combinations.next(), Some(vec![0, 2]));
-    assert_eq!(infinite_combinations.next(), Some(vec![0, 3]));
 }
 
 #[test]
@@ -633,12 +627,6 @@ fn combinations_with_replacement() {
         (0..0).combinations_with_replacement(2),
         <Vec<Vec<_>>>::new(),
     );
-
-    // Infinite iterator should work, even though it doesn't really make sense
-    let mut infinite_combinations = (0..).combinations_with_replacement(2);
-    assert_eq!(infinite_combinations.next(), Some(vec![0, 0]));
-    assert_eq!(infinite_combinations.next(), Some(vec![0, 1]));
-    assert_eq!(infinite_combinations.next(), Some(vec![0, 2]));
 }
 
 #[test]