combinatorics

© 2015 John Abbott, Anna M. Bigatti

GNU Free Documentation License, Version 1.2

CoCoALib Documentation Index

Examples

User documentation

Here are some basic combinatorial functions.

Operations

Counting integer partitions:

  • NumPartitions(n) computes number of partitions of n, i.e. how many distinct ways to write n as a sum of positive integers (error if n is negative)

Random subsets and random tuples:

  • RandomSubsetIndices(n) -- returns a random subset of {0,1,2...,n-1}
  • RandomSubsetIndices(n,r) -- returns a size r random subset of {0,1,2...,n-1}
  • RandomTupleIndices(n,r) -- returns a random r-tuple from {0,1,2,...,n-1}

    Notes:
  • the parameter n indicates the range {0,1,2,...,n-1} so that the integers produced are valid indices into a C++ vector of size n.
  • the result is of type vector<long>
  • the sampling is from a uniform distribution

Maintainer documentation

The algorithm for RandomSubsetIndices(n,r) was taken from the Wikipedia page on "Reservoir Sorting".

Bugs, shortcomings and other ideas

Ugly fn names RandomSubsetIndices and RandomTupleIndices

Main changes

2015

  • June (v0.99536): first version