OKlibrary  0.2.1.6
general.hpp File Reference

Central docus-file for enumeration at the Maxima/Lisp level. More...

Go to the source code of this file.


Detailed Description

Central docus-file for enumeration at the Maxima/Lisp level.

Enumeration of basic combinatorial objects

Generalities

Load all enumeration-functionality (specifically) by

oklib_load("OKlib/ComputerAlgebra/Combinatorics/Lisp/Enumeration/include.mac");
  

The basic concepts one finds in ComputerAlgebra/Combinatorics/Lisp/Enumeration/Basics.mac.

  • The basic situation is that one has given a finite set M(p), where p is some parameter (perhaps a list).
  • For example the set of k-element subsets of an n-element set.
  • The basic task is counting, that is determining the size of M(p).
  • Next comes to specify interesting linear orders of M(p), typically lexicographical and colexicographical order.
  • The simplest form of computing such orders is by simply listing M(p) in the order.
  • Finding the index in these lists of an element of M(p) is called ranking, while for an index (in these list) finding the corresponding object of M(p) is called unranking.
  • Indices start with 0 (as with list-indices).

Enumerating subsets

The functionality is loaded (specifically) by

(%i1) oklib_load("OKlib/ComputerAlgebra/Combinatorics/Lisp/Enumeration/Subsets.mac");
  

See ComputerAlgebra/Combinatorics/Lisp/Enumeration/Subsets.mac for the definitions and specifications.

k-subsets

Counting of k-subsets (subsets of length k) happens, of course, by using binomial coefficients, but for completeness we also provide special functions:

(%i2) count_ksubsets_s({1,3,5,6},2);
(%o2) 6
(%i3) count_ksubsets(4,2);
(%o3) 6
  

Lexicographical ordering

The list of all k-subsets of a set in lexicographical order:

(%i4) lex_ksubsets_l({1,-1,2,-2},2);
(%o4) [{-2,-1},{-2,1},{-2,2},{-1,1},{-1,2},{1,2}]
(%i5) lex_ksubsets_ll([1,-1,2,-2],2);
(%o5) [{-1,1},{1,2},{-2,1},{-1,2},{-2,-1},{-2,2}]
  

Ranking and unranking is available for standardised base-sets {1, ..., n}:

(%i6) lex_ksubsets_l(setn(4),2);
(%o6) [{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}]
(%i7) rank_lex_ksubsets({1,4},4);
(%o7) 3
(%i8) unrank_lex_ksubsets(3,4,2);
(%o8) {1,4}
  

Colexicographical ordering

The list of all k-subsets of a set in colexicographical order:

(%i9) colex_ksubsets_l({1,-1,2,-2},2);
(%o9) [{-2,-1},{-2,1},{-1,1},{-2,2},{-1,2},{1,2}]
(%i10) colex_ksubsets_ll([1,-1,2,-2],2);
(%o10) [{-1,1},{1,2},{-1,2},{-2,1},{-2,-1},{-2,2}]
  

Ranking and unranking is available for standardised base-sets {1, ..., n}:

(%i11) colex_ksubsets_l(setn(4),2);
(%o11) [{1,2},{1,3},{2,3},{1,4},{2,4},{3,4}]
(%i12) rank_colex_ksubsets({2,3});
(%o12) 3
(%i13) unrank_colex_ksubsets(3,4,2);
(%o13) {2,3}
  

Definition in file general.hpp.