Change `combinations` to return in lexicographic order

[lgoettgens]

Some progress towards https://github.com/oscar-system/Oscar.jl/issues/4726.

Once this is in, the special case in Oscar.LieAlgebras can get removed and instead use this function; thus reducing the number of combinations functions.

The performance is basically identical, with a slight boost for very small instances.

julia> @b AbstractAlgebra.combinations(5, 3)
547.500 ns (26 allocs: 1.438 KiB)  # master
519.140 ns (25 allocs: 1.344 KiB)  # PR

julia> @b AbstractAlgebra.combinations(15,10)
159.201 μs (6024 allocs: 524.375 KiB)  # master
156.635 μs (6018 allocs: 476.281 KiB)  # PR

julia> @b AbstractAlgebra.combinations(18,9)
2.449 ms (97266 allocs: 7.534 MiB)  # master
2.435 ms (97258 allocs: 6.729 MiB)  # PR

The only use of this in AbstractAlgebra is minors and minors_with_position, which in their docstrings don't guarantee any iteration order. So let's see using CI if anyone downstream expects that.

I deliberately did not add an export for this, as IMO this should instead return an iterator to be in line with functions like partitions and compositions in Oscar.

[codecov[bot]]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 88.82%. Comparing base (20ae601) to head (c28516a). Report is 18 commits behind head on master.

Additional details and impacted files

@@            Coverage Diff             @@
##           master    #2034      +/-   ##
==========================================
+ Coverage   88.41%   88.82%   +0.40%     
==========================================
  Files         125      125              
  Lines       31531    32437     +906     
==========================================
+ Hits        27879    28813     +934     
+ Misses       3652     3624      -28     

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

:rocket: New features to boost your workflow:

• :snowflake: Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[thofma]

What do you suggest as a way forward if we actually need an iterator?

[lgoettgens]

What do you suggest as a way forward if we actually need an iterator?

I already discussed this a bit Wednesday afternoon with @fingolfin. To allow code in AA and Hecke to use our combinatorics, basically everything from Oscar/src/EnumerativeCombinatorics should in the long term move to AA. This will then replace the internal function here.

Independently of that, someone would need to write an iterator in the style of the other iterators in Oscar/src/EnumerativeCombinatorics. And that should for the meantime land at the same place as the other things, and then moved all together.

If I recall correctly, @fingolfin wanted to ask someone in KL (maybe Morgan?) to look into the latter.

But all of this wouldn't be a blocker for this PR. Unfortunately, some doctest in Oscar prints some ideal where the gens are constructed from combinations, so merging this would break doctests downstream.

[thofma]

hm, I just pushed an iterator version here

was this the right thing to do?

[lgoettgens]

hm, I just pushed an iterator version here

was this the right thing to do?

IMO it would be easier to first add your new iterator to Oscar. And then at some point move all of the EnumerativeCombinatorics folder over here in one go. (as per the following except from my comment above)

Independently of that, someone would need to write an iterator in the style of the other iterators in Oscar/src/EnumerativeCombinatorics. And that should for the meantime land at the same place as the other things, and then moved all together.

But since you now already invested time into this, I can also check next week of this now conforms to the style the iterators in Oscar (like WeakCompositions). And then we have one thing less to move

[lgoettgens]

Thinking again about this, I would strongly prefer the iterator to land in Oscar first. We cannot merge this PR here until a breaking release due to doctest breakage downstream. In this breaking release, we can then also move all of the EnumerativeCombinatorics from Oscar here. So putting the iterator into Oscar right now would make it immediately available to users and would replace the other hacks in LieAlgebras and IntersectionTheory.

[thofma]

I can add it to Oscar and revert it here. But if the plan is as you described, doesn't it make this PR here obsolete?

[fingolfin]

We have instead implemented a new combinations in Oscar.