18.1 Combinatorial Functions

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:

Set-theoretic constructions:

Partitions:

Related functions:

Implemented in other modules (listed for completeness):

The sage.rings.arith module contains the following combinatorial functions:

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

arrangements( 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']

bell_number( n)

Returns the n-th Bell number (the number of ways to partition a set of n elements into pairwise disjoint nonempty subsets).

If $ n \leq 0$ , returns $ 1$ .

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

bernoulli_polynomial( x, n)

The generating function for the Bernoulli polynomials is

$\displaystyle \frac{t e^{xt}}{e^t-1}= \sum_{n=0}^\infty B_n(x) \frac{t^n}{n!}.
$

One has $ B_n(x) = - n\zeta(1 - n,x)$ , where $ \zeta(s,x)$ 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

catalan_number( n)

Returns the n-th Catalan number

Catalan numbers: The $ n$ -th Catalan number is given directly in terms of binomial coefficients by

$\displaystyle C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!}$    for $\displaystyle n\ge 0.
$

Consider the set $ S = \{ 1, ..., n \}$ . A noncrossing partition of $ S$ 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. $ C_n$ is the number of noncrossing partitions of the set $ S$ . There are many other interpretations (see REFERENCES).

When $ n=-1$ , this function raises a ZeroDivisionError; for other $ n<0$ 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:

combinations( 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.

combinations_iterator( 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]]

cyclic_permutations( 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]]

cyclic_permutations_iterator( 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]]

derangements( 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']

euler_number( 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

fibonacci( n, [algorithm=pari])

Returns then n-th Fibonacci number. The Fibonacci sequence $ F_n$ is defined by the initial conditions $ F_1=F_2=1$ and the recurrence relation $ F_{n+2} = F_{n+1} + F_n$ . For negative $ n$ we define $ F_n = (-1)^{n+1}F_{-n}$ , which is consistent with the recurrence relation.

For negative $ n$ , define $ F_{n} = -F_{\vert n\vert}$ .

Input:

algorithm
- string:
"pari"
- (default) - use the PARI C library's fibo function.
"gap"
- use GAP's Fibonacci function

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

fibonacci_sequence( start, [stop=None], [algorithm=None])

Returns an iterator over the Fibonacci sequence, for all fibonacci numbers $ f_n$ from n = start up to (but not including) n = stop

Input:

start
- starting value
stop
- stopping value
algorithm
- default (None) - passed on to fibonacci function (or not passed on if None, i.e., use the default).

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

fibonacci_xrange( 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

hadamard_matrix( n)

Returns an n x n Hadamard matrix of order $ n$ , 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.

hurwitz_zeta( s, x, N)

Returns the value of the $ \zeta(s,x)$ to $ N$ decimals, where s and x are real.

The Hurwitz zeta function is one of the many zeta functions. It defined as

$\displaystyle \zeta(s,x) = \sum_{k=0}^\infty (k+x)^{-s}.
$

When $ x=1$ , this coincides with Riemann's zeta function. The Dirichlet L-functions may be expressed as a linear combination of Hurwitz zeta functions.

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

lucas_number1( n, P, Q)

Returns then n-th Lucas number ``of the first kind'' (this is not standard terminology). The Lucas sequence $ L^{(1)}_n$ is defined by the initial conditions $ L^{(1)}_1=0$ , $ L^{(1)}_2=1$ and the recurrence relation $ L^{(1)}_{n+2} = P*L^{(1)}_{n+1} - Q*L^{(1)}_n$ .

Wraps GAP's Lucas(...)[1].

P=1, Q=-1 fives the Fibonacci sequence.

Input:

n
- integer
P, Q
- integer or rational numbers

Output: integer or rational number

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 $ L_n$ defined by $ L_{n+2} = L_{n+1} + L_n$ , $ L_1=1$ , $ L_2=3$ , has the property that $ n$ prime implies that $ L_n$ 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?

lucas_number2( n, P, Q)

Returns then n-th Lucas number ``of the second kind'' (this is not standard terminology). The Lucas sequence $ L^{(2)}_n$ is defined by the initial conditions $ L^{(2)}_1=2$ , $ L^{(2)}_2=P$ and the recurrence relation $ L^{(2)}_{n+2} = P*L^{(2)}_{n+1} - Q*L^{(2)}_n$ .

Wraps GAP's Lucas(...)[2].

Input:

n
- integer
P, Q
- integer or rational numbers

Output: integer or rational number

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]

number_of_arrangements( 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

number_of_combinations( 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

number_of_derangements( mset)

Returns the size of derangements(mset). Wraps GAP's NrDerangements.

sage: mset = [1,2,3,4]
sage: number_of_derangements(mset)
9

number_of_permutations( 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

number_of_tuples( 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

number_of_unordered_tuples( 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

permutations( 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 $ \vert mset\vert !$ such permutations. Otherwise if the first elements appears $ k_1$ times, the second element appears $ k_2$ times and so on, the number of permutations is $ \vert mset\vert! / (k_1! k_2! \ldots)$ , 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)]]

permutations_iterator( 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]]

stirling_number1( n, k)

Returns the n-th Stilling number $ S_1(n,k)$ 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, $ S_1(n,k) = S_1(n-1,k-1) + (n-1)S_1(n-1,k)$ .

stirling_number2( n, k)

Returns the n-th Stirling number $ S_2(n,k)$ 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_2(n,k)$ 's, $ k=0,...,n$ .) Wraps GAP's Stirling2.

Stirling numbers satisfy $ S_2(n,k) = S_2(n-1,k-1) + kS_2(n-1,k)$ :

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'>

tuples( 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?)

unordered_tuples( 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

class CombinatorialClass

Functions: count,$ \,$ filter,$ \,$ first,$ \,$ iterator,$ \,$ last,$ \,$ list,$ \,$ next,$ \,$ previous,$ \,$ random,$ \,$ random_element,$ \,$ rank,$ \,$ union,$ \,$ unrank

count( 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

filter( 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]]

first( self)

Default implementation for first which uses iterator.

sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.first() # indirect doctest
1

iterator( self)

Default implementation of iterator.

sage: C = CombinatorialClass()
sage: C.iterator()
Traceback (most recent call last):
...
NotImplementedError: iterator called but not implemented

last( self)

Default implementation for first which uses iterator.

sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.last() # indirect doctest
3

list( 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]

next( 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

previous( 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

random( self)

Deprecated. Use self.random_element() instead.

sage: C = CombinatorialClass()
sage: C.random()
Traceback (most recent call last):
...
NotImplementedError: Deprecated: use random_element() instead

random_element( self)

Default implementation of random which uses unrank.

sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.random_element()
1

rank( 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

union( 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]]

unrank( 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

__call__( 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

__cmp__( 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

__contains__( 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

__getitem__( 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

__iter__( 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]]

__len__( self)

Returns the number of elements in the combinatorial class.

sage: len(Partitions(5))
7

__repr__( self)

sage: repr(Partitions(5))
'Partitions of the integer 5'

__str__( self)

Returns a string representation of self.

sage: str(Partitions(5))
'Partitions of the integer 5'

_CombinatorialClass__count_from_iterator( 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

_CombinatorialClass__first_from_iterator( self)

Default implementation for first which uses iterator.

sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.first() # indirect doctest
1

_CombinatorialClass__iterator_from_list( 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]

_CombinatorialClass__iterator_from_next( 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]

_CombinatorialClass__iterator_from_previous( 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]

_CombinatorialClass__iterator_from_unrank( 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]

_CombinatorialClass__last_from_iterator( self)

Default implementation for first which uses iterator.

sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.last() # indirect doctest
3

_CombinatorialClass__list_from_iterator( 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]

_CombinatorialClass__next_from_iterator( 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

_CombinatorialClass__previous_from_iterator( 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

_CombinatorialClass__random_element_from_unrank( self)

Default implementation of random which uses unrank.

sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.random_element()
1

_CombinatorialClass__rank_from_iterator( 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

_CombinatorialClass__unrank_from_iterator( 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

class CombinatorialObject
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:

l
- a list

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

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__

__add__( self, other)

sage: c = CombinatorialObject([1,2,3])
sage: c + [4]
[1, 2, 3, 4]
sage: type(_)
<type 'list'>

__contains__( self, item)

sage: c = CombinatorialObject([1,2,3])
sage: 1 in c
True
sage: 5 in c
False

__eq__( 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

__ge__( 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

__getitem__( self, key)

sage: c = CombinatorialObject([1,2,3])
sage: c[0]
1
sage: c[1:]
[2, 3]
sage: type(_)
<type 'list'>

__gt__( 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

__iter__( self)

sage: c = CombinatorialObject([1,2,3])
sage: list(iter(c))
[1, 2, 3]

__le__( 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

__len__( self)

sage: c = CombinatorialObject([1,2,3])
sage: len(c)
3
sage: c.__len__()
3

__lt__( self, other)

sage: c = CombinatorialObject([1,2,3])
sage: d = CombinatorialObject([2,3,4])
sage: c < d
True
sage: c < [2,3,4]
True

__ne__( 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

__repr__( self)

sage: c = CombinatorialObject([1,2,3])
sage: c.__repr__()
'[1, 2, 3]'

__str__( self)

sage: c = CombinatorialObject([1,2,3])
sage: str(c)
'[1, 2, 3]'

Class: FilteredCombinatorialClass

class FilteredCombinatorialClass
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

count( self)

sage: P = Permutations(3).filter(lambda x: x.avoids([1,2]))
sage: P.count()
1

iterator( self)

sage: P = Permutations(3).filter(lambda x: x.avoids([1,2]))
sage: list(P.iterator())
[[3, 2, 1]]

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( 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

__repr__( 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

class UnionCombinatorialClass
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

count( self)

sage: P = Permutations(3).union(Permutations(2))
sage: P.count()
8

first( self)

sage: P = Permutations(3).union(Permutations(2))
sage: P.first()
[1, 2, 3]

iterator( 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]]

last( self)

sage: P = Permutations(3).union(Permutations(2))
sage: P.last()
[2, 1]

list( 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]]

rank( self, x)

sage: P = Permutations(3).union(Permutations(2))
sage: P.rank(Permutation([2,1]))
7
sage: P.rank(Permutation([1,2,3]))
0

unrank( 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__

__contains__( 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

__repr__( 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.