OKlibrary  0.2.1.6
Basics.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 12.2.2010 (Swansea) */
00002 /* Copyright 2010 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 /* ******************
00023    * Basic concepts *
00024    ******************
00025 */
00026 
00027 /*
00028   Considered is a finite set M(p) of combinatorial objects, depending
00029   on a parameter p (in general a tuple of objects).
00030   The general task is to "enumerate" M(p), which has many facets.
00031   See ComputerAlgebra/Combinatorics/Lisp/Enumeration/Subsets.mac
00032   for the most up-to-date example yet.
00033 
00034   In module ComputerAlgebra/Combinatorics we only consider "classical"
00035   combinatorial objects. An attempt to define this could use the following
00036   properties:
00037    - The size of M(p) must be relatively easy to compute.
00038    - Enumeration is not a "hard" task.
00039 
00040   The starting task to is determine the size of M(p).
00041   Functions for doing so should start with "count_M", where M is a place-holder
00042   for the name of the object class.
00043 
00044   The most basic enumeration task is to completely list M(p) (as a list),
00045   where the two most basic orderings are lexicographical and colexicographical
00046   ordering (see ComputerAlgebra/Combinatorics/Lisp/Enumeration/Order.mac).
00047   The naming scheme is "lex_M_l", "colex_M_l" etc.
00048 
00049   The core task then is to *rank* the elements of M(p), that is, to compute
00050   functions M(p) -> {1, ..., |M(p)|} for the orderings considered, and
00051   to unrank them, that is, to compute the inverses of these functions.
00052   The naming scheme here is "rank_lex_M", "rank_colex_M" etc., resp.
00053   "unrank_lex_M", "unrank_colex_M" etc.
00054 */
00055