combalg-py¶
combalg-py is a collection of combinatorial algorithms in python. The algorithms are primarily involve enumeration and random selection of combinatorial objects like sets, subsets, permutations, partitions and compositions. Random selection is always (unless noted otherwise) uniformly at random. The majority of the initial implementation was adapted from the mathematics presented in [NW1978].
API Documentation:¶
combalg.subset |
subset.py |
combalg.combalg |
combalg.py |
combalg.rooted_tree |
rooted_tree.py |
combalg.utility |
utility.py |
subset.py¶
Enumeration and random selection of arbitrary and k-element restricted subsets.
Members¶
-
combalg.subset.all_k_element(elements, k)[source]¶ A generator that produces all k-element subsets of the input elements in lexicographic order.
Parameters: - elements (list) – the input set
- k (int) – size of the output set
Returns: one of the k-element subsets of the input set
Return type: list
-
combalg.subset.powerset(elements)[source]¶ A generator that produces all subsets of the input ‘set’ of elements. The input doesn’t need to be a set, any iterable will do (I think). The point is that the elements need not be unique, but will be treated as unique with respect to the subset generation. For example: powerset([‘a’,’a’]) will give the sequence [‘a’,’a’], [‘a’], [‘a’], []
Parameters: elements (list) – input set Returns: one of the subsets of the input set Return type: list
-
combalg.subset.random(elements)[source]¶ Returns a random subset of a set of elements. Equivalent to randomly selecting an element of powerset(elements). For each element of the universal set, select it to be in the subset with p=0.5
Parameters: elements (list) – the input set Returns: a random subset of the input set Return type: list
-
combalg.subset.random_k_element(elements, k)[source]¶ Returns a random k-element subset of a set of elements. This is a clever algorithm, explained in [NW1978] but not actually implemented. Essentially starting with the first element of the universal set, include it in the subset with p=k/n. If the first was selected, select the next with p=(k-1)/(n-1), if not p = k/(n-1), etc.
Parameters: - elements (list) – the input set
- k (int) – the size of the output set
Returns: a random k-element subset of the input set
Return type: list
combalg.py¶
Algorithms I didn’t categorize.
Todo
the local function ‘num_partitions(n)’ is not smart at all
Todo
the local functions ‘num_partitions(n)’ and ‘choose_dj(n, rho)’ can be combined, as in [NW1978]. I have had better luck implementing algorithms from [NW1978] using the mathematical description and NOT using the fortran source.
Members¶
-
class
combalg.combalg.permutation[source]¶ Permutations of letters.
-
class
combalg.combalg.composition[source]¶ Compositions of integer N into K parts.
-
static
all(n, k)[source]¶ A generator that returns all of the compositions of n into k parts. :param n: integer to compose :type n: int :param k: number of parts to compose :type k: int :return: a list of k-elements which sum to n
Compositions are an expression of n as a sum k parts, including zero terms, and order is important. For example, the compositions of 2 into 2 parts:
>>> compositions(2,2) = [2,0],[1,1],[0,2].
NOTE: There are C(n+k-1,n) partitions of n into k parts. See: Stars and Bars.
-
static
random(n, k)[source]¶ Returns a random composition of n into k parts.
Parameters: - n (int) – integer to compose
- k (int) – number of parts to compose
Returns: a list of k-elements which sum to n
Returns random element of
compositions()selected uniformly at random.
-
static
-
class
combalg.combalg.integer_partition[source]¶ Partitions of integers
-
static
all(n)[source]¶ A generator that returns all integer partitions of n.
Parameters: n (int) – integer to partition Returns: a list of integers that sum to n, one at a time. This implementation is due to [ZS1998]. Integer partitions are unique ways of writing a sum with each term > 0, and order does not matter. The partitions of 5 are:
>>> [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
-
static
-
class
combalg.combalg.set_partition[source]¶ Partitions of sets.
-
static
all(n)[source]¶ - A generator that returns all set partitions of [n] = {0,1,2,...,n-1}. The result is returned as a 3-tuple (p,q,nc): p - a list where p[i] is the population of the i-th equivalence class q - a list where q[i] is the equivalence class of i nc - the number of equivalence classes in the partition
Todo
The following will map the list q into a list of sets that make up the partition. I’d like to see a more efficient/pythonic implementation:
def map_set_partition(a, cls): y = [] for t in range(len(a)): x = reduce(lambda x,y: x+[a[y]] if cls[y] == t else x, range(len(a)), []) if x: y.append(x) return y
-
static
rooted_tree.py¶
Rooted Tree Algorithms. Well, only random selection. I believe there is enough material in chapter 13 of [NW1978] to implement an enumerated sequence (interesting challenge).
Members¶
-
combalg.rooted_tree.random(nn)[source]¶ Returns a random rooted tree on nn vertices
Parameters: nn (int) – number of vertices in the output tree. Returns: a random rooted tree Return type: list The returned list is in Prufer Code. You can convert the result to an edge list by zipping it with the sequence [0,1,..,nn] and discarding the initial entry, which is always (0,0).
>>> result = rooted_tree.random(7) >>> edge_list = list(zip(result, range(len(result))))[1:]
utility.py¶
These are some useful utility functions.
Members¶
-
combalg.utility.is_tree(num_vert, edge_list)[source]¶ Determines if edge_list describes a tree with num_vert vertices.
Parameters: - num_vert (int) – the number of vertices in the tree
- edge_list (list of (int,int) tuples) – a list of edges (pairs of vertices)
Returns: True if the input represents a tree, False otherwise
Todo¶
Todo
the local function ‘num_partitions(n)’ is not smart at all
(The original entry is located in /home/sstump/development/combalg-py/src/combalg/combalg.py:docstring of combalg.combalg, line 5.)
Todo
the local functions ‘num_partitions(n)’ and ‘choose_dj(n, rho)’ can be combined, as in [NW1978]. I have had better luck implementing algorithms from [NW1978] using the mathematical description and NOT using the fortran source.
(The original entry is located in /home/sstump/development/combalg-py/src/combalg/combalg.py:docstring of combalg.combalg, line 9.)
Todo
The following will map the list q into a list of sets that make up the partition. I’d like to see a more efficient/pythonic implementation:
def map_set_partition(a, cls):
y = []
for t in range(len(a)):
x = reduce(lambda x,y: x+[a[y]] if cls[y] == t else x, range(len(a)), [])
if x:
y.append(x)
return y
(The original entry is located in /home/sstump/development/combalg-py/src/combalg/combalg.py:docstring of combalg.combalg.set_partition.all, line 7.)
References¶
| [NW1978] | (1, 2, 3, 4) “Combinatorial Algorithms (for Computers and Calculators),2nd ed.”, Nijenhuis & Wilf, Academic Press, 1978. http://www.math.upenn.edu/~wilf/website/CombinatorialAlgorithms.pdf |
| [ZS1998] | “Fast Algorithms for Generating Integer Partitions”, Zoghbi & Stojmenovic, 1998. https://pdfs.semanticscholar.org/9613/c1666b5e48a5035141c8927ade99a9de450e.pdf |