Module: sage.combinat.combinat
Combinatorial Functions.
Author Log:
This module implements some combinatorial functions, as listed below. For a more detailed description, see the relevant docstrings.
Sequences:
bell_number
bernoulli_number
(though PARI's bernoulli is
better)
catalan_number
(not to be confused with the
Catalan constant)
euler_number
(Maxima)
fibonacci
(PARI) and fibonacci_number
(GAP)
The PARI version is better.
lucas_number1
, lucas_number2
.
stirling_number1
, stirling_number2
.
Set-theoretic constructions:
combinations
, combinations_iterator
,
and number_of_combinations
. These are unordered selections without
repetition of k objects from a multiset S.
arrangements
and number_of_arrangements
These are ordered selections without repetition of k objects from a
multiset S.
derangements
and number_of_derangements
.
tuples
and number_of_tuples
.
An ordered tuple of length k of set S is a ordered selection with
repetitions of S and is represented by a sorted list of length k
containing elements from S.
unordered_tuple
and number_of_unordered_tuples
.
An unordered tuple of length k of set S is a unordered selection with
repetitions of S and is represented by a sorted list of length k
containing elements from S.
permutations
, permutations_iterator
,
number_of_permutations
. A permutation is a list that contains exactly the same elements but
possibly in different order.
Partitions:
partitions_set
, number_of_partitions_set
.
An unordered partition of set S is a set of pairwise disjoint
nonempty sets with union S and is represented by a sorted list of
such sets.
partitions_list
, number_of_partitions_list
.
An unordered partition of n is an unordered sum
ordered_partitions
,
number_of_ordered_partitions
.
An ordered partition of n is an ordered sum
partitions_restricted
,
number_of_partitions_restricted
.
An unordered restricted partition of n is an unordered sum
partitions_greatest
implements a special type of restricted partition.
partitions_greatest_eq
is another type of restricted partition.
partition_tuples
,
number_of_partition_tuples
.
A
partition_power(pi, k)
.
The power of a partition corresponds to the
partition_sign( pi )
This means the sign of a permutation with cycle structure given by the
partition pi.
partition_associated( pi )
The ``associated'' (also called ``conjugate'' in the literature)
partition of the partition pi which is obtained by transposing the
corresponding Ferrers diagram.
ferrers_diagram
.
Analogous to the Young diagram of an irredicible representation
of Related functions:
bernoulli_polynomial
Implemented in other modules (listed for completeness):
The sage.rings.arith module contains the following combinatorial functions:
number_of_partitions
(wrapped from PARI)
the *number* of partitions:
falling_factorial
Definition: for integer rising_factorial
Definition: for integer
The sage.groups.perm_gps.permgroup_elements contains the following combinatorial functions:
TODO: GUAVA commands: * MOLS returns a list of n Mutually Orthogonal Latin Squares (MOLS). * VandermondeMat * GrayMat returns a list of all different vectors of length n over the field F, using Gray ordering. Not in GAP: * Rencontres numbers http://en.wikipedia.org/wiki/Rencontres_number
REFERENCES: http://en.wikipedia.org/wiki/Twelvefold_way (general reference)
Module-level Functions
mset, k) |
An arrangement of mset is an ordered selection without repetitions and is represented by a list that contains only elements from mset, but maybe in a different order.
arrangements
returns the set of arrangements of the
multiset mset that contain k elements.
IMPLEMENTATION: Wraps GAP's Arrangements.
WARNING: Wraps GAP - hence mset must be a list of objects that have string representations that can be interpreted by the GAP intepreter. If mset consists of at all complicated SAGE objects, this function does *not* do what you expect. A proper function should be written! (TODO!)
sage: mset = [1,1,2,3,4,4,5] sage: arrangements(mset,2) [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4]] sage: arrangements( ["c","a","t"], 2 ) ['ac', 'at', 'ca', 'ct', 'ta', 'tc'] sage: arrangements( ["c","a","t"], 3 ) ['act', 'atc', 'cat', 'cta', 'tac', 'tca']
n) |
Returns the n-th Bell number (the number of ways to partition a set of n elements into pairwise disjoint nonempty subsets).
If
, returns
.
Wraps GAP's Bell.
sage: bell_number(10) 115975 sage: bell_number(2) 2 sage: bell_number(-10) 1 sage: bell_number(1) 1 sage: bell_number(1/3) Traceback (most recent call last): ... TypeError: no coercion of this rational to integer
x, n) |
The generating function for the Bernoulli polynomials is
One has
, where
is the
Hurwitz zeta function. Thus, in a certain sense, the Hurwitz zeta
generalizes the Bernoulli polynomials to non-integer values of n.
sage: y = QQ['y'].0 sage: bernoulli_polynomial(y,5) y^5 - 5/2*y^4 + 5/3*y^3 - 1/6*y
REFERENCES: http://en.wikipedia.org/wiki/Bernoulli_polynomials
n) |
Returns the n-th Catalan number
Catalan numbers: The
-th Catalan number is given directly in terms of
binomial coefficients by
Consider the set
. A noncrossing partition of
is a partition in which no two blocks "cross" each other, i.e., if a
and b belong to one block and x and y to another, they are not arranged
in the order axby.
is the number of noncrossing partitions of the set
.
There are many other interpretations (see REFERENCES).
When
, this function raises a ZeroDivisionError; for other
it
returns 0
.
sage: [catalan_number(i) for i in range(7)] [1, 1, 2, 5, 14, 42, 132] sage: maxima.eval("-(1/2)*taylor (sqrt (1-4*x^2), x, 0, 15)") '-1/2+x^2+x^4+2*x^6+5*x^8+14*x^10+42*x^12+132*x^14' sage: [catalan_number(i) for i in range(-7,7) if i != -1] [0, 0, 0, 0, 0, 0, 1, 1, 2, 5, 14, 42, 132] sage: catalan_number(-1) Traceback (most recent call last): ... ZeroDivisionError: Rational division by zero
REFERENCES:
mset, k) |
A combination of a multiset (a list of objects which may contain the same object several times) mset is an unordered selection without repetitions and is represented by a sorted sublist of mset. Returns the set of all combinations of the multiset mset with k elements.
WARNING: Wraps GAP's Combinations. Hence mset must be a list of objects that have string representations that can be interpreted by the GAP intepreter. If mset consists of at all complicated SAGE objects, this function does *not* do what you expect. A proper function should be written! (TODO!)
sage: mset = [1,1,2,3,4,4,5] sage: combinations(mset,2) [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 4], [4, 5]] sage: mset = ["d","a","v","i","d"] sage: combinations(mset,3) ['add', 'adi', 'adv', 'aiv', 'ddi', 'ddv', 'div']
NOTE: For large lists, this raises a string error.
mset, [n=None]) |
Posted by Raymond Hettinger, 2006/03/23, to the Python Cookbook: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474124
Much faster than combinations.
sage: X = combinations_iterator([1,2,3,4,5],3) sage: [x for x in X] [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
mset) |
Returns a list of all cyclic permutations of mset. Treats mset as a list, not a set, i.e. entries with the same value are distinct.
Author: Emily Kirkman
sage: from sage.combinat.combinat import cyclic_permutations, cyclic_permutations_iterator sage: cyclic_permutations(range(4)) [[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1]] sage: for cycle in cyclic_permutations(['a', 'b', 'c']): ... print cycle ['a', 'b', 'c'] ['a', 'c', 'b']
Note that lists with repeats are not handled intuitively:
sage: cyclic_permutations([1,1,1]) [[1, 1, 1], [1, 1, 1]]
mset) |
Iterates over all cyclic permutations of mset in cycle notation. Treats mset as a list, not a set, i.e. entries with the same value are distinct.
Author: Emily Kirkman
sage: from sage.combinat.combinat import cyclic_permutations, cyclic_permutations_iterator sage: cyclic_permutations(range(4)) [[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1]] sage: for cycle in cyclic_permutations(['a', 'b', 'c']): ... print cycle ['a', 'b', 'c'] ['a', 'c', 'b']
Note that lists with repeats are not handled intuitively:
sage: cyclic_permutations([1,1,1]) [[1, 1, 1], [1, 1, 1]]
mset) |
A derangement is a fixed point free permutation of list and is represented by a list that contains exactly the same elements as mset, but possibly in different order. Derangements returns the set of all derangements of a multiset.
Wraps GAP's Derangements.
WARNING: Wraps GAP - hence mset must be a list of objects that have string representations that can be interpreted by the GAP intepreter. If mset consists of at all complicated SAGE objects, this function does *not* do what you expect. A proper function should be written! (TODO!)
sage: mset = [1,2,3,4] sage: derangements(mset) [[2, 1, 4, 3], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 3, 1, 2], [4, 3, 2, 1]] sage: derangements(["c","a","t"]) ['atc', 'tca']
n) |
Returns the n-th Euler number
IMPLEMENTATION: Wraps Maxima's euler.
sage: [euler_number(i) for i in range(10)] [1, 0, -1, 0, 5, 0, -61, 0, 1385, 0] sage: maxima.eval("taylor (2/(exp(x)+exp(-x)), x, 0, 10)") '1-x^2/2+5*x^4/24-61*x^6/720+277*x^8/8064-50521*x^10/3628800' sage: [euler_number(i)/factorial(i) for i in range(11)] [1, 0, -1/2, 0, 5/24, 0, -61/720, 0, 277/8064, 0, -50521/3628800] sage: euler_number(-1) Traceback (most recent call last): ... ValueError: n (=-1) must be a nonnegative integer
REFERENCES: http://en.wikipedia.org/wiki/Euler_number
n, [algorithm=pari]) |
Returns then n-th Fibonacci number. The Fibonacci sequence
is defined by the initial conditions
and the
recurrence relation
. For negative
we
define
, which is consistent with the
recurrence relation.
For negative
, define
.
Input:
NOTE: PARI is tens to hundreds of times faster than GAP here; moreover, PARI works for every large input whereas GAP doesn't.
sage: fibonacci(10) 55 sage: fibonacci(10, algorithm='gap') 55
sage: fibonacci(-100) -354224848179261915075 sage: fibonacci(100) 354224848179261915075
sage: fibonacci(0) 0 sage: fibonacci(1/2) Traceback (most recent call last): ... TypeError: no coercion of this rational to integer
start, [stop=None], [algorithm=None]) |
Returns an iterator over the Fibonacci sequence, for all fibonacci numbers
from
n = start
up to (but not including) n = stop
Input:
sage: fibs = [i for i in fibonacci_sequence(10, 20)] sage: fibs [55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
sage: sum([i for i in fibonacci_sequence(100, 110)]) 69919376923075308730013
SEE ALSO: fibonacci_xrange
Author: Bobby Moretti
start, [stop=None], [algorithm=pari]) |
Returns an iterator over all of the Fibonacci numbers in the given range,
including f_n = start
up to, but not including, f_n = stop
.
sage: fibs_in_some_range = [i for i in fibonacci_xrange(10^7, 10^8)] sage: len(fibs_in_some_range) 4 sage: fibs_in_some_range [14930352, 24157817, 39088169, 63245986]
sage: fibs = [i for i in fibonacci_xrange(10, 100)] sage: fibs [13, 21, 34, 55, 89]
sage: list(fibonacci_xrange(13, 34)) [13, 21]
A solution to the second Project Euler problem:
sage: sum([i for i in fibonacci_xrange(10^6) if is_even(i)]) 1089154
SEE ALSO: fibonacci_sequence
Author: Bobby Moretti
n) |
Returns an n x n Hadamard matrix of order
, if possible.
If the construction of this matrix is not implemented in GUAVA or there is no such matrix, raises a NotImplementedError.
sage: hadamard_matrix(4) [ 1 1 1 1] [ 1 -1 1 -1] [ 1 1 -1 -1] [ 1 -1 -1 1] sage: hadamard_matrix(6) Traceback (most recent call last): ... NotImplementedError: Hadamard matrix of order 6 does not exist or is not implemented yet.
s, x, N) |
Returns the value of the
to
decimals, where s and x are real.
The Hurwitz zeta function is one of the many zeta functions. It defined as
When
sage: hurwitz_zeta(3,1/2,6) 8.41439000000000 sage: hurwitz_zeta(1.1,1/2,6) 12.1041000000000 sage: hurwitz_zeta(1.1,1/2,50) 12.103813495683744469025853545548130581952676591199
REFERENCES: http://en.wikipedia.org/wiki/Hurwitz_zeta_function
n, P, Q) |
Returns then n-th Lucas number ``of the first kind'' (this is not
standard terminology). The Lucas sequence
is defined
by the initial conditions
,
and the recurrence
relation
.
Wraps GAP's Lucas(...)[1].
P=1, Q=-1 fives the Fibonacci sequence.
Input:
sage: lucas_number1(5,1,-1) 5 sage: lucas_number1(6,1,-1) 8 sage: lucas_number1(7,1,-1) 13 sage: lucas_number1(7,1,-2) 43
sage: lucas_number1(5,2,3/5) 229/25 sage: lucas_number1(5,2,1.5) Traceback (most recent call last): ... TypeError: no implicit coercion of element to the rational numbers
There was a conjecture that the sequence
defined by
,
,
, has the property
that
prime implies that
is prime.
sage: lucas = lambda n:(5/2)*lucas_number1(n,1,-1)+(1/2)*lucas_number2(n,1,-1) sage: [[lucas(n),is_prime(lucas(n)),n+1,is_prime(n+1)] for n in range(15)] [[1, False, 1, False], [3, True, 2, True], [4, False, 3, True], [7, True, 4, False], [11, True, 5, True], [18, False, 6, False], [29, True, 7, True], [47, True, 8, False], [76, False, 9, False], [123, False, 10, False], [199, True, 11, True], [322, False, 12, False], [521, True, 13, True], [843, False, 14, False], [1364, False, 15, False]]
Can you use SAGE to find a counterexample to the conjecture?
n, P, Q) |
Returns then n-th Lucas number ``of the second kind'' (this is not
standard terminology). The Lucas sequence
is defined
by the initial conditions
,
and the recurrence
relation
.
Wraps GAP's Lucas(...)[2].
Input:
sage: [lucas_number2(i,1,-1) for i in range(10)] [2, 1, 3, 4, 7, 11, 18, 29, 47, 76] sage: [fibonacci(i-1)+fibonacci(i+1) for i in range(10)] [2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
sage: n = lucas_number2(5,2,3); n 2 sage: type(n) <type 'sage.rings.integer.Integer'> sage: n = lucas_number2(5,2,-3/9); n 418/9 sage: type(n) <type 'sage.rings.rational.Rational'>
The case P=1, Q=-1 is the Lucas sequence in Brualdi's Introductory Combinatorics, 4th ed., Prentice-Hall, 2004:
sage: [lucas_number2(n,1,-1) for n in range(10)] [2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
mset, k) |
Returns the size of arrangements(mset,k). Wraps GAP's NrArrangements.
sage: mset = [1,1,2,3,4,4,5] sage: number_of_arrangements(mset,2) 22
mset, k) |
Returns the size of combinations(mset,k). IMPLEMENTATION: Wraps GAP's NrCombinations.
NOTE: mset must be a list of integers or strings (i.e., this is very restricted).
sage: mset = [1,1,2,3,4,4,5] sage: number_of_combinations(mset,2) 12
mset) |
Returns the size of derangements(mset). Wraps GAP's NrDerangements.
sage: mset = [1,2,3,4] sage: number_of_derangements(mset) 9
mset) |
Do not use this function. It will be deprecated in future version of Sage and eventually removed. Use Permutations instead; instead of
number_of_permutations(mset)
use
Permutations(mset).count().
If you insist on using this now:
Returns the size of permutations(mset).
Author: Robert L. Miller
sage: mset = [1,1,2,2,2] sage: number_of_permutations(mset) 10
S, k) |
Returns the size of tuples(S,k). Wraps GAP's NrTuples.
sage: S = [1,2,3,4,5] sage: number_of_tuples(S,2) 25 sage: S = [1,1,2,3,4,5] sage: number_of_tuples(S,2) 25
S, k) |
Returns the size of unordered_tuples(S,k). Wraps GAP's NrUnorderedTuples.
sage: S = [1,2,3,4,5] sage: number_of_unordered_tuples(S,2) 15
mset) |
A permutation is represented by a list that contains exactly the same
elements as mset, but possibly in different order. If mset is a
proper set there are
such permutations. Otherwise if the
first elements appears
times, the second element appears
times
and so on, the number of permutations is
,
which is sometimes called a multinomial coefficient.
permutations returns the set of all permutations of a multiset. Calls a function written by Mike Hansen, not GAP.
sage: mset = [1,1,2,2,2] sage: permutations(mset) [[1, 1, 2, 2, 2], [1, 2, 1, 2, 2], [1, 2, 2, 1, 2], [1, 2, 2, 2, 1], [2, 1, 1, 2, 2], [2, 1, 2, 1, 2], [2, 1, 2, 2, 1], [2, 2, 1, 1, 2], [2, 2, 1, 2, 1], [2, 2, 2, 1, 1]] sage: MS = MatrixSpace(GF(2),2,2) sage: A = MS([1,0,1,1]) sage: permutations(A.rows()) [[(1, 0), (1, 1)], [(1, 1), (1, 0)]]
mset, [n=None]) |
Do not use this function. It will be deprecated in future version of Sage and eventually removed. Use Permutations instead; instead of
for p in permutations_iterator(range(1, m+1), n)
use
for p in Permutations(m, n).
Note that Permutations, unlike this function, treats repeated elements as identical.
If you insist on using this now:
Returns an iterator (http://docs.python.org/lib/typeiter.html) which can be used in place of permutations(mset) if all you need it for is a `for' loop.
Posted by Raymond Hettinger, 2006/03/23, to the Python Cookbook: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474124
Note- This function considers repeated elements as different entries, so for example:
sage: from sage.combinat.combinat import permutations, permutations_iterator sage: mset = [1,2,2] sage: permutations(mset) [[1, 2, 2], [2, 1, 2], [2, 2, 1]] sage: for p in permutations_iterator(mset): print p [1, 2, 2] [1, 2, 2] [2, 1, 2] [2, 2, 1] [2, 1, 2] [2, 2, 1]
sage: X = permutations_iterator(range(3),2) sage: [x for x in X] [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]]
n, k) |
Returns the n-th Stilling number
of the first kind (the number of
permutations of n points with k cycles).
Wraps GAP's Stirling1.
sage: stirling_number1(3,2) 3 sage: stirling_number1(5,2) 50 sage: 9*stirling_number1(9,5)+stirling_number1(9,4) 269325 sage: stirling_number1(10,5) 269325
Indeed,
.
n, k) |
Returns the n-th Stirling number
of the second kind (the
number of ways to partition a set of n elements into k pairwise
disjoint nonempty subsets). (The n-th Bell number is the sum of
the
's,
.)
Wraps GAP's Stirling2.
Stirling numbers satisfy
:
sage: 5*stirling_number2(9,5) + stirling_number2(9,4) 42525 sage: stirling_number2(10,5) 42525
sage: n = stirling_number2(20,11); n 1900842429486 sage: type(n) <type 'sage.rings.integer.Integer'>
S, k) |
An ordered tuple of length k of set is an ordered selection with repetition and is represented by a list of length k containing elements of set. tuples returns the set of all ordered tuples of length k of the set.
sage: S = [1,2] sage: tuples(S,3) [[1, 1, 1], [2, 1, 1], [1, 2, 1], [2, 2, 1], [1, 1, 2], [2, 1, 2], [1, 2, 2], [2, 2, 2]] sage: mset = ["s","t","e","i","n"] sage: tuples(mset,2) [['s', 's'], ['t', 's'], ['e', 's'], ['i', 's'], ['n', 's'], ['s', 't'], ['t', 't'], ['e', 't'], ['i', 't'], ['n', 't'], ['s', 'e'], ['t', 'e'], ['e', 'e'], ['i', 'e'], ['n', 'e'], ['s', 'i'], ['t', 'i'], ['e', 'i'], ['i', 'i'], ['n', 'i'], ['s', 'n'], ['t', 'n'], ['e', 'n'], ['i', 'n'], ['n', 'n']]
The Set(...) comparisons are necessary because finite fields are not enumerated in a standard order.
sage: K.<a> = GF(4, 'a') sage: mset = [x for x in K if x!=0] sage: tuples(mset,2) [[a, a], [a + 1, a], [1, a], [a, a + 1], [a + 1, a + 1], [1, a + 1], [a, 1], [a + 1, 1], [1, 1]]
Author: Jon Hanke (2006-08?)
S, k) |
An unordered tuple of length k of set is a unordered selection with repetitions of set and is represented by a sorted list of length k containing elements from set.
unordered_tuples returns the set of all unordered tuples of length k of the set. Wraps GAP's UnorderedTuples.
WARNING: Wraps GAP - hence mset must be a list of objects that have string representations that can be interpreted by the GAP intepreter. If mset consists of at all complicated SAGE objects, this function does *not* do what you expect. A proper function should be written! (TODO!)
sage: S = [1,2] sage: unordered_tuples(S,3) [[1, 1, 1], [1, 1, 2], [1, 2, 2], [2, 2, 2]] sage: unordered_tuples(["a","b","c"],2) ['aa', 'ab', 'ac', 'bb', 'bc', 'cc']
Class: CombinatorialClass
Functions: count,
filter,
first,
iterator,
last,
list,
next,
previous,
random,
random_element,
rank,
union,
unrank
self) |
Default implmentation of count which just goes through the iterator of the combinatorial class to count the number of objects.
sage: C = CombinatorialClass() sage: it = lambda: iter([1,2,3]) sage: C.iterator = it sage: C.count() #indirect doctest 3
self, f, [name=None]) |
Returns the combinatorial subclass of f which consists of the elements x of self such that f(x) is True.
sage: P = Permutations(3).filter(lambda x: x.avoids([1,2])) sage: P.list() [[3, 2, 1]]
self) |
Default implementation for first which uses iterator.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.first() # indirect doctest 1
self) |
Default implementation of iterator.
sage: C = CombinatorialClass() sage: C.iterator() Traceback (most recent call last): ... NotImplementedError: iterator called but not implemented
self) |
Default implementation for first which uses iterator.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.last() # indirect doctest 3
self) |
The default implementation of list which builds the list from the iterator.
sage: C = CombinatorialClass() sage: it = lambda: iter([1,2,3]) sage: C.iterator = it sage: C.list() #indirect doctest [1, 2, 3]
self, obj) |
Default implementation for next which uses iterator.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.next(2) # indirect doctest 3
self, obj) |
Default implementation for next which uses iterator.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.previous(2) # indirect doctest 1
self) |
Deprecated. Use self.random_element() instead.
sage: C = CombinatorialClass() sage: C.random() Traceback (most recent call last): ... NotImplementedError: Deprecated: use random_element() instead
self) |
Default implementation of random which uses unrank.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.random_element() 1
self, obj) |
Default implementation of rank which uses iterator.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.rank(3) # indirect doctest 2
self, right_cc, [name=None]) |
Returns the combinatorial class representing the union of self and right_cc.
sage: P = Permutations(2).union(Permutations(1)) sage: P.list() [[1, 2], [2, 1], [1]]
self, r) |
Default implementation of unrank which goes through the iterator.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.unrank(1) # indirect doctest 2
Special Functions: __call__,
__cmp__,
__contains__,
__getitem__,
__iter__,
__len__,
__repr__,
__str__,
_CombinatorialClass__count_from_iterator,
_CombinatorialClass__first_from_iterator,
_CombinatorialClass__iterator_from_list,
_CombinatorialClass__iterator_from_next,
_CombinatorialClass__iterator_from_previous,
_CombinatorialClass__iterator_from_unrank,
_CombinatorialClass__last_from_iterator,
_CombinatorialClass__list_from_iterator,
_CombinatorialClass__next_from_iterator,
_CombinatorialClass__previous_from_iterator,
_CombinatorialClass__random_element_from_unrank,
_CombinatorialClass__rank_from_iterator,
_CombinatorialClass__unrank_from_iterator
self, x) |
Returns x as an element of the combinatorial class's object class.
sage: p5 = Partitions(5) sage: a = [2,2,1] sage: type(a) <type 'list'> sage: a = p5(a) sage: type(a) <class 'sage.combinat.partition.Partition_class'> sage: p5([2,1]) Traceback (most recent call last): ... ValueError: [2, 1] not in Partitions of the integer 5
self, x) |
Compares two different combinatorial classes. For now, the comparison is done just on their repr's.
sage: p5 = Partitions(5) sage: p6 = Partitions(6) sage: repr(p5) == repr(p6) False sage: p5 == p6 False
self, x) |
Tests whether or not the combinatorial class contains the object x. This raises a NotImplementedError as a default since _all_ subclasses of CombinatorialClass should override this.
Note that we could replace this with a default implementation that just iterates through the elements of the combinatorial class and checks for equality. However, since we use __contains__ for type checking, this operation should be cheap and should be implemented manually for each combinatorial class.
sage: C = CombinatorialClass() sage: x in C Traceback (most recent call last): ... NotImplementedError
self, i) |
Returns the combinatorial object of rank i.
sage: p5 = Partitions(5) sage: p5[0] [5] sage: p5[6] [1, 1, 1, 1, 1] sage: p5[7] Traceback (most recent call last): ... ValueError: the value must be between 0 and 6 inclusive
self) |
Allows the combinatorial class to be treated as an iterator.
sage: p5 = Partitions(5) sage: [i for i in p5] [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
self) |
Returns the number of elements in the combinatorial class.
sage: len(Partitions(5)) 7
self) |
sage: repr(Partitions(5)) 'Partitions of the integer 5'
self) |
Returns a string representation of self.
sage: str(Partitions(5)) 'Partitions of the integer 5'
self) |
Default implmentation of count which just goes through the iterator of the combinatorial class to count the number of objects.
sage: C = CombinatorialClass() sage: it = lambda: iter([1,2,3]) sage: C.iterator = it sage: C.count() #indirect doctest 3
self) |
Default implementation for first which uses iterator.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.first() # indirect doctest 1
self) |
An iterator to use when .list() is provided()
sage: C = CombinatorialClass() sage: C.list = lambda: [1, 2, 3] sage: list(C.iterator()) # indirect doctest [1, 2, 3]
self) |
An iterator to use when .first() and .next() are provided.
sage: C = CombinatorialClass() sage: C.first = lambda: 0 sage: C.next = lambda c: c+1 sage: it = C.iterator() # indirect doctest sage: [it.next() for _ in range(4)] [0, 1, 2, 3]
self) |
An iterator to use when .last() and .previous() are provided. Note that this requires the combinatorial class to be finite. It is not recommended to implement combinatorial classes using last and previous.
sage: C = CombinatorialClass() sage: C.last = lambda: 4 sage: def prev(c): ... if c <= 1: ... return None ... else: ... return c-1 ... sage: C.previous = prev sage: it = C.iterator() # indirect doctest sage: [it.next() for _ in range(4)] [1, 2, 3, 4]
self) |
An iterator to use when .unrank() is provided.
sage: C = CombinatorialClass() sage: l = [1,2,3] sage: C.unrank = lambda c: l[c] sage: list(C.iterator()) # indirect doctest [1, 2, 3]
self) |
Default implementation for first which uses iterator.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.last() # indirect doctest 3
self) |
The default implementation of list which builds the list from the iterator.
sage: C = CombinatorialClass() sage: it = lambda: iter([1,2,3]) sage: C.iterator = it sage: C.list() #indirect doctest [1, 2, 3]
self, obj) |
Default implementation for next which uses iterator.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.next(2) # indirect doctest 3
self, obj) |
Default implementation for next which uses iterator.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.previous(2) # indirect doctest 1
self) |
Default implementation of random which uses unrank.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.random_element() 1
self, obj) |
Default implementation of rank which uses iterator.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.rank(3) # indirect doctest 2
self, r) |
Default implementation of unrank which goes through the iterator.
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.unrank(1) # indirect doctest 2
Class: CombinatorialObject
self, l) |
CombinatorialObject provides a thin wrapper around a list. The main differences are that __setitem__ is disabled so that CombinatorialObjects are shallowly immutable, and the intention is that they are semantically immutable.
Because of this, CombinatorialObjects provide a __hash__ function which computes the hash of the string representation of a list and the hash of its parent's class. Thus, each CombinatorialObject should have a unique string representation.
Input:
sage: c = CombinatorialObject([1,2,3]) sage: c == loads(dumps(c)) True sage: c._list [1, 2, 3] sage: c._hash is None True
Functions: index
self, key) |
sage: c = CombinatorialObject([1,2,3]) sage: c.index(1) 0 sage: c.index(3) 2
Special Functions: __add__,
__contains__,
__eq__,
__ge__,
__getitem__,
__gt__,
__init__,
__iter__,
__le__,
__len__,
__lt__,
__ne__,
__repr__,
__str__
self, other) |
sage: c = CombinatorialObject([1,2,3]) sage: c + [4] [1, 2, 3, 4] sage: type(_) <type 'list'>
self, item) |
sage: c = CombinatorialObject([1,2,3]) sage: 1 in c True sage: 5 in c False
self, other) |
sage: c = CombinatorialObject([1,2,3]) sage: d = CombinatorialObject([2,3,4]) sage: c == [1,2,3] True sage: c == [2,3,4] False sage: c == d False
self, other) |
sage: c = CombinatorialObject([1,2,3]) sage: d = CombinatorialObject([2,3,4]) sage: c >= c True sage: c >= d False sage: c >= [1,2,3] True
self, key) |
sage: c = CombinatorialObject([1,2,3]) sage: c[0] 1 sage: c[1:] [2, 3] sage: type(_) <type 'list'>
self, other) |
sage: c = CombinatorialObject([1,2,3]) sage: d = CombinatorialObject([2,3,4]) sage: c > c False sage: c > d False sage: c > [1,2,3] False
self) |
sage: c = CombinatorialObject([1,2,3]) sage: list(iter(c)) [1, 2, 3]
self, other) |
sage: c = CombinatorialObject([1,2,3]) sage: d = CombinatorialObject([2,3,4]) sage: c <= c True sage: c <= d True sage: c <= [1,2,3] True
self) |
sage: c = CombinatorialObject([1,2,3]) sage: len(c) 3 sage: c.__len__() 3
self, other) |
sage: c = CombinatorialObject([1,2,3]) sage: d = CombinatorialObject([2,3,4]) sage: c < d True sage: c < [2,3,4] True
self, other) |
sage: c = CombinatorialObject([1,2,3]) sage: d = CombinatorialObject([2,3,4]) sage: c != c False sage: c != d True sage: c != [1,2,3] False
self) |
sage: c = CombinatorialObject([1,2,3]) sage: c.__repr__() '[1, 2, 3]'
self) |
sage: c = CombinatorialObject([1,2,3]) sage: str(c) '[1, 2, 3]'
Class: FilteredCombinatorialClass
self, combinatorial_class, f, [name=None]) |
A filtered combinatorial class F is a subset of another combinatorial class C specified by a function f that takes in an element c of C and returns True if and only if c is in F.
TESTS:
sage: Permutations(3).filter(lambda x: x.avoids([1,2])) Filtered sublass of Standard permutations of 3
Functions: count,
iterator
self) |
sage: P = Permutations(3).filter(lambda x: x.avoids([1,2])) sage: P.count() 1
self) |
sage: P = Permutations(3).filter(lambda x: x.avoids([1,2])) sage: list(P.iterator()) [[3, 2, 1]]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
sage: P = Permutations(3).filter(lambda x: x.avoids([1,2])) sage: 'cat' in P False sage: [4,3,2,1] in P False sage: Permutation([1,2,3]) in P False sage: Permutation([3,2,1]) in P True
self) |
sage: P = Permutations(3).filter(lambda x: x.avoids([1,2])) sage: P.__repr__() 'Filtered sublass of Standard permutations of 3' sage: P._name = 'Permutations avoiding [1, 2]' sage: P.__repr__() 'Permutations avoiding [1, 2]'
Class: UnionCombinatorialClass
self, left_cc, right_cc, [name=None]) |
A UnionCombinatorialClass is a union of two other combinatorial classes.
TESTS:
sage: P = Permutations(3).union(Permutations(2)) sage: P == loads(dumps(P)) True
Functions: count,
first,
iterator,
last,
list,
rank,
unrank
self) |
sage: P = Permutations(3).union(Permutations(2)) sage: P.count() 8
self) |
sage: P = Permutations(3).union(Permutations(2)) sage: P.first() [1, 2, 3]
self) |
sage: P = Permutations(3).union(Permutations(2)) sage: list(P.iterator()) [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1], [1, 2], [2, 1]]
self) |
sage: P = Permutations(3).union(Permutations(2)) sage: P.last() [2, 1]
self) |
sage: P = Permutations(3).union(Permutations(2)) sage: P.list() [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1], [1, 2], [2, 1]]
self, x) |
sage: P = Permutations(3).union(Permutations(2)) sage: P.rank(Permutation([2,1])) 7 sage: P.rank(Permutation([1,2,3])) 0
self, x) |
sage: P = Permutations(3).union(Permutations(2)) sage: P.unrank(7) [2, 1] sage: P.unrank(0) [1, 2, 3]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
sage: P = Permutations(3).union(Permutations(2)) sage: [1,2] in P True sage: [3,2,1] in P True sage: [1,2,3,4] in P False
self) |
TESTS:
sage: print repr(Permutations(3).union(Permutations(2))) Union combinatorial class of Standard permutations of 3 and Standard permutations of 2
See About this document... for information on suggesting changes.