Repository: rust-itertools/itertools (language: rust)

Issue:
Can the order of Combinations be relied on?
Does `itertools::Combinations` makes any guarantees about the *order* in which it yields combinations?

The docs provide this example:

```rust
use itertools::Itertools;

let it = (1..5).combinations(3);
itertools::assert_equal(it, vec![
    vec![1, 2, 3],
    vec![1, 2, 4],
    vec![1, 3, 4],
    vec![2, 3, 4],
]);
```

Which at a glance is constructing the combinations by "indexing" the iterator `(1..5)` with lexicographically sorted indices `[0, 1, 2]`, `[0, 1, 3]`, `[0, 2, 3]`, and `[1, 2, 3]`.

I am wondering if this is something I can rely on, or if it is an implementation detail that should not be relied on?


Discussion / hints:
I certainly think it is guaranteed. Change it would be a major breaking change to me.

Then why would we change it? It's a worthy question. The only reason I can think of would be performance as it is not that fast: not because of the element order but because yield vectors for each item repeatedly heap-allocate (the performance bottleneck, no doubt). Change the order for performance without having "lending iterators" that would allow us to not heap-allocate each item (but return a reference `&'self [I::Item]`) seems very highly unlikely to me.

Plus, I made a size hint and count methods for it that explicitely require this order to work. And `Powerset` relies on `Combinations` to work.
(Plus, `.tuple_combinations::<(_, _, _)>()` is probably faster (no heap-allocation)).

If we were to change the order nonetheless, I think it should be another method.
To provide more context, I was mainly thinking of `Combinations` in relation to issues like #330. It recommends creating a new combination iterator, but theoretically it *could* be implemented as a major change to the current `Combination` iterator.

Is my understanding correct that itertools wants to avoid those kinds of major changes at all costs?

If so, could we document something like the below? Perhaps on the docs.rs landing page, or on `itertools::Itertools` itself?

> Given deterministic inputs, all iterator adapters currently yield items in a predictable order. This order is considered observable and is therefore intended to remain stable across releases that share the same major version.
Well, as a member, I shared my point of view on this. However, maybe we should include an owner in this discussion for a more definitive/long-term decision.
@jswrenn What do you think on this matter?
No, we don't yet guarantee this. Unless a guarantee is documented, it's not guaranteed.

I'd be willing for us to take on this guarantee, however. Feel free to file a PR adding a note to the documentation!

Fix patch:
diff --git a/src/lib.rs b/src/lib.rs
index f3b6e807d..ecf15effa 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1591,6 +1591,11 @@ pub trait Itertools: Iterator {
     /// let it: TupleCombinations<Range<u32>, (u32, u32, u32)> = (1..5).tuple_combinations();
     /// itertools::assert_equal(it, vec![(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]);
     /// ```
+    ///
+    /// # Guarantees
+    ///
+    /// If the adapted iterator is deterministic,
+    /// this iterator adapter yields items in a reliable order.
     fn tuple_combinations<T>(self) -> TupleCombinations<Self, T>
     where
         Self: Sized + Clone,
@@ -1629,6 +1634,11 @@ pub trait Itertools: Iterator {
     ///     vec![2, 2],
     /// ]);
     /// ```
+    ///
+    /// # Guarantees
+    ///
+    /// If the adapted iterator is deterministic,
+    /// this iterator adapter yields items in a reliable order.
     #[cfg(feature = "use_alloc")]
     fn combinations(self, k: usize) -> Combinations<Self>
     where


Test patch: