Faster skipping combinations with nth in Combinations

[lorepozo]

In impl Iterator for Combinations, only the next method is defined. It shouldn't be too difficult to permit skipping through combinations, so that vec![1, 2, 3, 4].into_iter().combinations(2).nth(4) doesn't unnecessarily waste time going through the first four iterations just to get to the fifth.

To do this, Combinations would need a field that kept track of how many iterations have already been made (this may replace the first bool field), its indices field would need to be settable immediately depending on the iteration number, and nth should thus be defined (save some pool-filling).

[kinto-b]

@Philippe-Cholet Hi there, a fairly efficient way to implement this would be to use the combinatorial number system to compute the indices of the Nth combination. (See this wikipedia article for the basic idea).

However, this is complicated by the fact that combinations() returns combinations in lexicographic ordering of the increasing sequence of their elements whereas the combinatorial number system goes in lexicographic ordering by decreasing sequence. For example,

# Decreasing, as per combinatorial
combinations([0,1,2,3], 2) -> {[0,1], [0,2], [1,2], [0,3], [1,3], [2,3]}

# Increasing, as per itertools
combinations([0,1,2,3], 2) -> {[0,1], [0,2], [0,3], [1,2], [1,3], [2, 3]}

To compute the indices belonging to the Nth combination using this 'reversed' ordering, we would need to know the total number of elements so that we can 'invert' the indices: i -> n-i-1. This is a bit of an issue given that the iterator could be infinite. So I think the only option to get this working would be to 'correct' the ordering. But that would be a breaking change.

The alternative, which I think #329 pursued, is to repeatedly 'increment' the indices in the way that the next() function does. However, I can't imagine this would provide us with any real efficiency gains.

[Philippe-Cholet]

@kinto-b
Without the iterator being infinite, the remaining length could still be more than usize::MAX. We could eventually implement such optimization in the case that compute the length does not overflow but it's not a priority.
(We won't change the order of the elements though. Especially since it's explicitely guaranteed in the doc.)

I disagree on no real efficiency gain of #329 because the generated type Vec<I::Item> heap-allocates which is slow. If it was a lending iterator, there would be no heap-allocate each time and it probably would not be interesting to specialize nth.
.nth(n) could here avoid n heap allocations which I expect to provide real gain.
I only closed the PR because the author was not around anymore and that I thought it would easier to start anew considering all changes that happened since it was opened.

[kinto-b]

@Philippe-Cholet Thanks for your prompt reply, and good point! Please see #914 :)

[Philippe-Cholet]

Solved by #914.