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

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

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