OKlibrary  0.2.1.6
general.hpp File Reference

General plans regarding enumerating basic combinatorial objects (in the algorithmic sense, as opposed to just counting) More...

Go to the source code of this file.

## Detailed Description

General plans regarding enumerating basic combinatorial objects (in the algorithmic sense, as opposed to just counting)

For pure counting see ComputerAlgebra/Combinatorics/Lisp/Counting/plans/general.hpp.

Todo:
Iteration
• Given a parameter p (which in general is a tuple) and a set M(p) of "combinatorial objects", the task is to "enumerate" M(p).
• Concepts for counting and ranking/unranking one finds in ComputerAlgebra/Combinatorics/Lisp/Enumeration/Basics.mac.
• Computing the first element of L(p), and given an object x, computing its successor in L(p) or deciding that x is the last element of L(p).
1. This could be called "state-free iteration" through M(p).
2. If x is the last element, then "done" is returned (otherwise the next element).
3. Naming "first_lex_ksubsets", "first_colex_ksubsets", "first_lex_permutations" etc., and "next_lex_ksubsets", "next_colex_ksubsets" and "next_lex_permutations" etc.
• Finally we have the task of "(general) iteration" through M(p).
1. The following needs updating according to the general concepts in ComputerAlgebra/AbstractDataTypes/Lisp/plans/general.hpp.
2. And see "Iteration through lexicographical order" in ComputerAlgebra/Combinatorics/Lisp/Enumeration/plans/Subsets.hpp for a specific example.
3. Iteration is given by a function-object I(p) which can be initialised, queried whether the past-the-end has been reached, and if this is not the case, can return the current object and can be advanced to the next element (possibly "past-the-end").
4. This is like forward-iterators in C++, only that we are running through a fixed collection (not an arbitrary one). Likely we don't need equality-comparison, but we should provide a method of ranking the current element (faster than by calling the ranking-function for the current element).
5. The point of such an iterator would be that it is more efficient than the state-free iteration.
6. Perhaps such an iterator could be just some object which contains all the necessary state-information (like the current index i, the current element x, and the underlying information on x such that the successor x' can be quickly determined.
7. The iterator-methods would then just inspect this object, or compute a new object from an old one.
8. However, according to the "concrete" character of the Maxima/Lisp level we should avoid hiding information.
9. So perhaps the general concept of an "iterator" is that of a triple I(p) = [true/false,i,state], where the first (boolean) entry specifies whether we are past-the-end; if not, then the natural number i is the current rank, and "state" finally contains all the information to make it easy to compute M(p)[i] and to go to the successor i+1.
10. Or perhaps the first (indicator) entry is "done/true", and the while-condition then is "while it[1] # done" ?
11. Or perhaps we have a pair [i,state], where i is either "done" or the rank? This would also fit better with the state-free approach.
Todo:
Connections
Todo:
Basic overview
• According to [Stanton, White; Constructive Combinatorics], the basic sub-modules would be:
1. Permutations; perhaps with submodule Involutions
2. Subsets
3. Set partitions
4. Integer partitions
5. Product spaces
6. Trees (not as data structures; in ComputerAlgebra/Graphs/Lisp/Trees/plans/Generators.hpp we do not handle the proper enumerative aspects)
7. Tableaux
• The appendix of [Stanton, White; Constructive Combinatorics] contains enumeration algorithms to start with.
• Another source is [Knuth, Volume 4, Fascicle 3].
• Apparently not handled by the above sources are for given n,k,s the multisubsets of {1,...,n} with k elements, where every element has multiplicity at most s.
1. Generalising the recursive formulas for binomial coefficients we have
```count_multisubsets_1[n,k,s] := if n=0 then (if k=0 then 1 else 0) else
sum(count_multisubsets_1[n-1,k-i,s],i,0,min(k,s));
```
2. This recurses in n; alternatively we can recurse in s:
```count_multisubsets_1[n,k,s] := if s=0 then (if k=0 then 1 else 0) else
sum(binomial(n,i)*count_multisubsets_2[n-i,k-i*s,s-1],i,0,min(n,floor(k/s)));
```
3. The latter seems slower?

Definition in file general.hpp.