Array combinations

[conradludgate]

An alternative to TupleCombinations that works in a similar fashion to the standard Combinations iterator. It's implemented using const generics and manages to work for >12 elements too. Another benefit is that it doesn't require the iterator to implement Clone, only I::Item

I doubt I'll be able to get merged as is. Since this uses const generics, it would need to either be feature gated or we raise the MSRV from 1.32 all the way to 1.51

Benchmark results:

tuple comb for1         time:   [23.681 us 23.714 us 23.757 us]
tuple comb for2         time:   [27.554 us 27.584 us 27.617 us]
tuple comb for3         time:   [67.963 us 68.138 us 68.343 us]
tuple comb for4         time:   [60.098 us 60.182 us 60.280 us]

tuple comb c1           time:   [24.335 us 24.357 us 24.383 us]
tuple comb c2           time:   [43.833 us 43.876 us 43.924 us]
tuple comb c3           time:   [282.67 us 282.98 us 283.31 us]
tuple comb c4           time:   [1.2475 ms 1.2496 ms 1.2525 ms]

array comb c1           time:   [64.303 us 64.325 us 64.349 us]
array comb c2           time:   [201.38 us 201.49 us 201.61 us]
array comb c3           time:   [120.58 us 120.96 us 121.41 us]
array comb c4           time:   [176.37 us 176.58 us 176.79 us]

Interesting notes: c1 and c2 for this version are much higher than I would have expected but c3 and c4 are much lower than the tuple alternatives

[conradludgate]

I think I'm amenable to increasing the MSRV for const-generics in a major version bump, but it'd be great if we could identify any other parts of the library that'd also benefit from const generics first.

Certainly. Perhaps it's worth opening a tracking issue and a feature branch for 0.11?

[conradludgate]

For now, I'm not in a rush to get this merged in. For my own use cases, noting the performance details above, I ended up making a macro to implement the for loop strategy simply

for_combinations!([a, b, c] in slice {
	println!("{:?} {:?} {:?}", a, b, c);
}):

But I'm happy to look into the const generics major bump

[conradludgate]

I've updated the implementation quite a bit. I've used array_init for now to handle the safety of array initialisation. I've also implemented the lazy approach as discussed, I've also changed the combinations algorithm to support infinite iterators from #330

Updated benchmark times:

tuple comb for1         time:   [24.681 us 24.730 us 24.781 us]
tuple comb for2         time:   [27.828 us 27.894 us 28.000 us]
tuple comb for3         time:   [66.224 us 66.343 us 66.501 us]
tuple comb for4         time:   [78.554 us 78.648 us 78.766 us]

tuple comb c1           time:   [24.809 us 24.961 us 25.130 us]
tuple comb c2           time:   [43.905 us 43.985 us 44.081 us]
tuple comb c3           time:   [287.64 us 287.92 us 288.22 us]
tuple comb c4           time:   [1.2784 ms 1.2798 ms 1.2812 ms]

array comb c1           time:   [388.77 us 396.34 us 403.18 us]
array comb c2           time:   [306.41 us 315.74 us 327.54 us]
array comb c3           time:   [458.90 us 460.14 us 461.50 us]
array comb c4           time:   [484.57 us 485.31 us 486.09 us]