Combinatorics is a Python module that was created to supplement Python's itertools module, filling in gaps in two important areas of basic combinatorics: (A) ordered and unordered m-way combinations, and (B) generalized versions of several important occupancy problems ('balls in boxes').
Brief descriptions of the included functions and classes follow (more detailed descriptions, and in some cases also examples, can be found in the individual doc strings within the functions):
n_choose_m(n, m): calculate n-choose-m, using a simple algorithm that is less likely to involve large integers than the direct evaluation of n! / m! / (n-m)!
m_way_ordered_combinations(items, ks): This function returns a generator that produces all m-way ordered combinations (multinomial combinations) from the specified collection of items, with ks[0] items in the first group, ks[1] in the second group, and so forth. By 'ordered combinations', we mean that the relative order of equal- size groups is important; the order of the items within any group is not important. The total number of combinations generated is given by the multinomial coefficient formula.
m_way_unordered_combinations(items, ks): This function returns a generator that produces all m-way unordered combinations from the specified collection of items, with ks[i] items in the ith group, i= 0, 1, 2, ..., m-1, where m= len(ks) is the number of groups. By 'unordered combinations', we mean that the relative order of equal-size groups is not important. The order of the items within any group is also unimportant.
unlabeled_balls_in_labeled_boxes(balls, box_sizes): This function returns a generator that produces all distinct distributions of indistinguishable balls among labeled boxes with specified box sizes (capacities). This is a generalization of the most common formulation of the problem, where each box is sufficiently large to accommodate all of the balls, and is an important example of a class of combinatorics problems called 'weak composition' problems.
unlabeled_balls_in_unlabeled_boxes(balls, box_sizes): This function returns a generator that produces all distinct distributions of indistinguishable balls among indistinguishable boxes, with specified box sizes (capacities). This is a generalization of the most common formulation of the problem, where each box is sufficiently large to accommodate all of the balls. It might be asked, 'In what sense are the boxes indistinguishable if they have different capacities?' The answer is that the box capacities must be considered when distributing the balls, but once the balls have been distributed, the identities of the boxes no longer matter.
labeled_balls_in_unlabeled_boxes(balls, box_sizes): This function returns a generator that produces all distinct distributions of distinguishable balls among indistinguishable boxes, with specified box sizes (capacities). This is a generalization of the most common formulation of the problem, where each box is sufficiently large to accommodate all of the balls.
Product's homepage
Requirements:
· Python
What's New in This Release: [ read full changelog ]
· I added three algorithms that solve the off-by-m problem. The first, which is the slowest, and the last, which is the fastest, were written by me. The second was contributed by Warren Weckesser of Enthought.
Find us on Google+
