# Basic combinatorics in OSCAR

It would be great if we could clean up, unify and possibly extend the functionality for basic combinatorics (partitions, combinations, etc.) in OSCAR.
Corresponding issue: https://github.com/oscar-system/Oscar.jl/issues/3147
Further related issues:
* https://github.com/oscar-system/Oscar.jl/issues/2462 (fancy printing of tableaux)
* https://github.com/oscar-system/Oscar.jl/issues/2301 (partitions should be in `src`)
* https://github.com/oscar-system/Oscar.jl/issues/1732 (more combinatorics!)

## Possible common interface
Inspired from `JuLie`, I propose the following rough interface for these basic combinatorial functions as a basis for further discussion.
* The functions should return iterators; there are usually a lot of returned objects (and in some applications one only needs a few). For a `Vector` of all objects, one can always use `collect`.

For functions that take an integer `n` and optional further arguments and produce lists of integers:
* Input arguments are of type `IntegerUnion`.
* I would say that the element type of the returned iterator should be a dedicated type, e.g. `Partition`. I assume that this will in general be a wrapper around `Vector{T}`, if the input is of type `T`. The dedicated type should be be a subtype of `AbstractVector`.

For functions that take a (multi-)set and optional further arguments and produce lists of (multi-)sets (e.g. partitions of a multiset, combinations of a vector)
* In consistency with the above, the return type should be a dedicated type in general wrapping `Vector{T}` where the input is of type `T`, which could be for example `MSet{Int}`.

## What we have
(or rather "what we know of")
#### in `src`
* Some non-exported or non-documented ad hoc functionality in `src/Combinatorics/OrderMultiIndex.jl` (strictly increasing sequences of `p` elements and weak compositions of `d` into `n` parts) and `src/Combinatorics/Compositions.jl` (compositions and weak compositions of `d` into `n` parts)
* `monomials_of_degree` which does weak compositions of `d` into `n` parts under the hood in `src/InvariantTheory/iterators.jl`
* partitions of a multiset in `src/InvariantTheory/iterators.jl` (not exported and not documented)
#### in `experimental`
* Several variants of partitions in `experimental/JuLie/src/partitions.jl`
* Combinations, multicombinations, permutations in `experimental/LieAlgebras/src/Combinatorics.jl`
* `experimental/SymmetricIntersections/src/elevators.jl` : Given an (ordered) list `L` of positive integers, and an integer `d`, return an iterator on the tuples of indices for which the corresponding elements in `L` sum up to `d`. Each index can be repeated, and one could ask to have an upper (and lower?) bound on the number of time each index should be used. See https://github.com/oscar-system/Oscar.jl/issues/3147#issuecomment-1875352901 .
* Related, but probably out of scope of 'basic functionality': Set partitions via https://github.com/oscar-system/Oscar.jl/pull/2977
#### in 'associated packages'
* Subsets and submultisets of a multiset in Hecke
* Some stuff in GAP https://docs.gap-system.org/doc/ref/chap16_mj.html
* Some stuff in JuLie https://github.com/ulthiel/JuLie.jl/tree/master/src/combinatorics (not all of it is in `experimental`!)
* `number_of_partitions` in Nemo

## What should be done
* [x] Adjust `weak_compositions` to the proposed interface and remove the other implementations (`monomials_of_degree`, `MultiIndicesOfDegree`); the implementation in `monomials_of_degree` appears to be the fastest, see https://github.com/oscar-system/Oscar.jl/pull/3573
* [x] Adjust `compositions` to the proposed interface, see https://github.com/oscar-system/Oscar.jl/pull/3682
* [x] Consolidate the functions from `experimental/JuLie` and move them to `src`, see https://github.com/oscar-system/Oscar.jl/pull/3159
* [x] Adjust the functions returning partitions to return iterators, see https://github.com/oscar-system/Oscar.jl/pull/3389 and https://github.com/oscar-system/Oscar.jl/pull/3830
* [x] Adjust the functions returning tableaux to return iterators, see https://github.com/oscar-system/Oscar.jl/pull/3887 and https://github.com/oscar-system/Oscar.jl/pull/4004
* [ ] `OrderedMultiIndex` appears to be combinations? If yes, merge this with the combinations in `experimental/LieAlgebras`.
* [ ] Consolidate the functions from `experimental/LieAlgebras` and move them to `src`; the implementations are 'ad hoc', but I prefer having *something* over nothing at all
* [ ] Move more things from `JuLie` over? (See https://github.com/oscar-system/Oscar.jl/pull/2183 for quantum analogs/q-analogs.)
* [ ] Provide "in place" versions of some iterators; this could lead to significant runtime improvements if people just want to use one partition/composition/... at a time