Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
sagemath
GitHub Repository: sagemath/sagelib
Path: blob/master/sage/combinat/composition_signed.py
4045 views
1
r"""
2
Signed Compositions
3
"""
4
#*****************************************************************************
5
# Copyright (C) 2007 Mike Hansen <[email protected]>,
6
#
7
# Distributed under the terms of the GNU General Public License (GPL)
8
#
9
# This code is distributed in the hope that it will be useful,
10
# but WITHOUT ANY WARRANTY; without even the implied warranty of
11
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12
# General Public License for more details.
13
#
14
# The full text of the GPL is available at:
15
#
16
# http://www.gnu.org/licenses/
17
#*****************************************************************************
18
19
from combinat import CombinatorialClass
20
import composition
21
import cartesian_product
22
from sage.rings.all import binomial, Integer
23
import __builtin__
24
25
def SignedCompositions(n):
26
"""
27
Returns the combinatorial class of signed compositions of n.
28
29
EXAMPLES::
30
31
sage: SC3 = SignedCompositions(3); SC3
32
Signed compositions of 3
33
sage: SC3.cardinality()
34
18
35
sage: len(SC3.list())
36
18
37
sage: SC3.first()
38
[1, 1, 1]
39
sage: SC3.last()
40
[-3]
41
sage: SC3.random_element()
42
[1, -1, 1]
43
sage: SC3.list()
44
[[1, 1, 1],
45
[1, 1, -1],
46
[1, -1, 1],
47
[1, -1, -1],
48
[-1, 1, 1],
49
[-1, 1, -1],
50
[-1, -1, 1],
51
[-1, -1, -1],
52
[1, 2],
53
[1, -2],
54
[-1, 2],
55
[-1, -2],
56
[2, 1],
57
[2, -1],
58
[-2, 1],
59
[-2, -1],
60
[3],
61
[-3]]
62
"""
63
return SignedCompositions_n(n)
64
65
class SignedCompositions_n(CombinatorialClass):
66
def __init__(self, n):
67
"""
68
TESTS::
69
70
sage: SC3 = SignedCompositions(3)
71
sage: SC3 == loads(dumps(SC3))
72
True
73
"""
74
self.n = n
75
76
def __repr__(self):
77
"""
78
TESTS::
79
80
sage: repr(SignedCompositions(3))
81
'Signed compositions of 3'
82
"""
83
return "Signed compositions of %s"%self.n
84
85
def __contains__(self, x):
86
"""
87
TESTS::
88
89
sage: [] in SignedCompositions(0)
90
True
91
sage: [0] in SignedCompositions(0)
92
False
93
sage: [2,1,3] in SignedCompositions(6)
94
True
95
sage: [-2, 1, -3] in SignedCompositions(6)
96
True
97
"""
98
if x == []:
99
return True
100
101
if isinstance(x, __builtin__.list):
102
for i in range(len(x)):
103
if not isinstance(x[i], (int, Integer)):
104
return False
105
if x[i] == 0:
106
return False
107
return True
108
else:
109
return False
110
111
return sum([abs(i) for i in x]) == self.n
112
113
def cardinality(self):
114
"""
115
TESTS::
116
117
sage: SC4 = SignedCompositions(4)
118
sage: SC4.cardinality() == len(SC4.list())
119
True
120
sage: SignedCompositions(3).cardinality()
121
18
122
"""
123
return sum([ binomial(self.n-1, i-1)*2**(i) for i in range(1, self.n+1)])
124
125
def __iter__(self):
126
"""
127
TESTS::
128
129
sage: SignedCompositions(0).list() #indirect doctest
130
[[]]
131
sage: SignedCompositions(1).list() #indirect doctest
132
[[1], [-1]]
133
sage: SignedCompositions(2).list() #indirect doctest
134
[[1, 1], [1, -1], [-1, 1], [-1, -1], [2], [-2]]
135
"""
136
for comp in composition.Compositions(self.n):
137
l = len(comp)
138
a = [[1,-1] for i in range(l)]
139
for sign in cartesian_product.CartesianProduct(*a):
140
yield [ sign[i]*comp[i] for i in range(l)]
141
142
143