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).

This could be called "statefree iteration" through M(p).

If x is the last element, then "done" is returned (otherwise the next element).

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).

The following needs updating according to the general concepts in ComputerAlgebra/AbstractDataTypes/Lisp/plans/general.hpp.

And see "Iteration through lexicographical order" in ComputerAlgebra/Combinatorics/Lisp/Enumeration/plans/Subsets.hpp for a specific example.

Iteration is given by a functionobject I(p) which can be initialised, queried whether the pasttheend has been reached, and if this is not the case, can return the current object and can be advanced to the next element (possibly "pasttheend").

This is like forwarditerators in C++, only that we are running through a fixed collection (not an arbitrary one). Likely we don't need equalitycomparison, but we should provide a method of ranking the current element (faster than by calling the rankingfunction for the current element).

The point of such an iterator would be that it is more efficient than the statefree iteration.

Perhaps such an iterator could be just some object which contains all the necessary stateinformation (like the current index i, the current element x, and the underlying information on x such that the successor x' can be quickly determined.

The iteratormethods would then just inspect this object, or compute a new object from an old one.

However, according to the "concrete" character of the Maxima/Lisp level we should avoid hiding information.

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 pasttheend; 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.

Or perhaps the first (indicator) entry is "done/true", and the whilecondition then is "while it[1] # done" ?

Or perhaps we have a pair [i,state], where i is either "done" or the rank? This would also fit better with the statefree approach.
 Todo:
 Connections
 Todo:
 Basic overview

According to [Stanton, White; Constructive Combinatorics], the basic submodules would be:

Permutations; perhaps with submodule Involutions

Subsets

Set partitions

Integer partitions

Product spaces

Trees (not as data structures; in ComputerAlgebra/Graphs/Lisp/Trees/plans/Generators.hpp we do not handle the proper enumerative aspects)

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.

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[n1,ki,s],i,0,min(k,s));

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[ni,ki*s,s1],i,0,min(n,floor(k/s)));

The latter seems slower?
Definition in file general.hpp.