An Introduction to Sets and Combinatorics using Sage
Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial - No Derivative Works 3.0 United States License.
Here are a few tips on how to get started using Sage to work with sets and combinatorial calculations.
Sets
A set is an expression of the form set(list). By wrapping a list with set, the order of elements appearing in the list and their duplication are ignored. For example, L1 and L2 are two different list, but notice how as sets they are considered equal:
L1=[3,6,9,0,3]L2=[9,6,3,0,9]L1==L2
False
set(L1)==set(L2)
True
The standard set operations are all methods and/or functions that can act on Sage sets.
A=set(range(5,50,5))
B=set(range(6,50,6))
A & B
set([30])
Notice that the union isn't sorted in any obvious way
A | B
set([35, 36, 5, 6, 40, 10, 12, 45, 15, 48, 18, 20, 24, 25, 42, 30])
The union operation is also a method, as are the other set operations.
A.union(B)
set([35, 36, 5, 6, 40, 10, 12, 45, 15, 48, 18, 20, 24, 25, 42, 30])
Caution: sorting a union strips away the set wrapper.
sorted(A|B)
[5, 6, 10, 12, 15, 18, 20, 24, 25, 30, 35, 36, 40, 42, 45, 48]
A strange result: putting the set wrapper back on unsorts the list. ????
D2=sorted(union(A,B))set(D2)
set([35, 36, 5, 6, 40, 10, 12, 45, 15, 48, 18, 20, 24, 25, 42, 30])
Set difference, or complementation:
set(srange(0,50)).difference(A)
set([0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, 42, 43, 44, 46, 47, 48, 49])
U=set([0,1,2,3])
subsets(U)
You can easily convert the result to list, but in practice the result is often a very large list. Not the case here:
list(subsets(U))
[[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2], [3], [0, 3], [1, 3], [0, 1, 3], [2, 3], [0, 2, 3], [1, 2, 3], [0, 1, 2, 3]]
Here is a simple loop using the generator object.
for a in subsets(U): print(str(a)+ " has " +str(len(a))+" elements.")
[] has 0 elements.
[0] has 1 elements.
[1] has 1 elements.
[0, 1] has 2 elements.
[2] has 1 elements.
[0, 2] has 2 elements.
[1, 2] has 2 elements.
[0, 1, 2] has 3 elements.
[3] has 1 elements.
[0, 3] has 2 elements.
[1, 3] has 2 elements.
[0, 1, 3] has 3 elements.
[2, 3] has 2 elements.
[0, 2, 3] has 3 elements.
[1, 2, 3] has 3 elements.
[0, 1, 2, 3] has 4 elements.
Here is an example where the generator goes through the 32768 different subsets of the integers from 0 to 14 and tallies the cardinalities.
isetsize={}for a in subsets(srange(0,15)): if len(a) in setsize: setsize[len(a)]+=1 else: setsize[len(a)]=1setsize.items()
[(0, 1), (1, 15), (2, 105), (3, 455), (4, 1365), (5, 3003), (6, 5005), (7, 6435), (8, 6435), (9, 5005), (10, 3003), (11, 1365), (12, 455), (13, 105), (14, 15), (15, 1)]
Set-builder notation in Sage
Syntax for building a set by logical selection from a "universe" is remarkably similar to mathematical notation. Here the universe is the set {0, 1, 2, ..., 99} and we select the primes from that set.
set([x for x in set(range(100)) if x.is_prime()])
set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97])
The set of rational numbers reduced to lowest terms with denominator less than 9 can be generated as follows.
[a/b for b in range(9) for a in range(1,b) if gcd(a,b)==1]
[1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 1/8, 3/8, 5/8, 7/8]
The condition on the greatest common divisor can be dropped if the set wrapper is used since duplicates are ignored.
set([a/b for b in range(9) for a in range(1,b)])
set([4/7, 2/3, 1/3, 1/2, 1/5, 1/4, 3/5, 3/4, 1/8, 6/7, 2/5, 5/7, 5/8, 3/8, 5/6, 4/5, 1/6, 3/7, 1/7, 7/8, 2/7])
We define R to the the integers modulo 81, $\mathbb{Z}_{81}$ (see Section 11.3 of Applied Discrete Structures). We then build the list of solutions to the equation 69 x = 15.
R=Integers(81)
set([ x for x in R if R(69)*x == R(15)])
set([73, 19, 46])
Cartesian Products
cartesian_produc
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/misc/mrange.py
Signature : cartesian_product_iterator()
Docstring :
Iterate over the Cartesian product.
INPUT:
* "X" - list or tuple of lists
OUTPUT: iterator over the Cartesian product of the elements of X
EXAMPLES:
sage: list(cartesian_product_iterator([[1,2], ['a','b']]))
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]
sage: list(cartesian_product_iterator([]))
[()]
B3=cartesian_product(range(2),range(2))
Error in lines 1-1
Traceback (most recent call last):
File "/projects/sage/sage-7.3/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 976, in execute
exec compile(block+'\n', '', 'single') in namespace, locals
File "", line 1, in
File "sage/misc/lazy_import.pyx", line 386, in sage.misc.lazy_import.LazyImport.__call__ (/projects/sage/sage-7.3/src/build/cythonized/sage/misc/lazy_import.c:3636)
return self._get_object()(*args, **kwds)
TypeError: __call__() takes exactly 2 arguments (3 given)
B3.cardinality()
B3.list()
[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
type(B3)
def parity(s): var('p') p=0 for k in s: p+=k return p.mod(2)
parity([1,1,1])
1
Here, we append a parity bit to each element of B3 to produce eight sequence of four bits, all with even parity.
for s in B3: print(s+[parity(s)])
[0, 0, 0, 0]
[0, 0, 1, 1]
[0, 1, 0, 1]
[0, 1, 1, 0]
[1, 0, 0, 1]
[1, 0, 1, 0]
[1, 1, 0, 0]
[1, 1, 1, 1]
Basic Combinatorial Calculations
The factorial function is method attached to integers
5.factorial()
120
Binomial coefficients are computed by the function binomial.
binomial(52,5)
2598960
var('n')binomial(n,2)
1/2*(n - 1)*n
The binomial_coefficents function creates a dictionary of values.
binomial_coefficients(8)
{(5, 3): 56, (2, 6): 28, (7, 1): 8, (8, 0): 1, (4, 4): 70, (6, 2): 28, (1, 7): 8, (0, 8): 1, (3, 5): 56}
large=binomial_coefficients(100)
large[(60,40)]
13746234145802811501267369720
large.values()
[141629804643600, 93206558875049876949581681100, 161700, 132341572939212267400, 38116532895986727945334202400, 13746234145802811501267369720, 1917353200780443050763600, 5670048986634686922786117600, 84413487283064039501507937600, 49378235797073715747364762200, 1345860629046814650, 141629804643600, 66324638306863423796047200, 1095067153187962886461165020, 4998813702034726525205100, 4950, 9013924030034630492634340800, 580717429720889409486981450, 161700, 98913082887808032681188722800, 30664510802988208300, 79776075565900368755100, 75287520, 6650134872937201800, 1345860629046814650, 1977204582144932989443770175, 6650134872937201800, 4950, 28258808871162574166368460400, 1050421051106700, 29372339821610944823963760, 73470998190814997343905056800, 24865270306254660391200, 253338471349988640, 73470998190814997343905056800, 30664510802988208300, 143012501349174257560226775, 3420029547493938143902737600, 1902231808400, 20116440213369968050635175200, 1977204582144932989443770175, 16007560800, 7332066885177656269200, 294692427022540894366527900, 66324638306863423796047200, 3420029547493938143902737600, 7110542499799200, 79776075565900368755100, 186087894300, 4998813702034726525205100, 16007560800, 294692427022540894366527900, 29372339821610944823963760, 242519269720337121015504, 580717429720889409486981450, 100891344545564193334812497256, 38116532895986727945334202400, 84413487283064039501507937600, 253338471349988640, 1050421051106700, 242519269720337121015504, 535983370403809682970, 1, 75287520, 28258808871162574166368460400, 186087894300, 535983370403809682970, 20116440213369968050635175200, 699574816500972464467800, 5670048986634686922786117600, 1917353200780443050763600, 44186942677323600, 24865270306254660391200, 44186942677323600, 3921225, 12410847811948286545336800, 699574816500972464467800, 1, 9013924030034630492634340800, 143012501349174257560226775, 1192052400, 3921225, 1902231808400, 1192052400, 2041841411062132125600, 2041841411062132125600, 1095067153187962886461165020, 49378235797073715747364762200, 17310309456440, 98913082887808032681188722800, 100, 13746234145802811501267369720, 100, 17310309456440, 12410847811948286545336800, 132341572939212267400, 61448471214136179596720592960, 61448471214136179596720592960, 7332066885177656269200, 7110542499799200, 93206558875049876949581681100]