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.

  • 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.
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 
    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 
    3. The latter seems slower?

Definition in file general.hpp.