Can the order of Combinations be relied on?

[ryanavella]

Does itertools::Combinations makes any guarantees about the order in which it yields combinations?

The docs provide this example:

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?

[Philippe-Cholet]

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.

[ryanavella]

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.

[Philippe-Cholet]

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?

[jswrenn]

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!