array_combinations using array::map

[ronnodas]

This is an implementation of array_combinations that imitates combinations except using [_; K] (with K a const generic) for the indices and the item type instead of Vec. Uses array::from_fn and array::map although the former could be easily avoided.

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 95.55556% with 4 lines in your changes missing coverage. Please review.

Project coverage is 94.41%. Comparing base (6814180) to head (b5e5cd1). Report is 126 commits behind head on master.

Files with missing lines	Patch %	Lines
src/combinations.rs	93.65%	4 Missing :warning:

Additional details and impacted files

```diff @@ Coverage Diff @@ ## master #991 +/- ## ========================================== + Coverage 94.38% 94.41% +0.02% ========================================== Files 48 49 +1 Lines 6665 6768 +103 ========================================== + Hits 6291 6390 +99 - Misses 374 378 +4 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[ronnodas]

Note that tuple_combinations does not need to allocate but does need to clone the input iterator (and not just its elements) because it is using a different algorithm, in a way recursing on the length of tuple. I do not see a straightforward way to do that with const generics.

[phimuemue]

Hi there, thanks for this.

As far as I can judge, this is pretty much a copy-paste of combinations.rs, right?

As such, I strongly suggest to try and generalize our existing combinations (that works on Vec) so that it can work on arrays, too. The algorithms for generating combinations are non-trivial and we should strive to have one source of truth.

In addition, I hope that we are able to not only generalize combinations to arrays, but also other algorithms.

@Philippe-Cholet You refactored lots of these algorithms. What's your take on this?

As far as I can see, generalizing our Vec usage in combinations to also support arrays should be possible. We could introduce a trait VecOrArray that is implemented by Vec and by arrays, offering these:

• from_fn to construct the initial indices
• len to compute k
• (maybe) is_empty
• map_onto_elements_from_pool to generalize get_at/get_array
• type Output so that the iterator knows its Item
• as_slice to pass it to n_and_count

Maybe there are even simpler/better abstractions, but I think generalizing over Vec/array leads to code that is easier to maintain:

• the gist of combination generation would only be present once
• we could potentially re-use the Vec/array abstraction for other algorithms

[ronnodas]

Hi, thanks for the suggestion! Yes, it's basically copy-paste from combinations.

I have refactored following your comment. I didn't include the initialization function (what you called from_fn) in the common indexing trait because it's specific to combinations.

I also hope that there will be more array methods soon, permutations and combinations_with_replacement are the most obviously related. For the other clear candidates, eg analogs of tuple_X, it may make more sense to wait for array::try_from_fn.

[ronnodas]

Thanks for the extremely helpful guidance!

[ronnodas]

Is there something to do on my end about the semver check? I'm not sure why it's complaining about ConsTuples. Combinations did change from a pub struct to a pub type made of a more generic struct but I think with the same public API so I don't know if this counts as a breaking change.

[phimuemue]

@jswrenn Do you agree we can include this?